[TW07] E.-G. Talbi, B. Weinberg (2007). Breaking the search space symmetry in partitioning problems: An application to the graph coloring problem. Theoretical Computer Science, vol. 378, no. 1, pp. 78 - 86. [ bib | DOI ]
[TH06] Y. Takenaga, K. Higashide (2006). Vertex Coloring of Comparability+e and -e Graphs. In F. V. Fomin (ed.), Graph-Theoretic Concepts in Computer Science, vol. 4271 of Lecture Notes in Computer Science, pp. 102-112. Springer Verlag, Berlin, Germany. [ bib | DOI ]
[CE05] K. Cameron, J. Edmonds (2005). Colouring Some Classes of Perfect Graphs Robustly. Electronic Notes in Discrete Mathematics, vol. 22, pp. 553-556. [ bib | DOI ]
[NW05] J. Nešetřil, G. Woeginger (eds.) (2005). Graph Colorings, Dagstuhl, Germany, 2003, vol. 349. [ bib ]
[Bol04] B. Bollobás (2004). Random graphs. Cambridge studies in advanced mathematics. Cambridge University Press, Cambridge, UK, second edn. [ bib ]
[Chv04] V. Chvátal (2004). Coloring the queen graphs. Web repository (last visited July 2005). [ bib | .html ]
[Gol04] M. C. Golumbic (2004). Algorithmic graph theory and perfect graphs. Elsevier, 2 edn. [ bib ]
[Gon04] G. Gonthier (2004). A computer-checked proof of the four-colour theorem. Available online (Last visited July 2005). [ bib | http ]
[MR02] M. Molloy, B. Reed (2002). Graph colouring and the probabilistic method, vol. 23 of Algorithms and Combinatorics. Springer, Berlin, xiv+326 pp. [ bib ]
[Die00] R. Diestel (2000). Graph Theory. Springer, Berlin, second ed., electronic edn. [ bib ]
[AKS99] N. Alon, M. Krivelevich, B. Sudakov (1999). Coloring graphs with sparse neighborhoods. Journal of Combinatorial Theory, Ser. B, vol. 77, pp. 73-82. [ bib ]
[BLS99] A. Brandstädt, V. B. Le, J. P. Spinrad (1999). Graph Classes: A Survey, vol. 3 of Monographs on Discrete Mathematics and Applications. SIAM Society for Industrial and Applied Mathematics, Philadelphia. [ bib ]
[RSST96] N. Robertson, D. P. Sanders, P. Seymour, R. Thomas (1996). A new proof of the four-colour theorem. Electronic Research Announcements of the American Mathematical Society, vol. 2, no. 1, pp. 17-25. [ bib ]
[JT94] T. R. Jensen, B. Toft (1994). Graph Coloring Problems. John Wiley & Sons, New York, NY, USA. [ bib ]
[Knu94] D. E. Knuth (1994). The Sandwich Theorem. Electron. J. Combin., vol. 1, pp. Article 1, approx. 48 pp. (electronic). [ bib | .pdf ]
[Luc91] T. Luczak (1991). The chromatic number of random graphs. Combinatorica, vol. 11, no. 1, pp. 45-54. [ bib ]
[VL88] R. Venkatesan, L. Levin (1988). Random instances of a graph coloring problem are hard. In STOC '88: Proceedings of the twentieth annual ACM symposium on Theory of computing, pp. 217-222. ACM Press, New York, NY, USA. ISBN 0-89791-264-0. [ bib | DOI ]
[BT85] B. Bollobás, A. Thomason (1985). Random graphs of small order. Annals of Discrete Mathematics, vol. 28, pp. 251-256. [ bib ]
[JM82] A. Johri, D. Matula (1982). Probabilistic Bounds and Heuristic Algorihms for Coloring Large Random Graphs. Tech. Rep. 82-CSE-6, Southern Methodist University, Dallas, Texas, USA. [ bib ]
[GLS81] M. Grötschel, L. Lovász, A. Schrijver (1981). The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, vol. 1, no. 2, pp. 169-197. [ bib ]
[GJMP80] M. R. Garey, D. S. Johnson, G. L. Miller, C. H. Papadimitriou (1980). The Complexity of Coloring Circular Arcs and Chords. SIAM Journal of Algebraic and Discrete Methods, vol. 1, pp. 216-227. [ bib ]
[GJ79] M. R. Garey, D. S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco, CA, USA. [ bib ]
[Lov79] L. Lovász (1979). On the Shannon capacity of a graph. IEEE Transactions on Information Theory, vol. 25, pp. 1-7. [ bib ]
[AHK77] K. Appel, W. Haken, J. Koch (1977). Every planar map is four colorable. Illinois Journal of Mathematics, vol. 21, pp. 429-567. [ bib ]
[GJ76] M. R. Garey, D. S. Johnson (1976). The Complexity of Near Optimal Graph Coloring. Journal of the Association for Computing Machinery, vol. 23, pp. 43-49. [ bib ]
[Joh74] D. S. Johnson (1974). Worst-case behavior of graph-coloring algorithms. In F. Hoffman, R. Kingsley, R. Levow, R. Mullin, R. Thomas (eds.), South-Eastern Conference on Combinatorics, Graph Theory and Computing, vol. X of Congressus Numerantium, pp. 513-528. Utilitas Mathematica Publishing, Winnipeg, Canada. [ bib ]
[Sto73] L. Stockmeyer (1973). Planar 3-Colorability is NP-Complete. SIGACT News, vol. 5, no. 3, pp. 19-25. [ bib ]
[Kar72] R. M. Karp (1972). Reducibility among combinatorial problems. In R. E. Miller, J. W. Thatcher (eds.), Complexity of Computer Computations, pp. 85-103. Plenum Press, New York, USA. [ bib ]
[Erd61] P. Erdős (1961). Graph theory and probability II. Canadian Journal of Mathematics, vol. 13, pp. 346-352. [ bib ]