[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 ]
|