無限グラフ G の全ての有限部分グラフが k-彩色可能であれば、選択公理を仮定した場合にG自体も同様である(de Bruijn & Erdős 1951)。
また、n ≥ n0 の n 色全部を使って彩色可能なグラフは、無限完全彩色可能である(Fawcett 1978)。
未解決の問題
単位距離だけ離れている任意の2つの点が同じ色にならないように平面を彩色する問題 (Hadwiger–Nelson problem) は未解決だが、その彩色数は5、6、7のいずれかだということまでは判明している。その他のグラフの彩色数に関する未解決問題としては、Hadwiger予想(en)がある。これは、彩色数 k のグラフはマイナーとして頂点 k 個の完全グラフを含む、という予想である。また、Erdős–Faber–Lovász予想(en)は、k-クリークが互いに高々1つの頂点を共有する形でk個連結されたグラフはk-彩色的だ、というものである。Albertson予想(en)は、k-彩色的グラフの中で完全グラフが最も交差数が小さい、というものである。
BirkhoffとLewisは四色問題を攻略する手段として彩色多項式を導入し、平面グラフ G の彩色多項式 は の領域でゼロにならないという予想を立てた。そのような彩色多項式が の領域でゼロにならないことと、 であることは判明しているが、彼らの予想自体は未解決である。任意の2つのグラフの彩色多項式が同一かどうかの判定や、ある多項式が彩色多項式かどうかの判定も未解決の問題である。
グラフ G の縮約 とは、グラフ内の頂点 u と v を特定し、それらの間の辺を全て除去し、その2つの頂点を1つの新たな頂点 w に置き換え、u や v と接合していた全ての辺を w に繋ぎかえることでできるグラフである。この操作はグラフ彩色の解析において重要な役割を演じる。
Zykov (1949) によれば、彩色数は次の漸化式を満たす。
u と v が隣接した頂点でない場合、 は辺 を加えたグラフを意味する。この漸化式を評価することに基づくアルゴリズムもいくつかあり、それによって形成される計算木を Zykov 木と呼ぶこともある。実際にかかる時間は頂点 u と v の選択のしかた(ヒューリスティック)に依存する。
彩色多項式は次の漸化式を満たす。
u と v が隣接した頂点の場合、 は辺 を除去したグラフを意味する。 はそのグラフの彩色の組み合わせ数を表し、u と v が同色の場合もそうでない場合も含まれる。上の式から、彩色の組み合わせ数は2つのグラフの彩色組み合わせ数の和で表される。頂点 u と v の色が異なる場合、u と v が1つの辺で結ばれたグラフでも同じ彩色が可能である。u と v が同色の場合、u と v を縮約したグラフと同じとみなすことができる。W・T・タットはこの漸化式を満たすグラフの属性について興味を持ち、彩色多項式を一般化したタット多項式を発見した。
Barenboim, L.; Elkin, M. (2009), “Distributed (Δ + 1)-coloring in linear (in Δ) time”, Proceedings of the 41st Symposium on Theory of Computing, pp. 111–120, doi:10.1145/1536414.1536432
Beigel, R.; Eppstein, D. (2005), “3-coloring in time O(1.3289n)”, Journal of Algorithms54 (2)): 168–204, doi:10.1016/j.jalgor.2004.06.008
Björklund, A.; Husfeldt, T.; Koivisto, M. (2009), “Set partitioning via inclusion–exclusion”, SIAM Journal on Computing39 (2): 546–563, doi:10.1137/070683933
Brèlaz, D. (1979), “New methods to color the vertices of a graph”, Communications of the ACM22: 251–256, doi:10.1145/359094.359101
Brooks, R. L.; Tutte, W. T. (1941), “On colouring the nodes of a network”, Proceedings of the Cambridge Philosophical Society37: 194–197, doi:10.1017/S030500410002168X
de Bruijn, N. G.; Erdős, P. (1951), “A colour problem for infinite graphs and a problem in the theory of relations”, Nederl. Akad. Wetensch. Proc. Ser. A54: 371–373, http://www.math-inst.hu/~p_erdos/1951-01.pdf (= Indag. Math.13)
Byskov, J.M. (2004), “Enumerating maximal independent sets with applications to graph colouring”, Operations Research Letters32: 547–556, doi:10.1016/j.orl.2004.03.002
Chaitin, G. J. (1982), “Register allocation & spilling via graph colouring”, Proc. 1982 SIGPLAN Symposium on Compiler Construction, pp. 98–105, doi:10.1145/800230.806984
Cole, R.; Vishkin, U. (1986), “Deterministic coin tossing with applications to optimal parallel list ranking”, Information and Control70 (1): 32–53, doi:10.1016/S0019-9958(86)80023-7
Cormen, T. H.; Leiserson, C. E.; Rivest, R. L. (1990), Introduction to Algorithms (1st ed.), The MIT Press
Dailey, D. P. (1980), “Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete”, Discrete Mathematics30: 289–293, doi:10.1016/0012-365X(80)90236-8
Duffy, K.; O'Connell, N.; Sapozhnikov, A. (2008), “Complexity analysis of a decentralised graph colouring algorithm”, Information Processing Letters107: 60–63, doi:10.1016/j.ipl.2008.01.002
Fawcett, B. W. (1978), “On infinite full colourings of graphs”, Canadian Journal of MathematicsXXX: 455–457
Garey, M. R.; Johnson, D. S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, ISBN 0-7167-1045-5
Garey, M. R.; Johnson, D. S.; Stockmeyer, L. (1974), “Some simplified NP-complete problems”, Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, pp. 47–63, http://portal.acm.org/citation.cfm?id=803884
Goldberg, L. A.; Jerrum, M. (July 2008), “Inapproximability of the Tutte polynomial”, Information and Computation206 (7): 908–929, doi:10.1016/j.ic.2008.04.003
Goldberg, A. V.; Plotkin, S. A.; Shannon, G. E. (1988), “Parallel symmetry-breaking in sparse graphs”, SIAM Journal on Discrete Mathematics1 (4): 434–446, doi:10.1137/0401044
Guruswami, V.; Khanna, S. (2000), “On the hardness of 4-coloring a 3-colorable graph”, Proceedings of the 15th Annual IEEE Conference on Computational Complexity, pp. 188–197, doi:10.1109/CCC.2000.856749
Halldórsson, M. M. (1993), “A still better performance guarantee for approximate graph coloring”, Information Processing Letters45: 19–23, doi:10.1016/0020-0190(93)90246-6
Holyer, I. (1981), “The NP-completeness of edge-coloring”, SIAM Journal on Computing10: 718–720, doi:10.1137/0210055
Crescenzi, P.; Kann, V. (December 1998), “How to find the best approximation results — a follow-up to Garey and Johnson”, ACM SIGACT News29: 90, doi:10.1145/306198.306210
Jaeger, F.; Vertigan, D. L.; Welsh, D. J. A. (1990), “On the computational complexity of the Jones and Tutte polynomials”, Mathematical Proceedings of the Cambridge Philosophical Society108: 35–53, doi:10.1017/S0305004100068936
Jensen, T. R.; Toft, B. (1995), Graph Coloring Problems, Wiley-Interscience, New York, ISBN 0-471-02865-7
Khot, S. (2001), “Improved inapproximability results for MaxClique, chromatic number and approximate graph coloring”, Proc. 42nd Annual Symposium on Foundations of Computer Science, pp. 600–609, doi:10.1109/SFCS.2001.959936
Kubale, M. (2004), Graph Colorings, American Mathematical Society, ISBN 0-8218-3458-4
Kuhn, F. (2009), “Weak graph colorings: distributed algorithms and applications”, Proceedings of the 21st Symposium on Parallelism in Algorithms and Architectures, pp. 138–144, doi:10.1145/1583991.1584032
Lawler, E.L. (1976), “A note on the complexity of the chromatic number problem”, Information Processing Letters5 (3): 66–67, doi:10.1016/0020-0190(76)90065-X
Leith, D.J.; Clifford, P. (2006), “A Self-Managed Distributed Channel Selection Algorithm for WLAN”, Proc. RAWNET 2006, Boston, MA
Linial, N. (1992), “Locality in distributed graph algorithms”, SIAM Journal on Computing21 (1): 193–201, doi:10.1137/0221015
van Lint, J. H.; Wilson, R. M. (2001), A Course in Combinatorics (2nd ed.), Cambridge University Press, ISBN 0-521-80340-3
Marx, Dániel (2004), “Graph colouring problems and their applications in scheduling”, Periodica Polytechnica, Electrical Engineering, 48, pp. 11–16, http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.95.4268&rep=rep1&type=pdf
Mycielski, J. (1955), “Sur le coloriage des graphes”, Colloq. Math.3: 161–162, http://matwbn.icm.edu.pl/ksiazki/cm/cm3/cm3119.pdf
Sekine, K.; Imai, H.; Tani, S. (1995), “Computing the Tutte polynomial of a graph of moderate size”, Proc. 6th International Symposium on Algorithms and Computation (ISAAC 1995), Lecture Notes in Computer Science, 1004, Springer, pp. 224–233, doi:10.1007/BFb0015427
Welsh, D. J. A.; Powell, M. B. (1967), “An upper bound for the chromatic number of a graph and its application to timetabling problems”, The Computer Journal10 (1): 85–86, doi:10.1093/comjnl/10.1.85
West, D. B. (1996), Introduction to Graph Theory, Prentice-Hall, ISBN 0-13-227828-6
Wilf, H. S. (1986), Algorithms and Complexity, Prentice–Hall
Zuckerman, D. (2007), “Linear degree extractors and the inapproximability of Max Clique and Chromatic Number”, Theory of Computing3: 103–128, doi:10.4086/toc.2007.v003a006
Zykov, A. A. (1949), “О некоторых свойствах линейных комплексов (On some properties of linear complexes)” (Russian), Math. Sbornik.24(66) (2): 163–188, http://mi.mathnet.ru/eng/msb5974
関連項目
四色定理
数独
外部リンク
Chromatic number of a space at PlanetMath.org
Graph Coloring Page by Joseph Culberson (グラフ彩色プログラム)
CoLoRaTiOn by Jim Andrews and Mike Fellows (グラフ彩色パズルゲーム)
各種グラフ彩色プログラムのソースへのリンク集
Code for efficiently computing Tutte, Chromatic and Flow Polynomials by Gary Haggard, David J. Pearce and Gordon Royle