グラフ彩色
P ( G , t ) {\displaystyle P(G,t)} における t n − 1 {\displaystyle t^{n-1}} の係数は − m {\displaystyle -m} である。 t 0 , t 1 , {\displaystyle t^{0},t^{1},} ... t k − 1 {\displaystyle t^{k-1}} の係数は全てゼロである。 t k {\displaystyle t^{k}} の係数はゼロではない。 P ( G , t ) = P ( G 1 , t ) P ( G 2 , t ) {\displaystyle P(G,t)=P(G_{1},t)P(G_{2},t)} ⋯ P ( G k , t ) {\displaystyle P(G_{k},t)}
全ての彩色多項式の係数は符号が交互に変化する。
P ( G , t ) = t ( t − 1 ) n − 1 {\displaystyle P(G,t)=t(t-1)^{n-1}} であるときのみ、 n {\displaystyle n} 頂点のグラフ G は木である。
単位元で評価された導関数 P ′ ( G , 1 ) {\displaystyle P'(G,1)} は「彩色不変量(chromatic invariant)」 θ ( G ) {\displaystyle \theta (G)} である。
↑ M. Kubale, History of graph coloring, in Kubale (2004)
↑ van Lint & Wilson (2001, Chap. 33)
↑ Jensen & Toft (1995, p. 2)
↑ Brooks (1941)
↑ Mycielski (1955)
↑ Heule, Marijn J.H. (2018), Computing Small Unit-Distance Graphs with Chromatic Number 5, arXiv:1805.12181, Bibcode: 2018arXiv180512181H
1 2 Björklund, Husfeldt & Koivisto (2006)
↑ Lawler (1976)
↑ Beigel & Eppstein (2005)
↑ Byskov (2004)
↑ Wilf (1986)
↑ Sekine, Imai & Tani (1995)
↑ Welsh & Powell (1967)
頂点彩色は各種スケジューリング問題のモデルとなる。最も単純化したスケジューリング問題は、一連の仕事を時間割にひとつずつ(ある時間には1つの仕事だけをするように)あてはめていくものである。個々の仕事にはリソースの競合など同時に実施できない制約条件がある。これをグラフで表すと、個々の仕事が頂点、競合する仕事を結ぶ線が辺となる。このグラフの彩色数を求める問題は、全部の仕事が終わるまでにかかる時間を最小にすることと等価である。
スケジューリング問題の詳細がそのグラフの構造を定義する。例えば航空機の運航スケジューリングの場合、インターバルグラフで表せば効率的に彩色問題として解ける。無線局の帯域幅割り当ての場合、単位円グラフで表せばよい。
↑ Brèlaz (1979)
↑ Cole & Vishkin (1986), see also Cormen, Leiserson & Rivest (1990, Section 30.5)
↑ Goldberg, Plotkin & Shannon (1988)
↑ Barenboim & Elkin (2009); see also Kuhn (2009)
↑ Leith (2006) and Duffy (2008)
↑ Dailey (1980)
↑ Halldórsson (1993)
↑ Zuckerman (2007)
↑ Guruswami & Khanna (2000)
↑ Khot (2001)
↑ Jaeger, Vertigan & Welsh (1990)
↑ Goldberg & Jerrum (2008)
↑ Holyer (1981)
↑ Crescenzi & Kann (1998)
↑ Marx (2004)
↑ Chaitin (1982)