@comment{{This file has been generated by bib2bib 1.97}}

@comment{{Command line: /usr/bin/bib2bib --expand -ob theor.bib -oc theor-list.bib ../all-entries.bib ./bib-gualandi.bib -c 'keywords : "graph coloring problem"' -c 'keywords : "theoretical analyses" | keywords : "theory"'}}

@article{AloKriSud99, title = {Coloring graphs with sparse neighborhoods}, author = {N. Alon and M. Krivelevich and B. Sudakov}, journal = {Journal of Combinatorial Theory, Ser. B}, year = {1999}, pages = {73--82}, volume = {77}, keywords = {graph coloring problem, theoretical analyses} }

@article{AppHakKoc77, title = {Every planar map is four colorable}, author = {K. Appel and W. Haken and J. Koch}, journal = {Illinois Journal of Mathematics}, year = {1977}, pages = {429-567}, volume = {21}, keywords = {graph coloring problem, theoretical analyses} }

@book{Bol04, title = {Random graphs}, author = {B\'ela Bollob\'as}, publisher = {Cambridge University Press}, year = {2004}, address = {Cambridge, UK}, edition = {second}, series = {Cambridge studies in advanced mathematics}, keywords = {graph coloring problem, theoretical analyses} }

@article{Bol85, title = {Random graphs of small order}, author = {B. Bollob\'as and A. Thomason}, journal = {Annals of Discrete Mathematics}, year = {1985}, pages = {251--256}, volume = {28}, keywords = {graph coloring problem, theoretical analyses} }

@book{BraBanSpi99, title = {Graph Classes: A Survey}, author = {A. Brandst\"adt and V. Bang Le and J.~P. Spinrad}, publisher = {SIAM Society for Industrial and Applied Mathematics}, year = {1999}, address = {Philadelphia}, series = {Monographs on Discrete Mathematics and Applications}, volume = {3}, keywords = {graph coloring problem, theoretical analyses} }

@article{CamEdm05, title = {Colouring Some Classes of Perfect Graphs Robustly}, author = {Kathie Cameron and Jack Edmonds}, journal = {Electronic Notes in Discrete Mathematics}, year = {2005}, pages = {553--556}, volume = {22}, doi = {doi:10.1016/j.endm.2005.06.083}, keywords = {graph coloring problem, theoretical analyses} }

@misc{Chv04, title = {Coloring the queen graphs}, author = {V. Chv\'atal}, note = {Web repository (last visited July 2005)}, year = {2004}, keywords = {graph coloring problem, theoretical analyses, instances}, url = {http://www.cs.concordia.ca/~chvatal/queengraphs.html} }

@book{diestel, title = {Graph Theory}, author = {R. Diestel}, publisher = {Springer}, year = {2000}, address = {Berlin}, edition = {second ed., electronic}, month = {February}, keywords = {graph coloring problem, theoretical analyses} }

@article{Erd61, title = {Graph theory and probability {II}}, author = {P.~Erd{\H{o}}s}, journal = {Canadian Journal of Mathematics}, year = {1961}, pages = {346--352}, volume = {13}, keywords = {graph coloring problem, theoretical analyses} }

@book{GarJoh79, title = {Computers and Intractability: A Guide to the Theory of {${\cal NP}$}-Completeness}, author = {M. R. Garey and D. S. Johnson}, publisher = {Freeman, San Francisco, CA, USA}, year = {1979}, keywords = {graph coloring problem, theoretical analyses} }

@article{GarJoh76, title = {The Complexity of Near Optimal Graph Coloring}, author = {M. R. Garey and D. S. Johnson}, journal = {Journal of the Association for Computing Machinery}, year = {1976}, pages = {43--49}, volume = {23}, keywords = {graph coloring problem, theoretical analyses} }

@article{GarJohMilPap80, title = {The Complexity of Coloring Circular Arcs and Chords}, author = {M. R. Garey and D. S. Johnson and G. L. Miller and C. H. Papadimitriou}, journal = {SIAM Journal of Algebraic and Discrete Methods}, year = {1980}, pages = {216--227}, volume = {1}, keywords = {graph coloring problem, theoretical analyses} }

@book{Golumbic2004, title = {Algorithmic graph theory and perfect graphs}, author = {Martin Charles Golumbic}, publisher = {Elsevier}, year = {2004}, edition = {2}, keywords = {graph coloring problem, theory}, owner = {marco}, timestamp = {2010.11.20} }

@unpublished{Gon04, title = {A computer-checked proof of the four-colour theorem}, author = {Georges Gonthier}, note = {Available online (Last visited July 2005)}, year = {2004}, keywords = {graph coloring problem, theoretical analyses}, url = {http://research.microsoft.com/~gonthier/} }

@article{Grotschel1981, title = {The ellipsoid method and its consequences in combinatorial optimization}, author = {Martin Gr{\"o}tschel and L{\'a}szlo Lov{\'a}sz and Alexander Schrijver}, journal = {Combinatorica}, year = {1981}, number = {2}, pages = {169--197}, volume = {1}, classmath = {*90C10 68Q25 65K05 90C05 90C09}, keywords = {graph coloring problem, theory}, language = {English} }

@book{JenTof94, title = {Graph Coloring Problems}, author = {T. R. Jensen and B. Toft}, publisher = {John Wiley \& Sons, New York, NY, USA}, year = {1994}, keywords = {graph coloring problem, theoretical analyses} }

@inproceedings{Joh74:b, title = {Worst-case behavior of graph-coloring algorithms}, author = {D.~S.~Johnson}, booktitle = {South-Eastern Conference on Combinatorics, Graph Theory and Computing}, year = {1974}, editor = {F. Hoffman and R.A. Kingsley and R.B. Levow and R.C. Mullin and R.S.D. Thomas}, pages = {513--528}, publisher = {Utilitas Mathematica Publishing, Winnipeg, Canada}, series = {Congressus Numerantium}, volume = {X}, keywords = {graph coloring problem, theoretical analyses} }

@techreport{JohMat82, title = {Probabilistic Bounds and Heuristic Algorihms for Coloring Large Random Graphs}, author = {A.~Johri and D.W.~Matula}, institution = {Southern Methodist University}, year = {1982}, address = {Dallas, Texas, USA}, number = {82-CSE-6}, keywords = {graph coloring problem, theoretical analyses} }

@incollection{Kar72, title = {Reducibility among combinatorial problems}, author = {R.~M.~Karp}, booktitle = {Complexity of Computer Computations}, publisher = {Plenum Press}, year = {1972}, address = {New York, USA}, editor = {R. E. Miller and J. W. Thatcher}, pages = {85--103}, keywords = {graph coloring problem, theoretical analyses} }

@article{Knuth1994, title = {The Sandwich Theorem}, author = {Knuth, Donald E.}, journal = {Electron. J. Combin.}, year = {1994}, pages = {Article 1, approx.\ 48 pp.\ (electronic)}, volume = {1}, ee = {http://www.combinatorics.org/Volume_1/Abstracts/v1i1a1.html}, keywords = {graph coloring problem, theory}, url = {http://www.combinatorics.org/Volume_1/PDFFiles/v1i1a1.pdf} }

@article{Lovasz1979, title = {On the {S}hannon capacity of a graph}, author = {L. Lov{\'a}sz}, journal = {IEEE Transactions on Information Theory}, year = {1979}, pages = {1--7}, volume = {25}, keywords = {graph coloring problem, theory}, owner = {marco}, timestamp = {2010.11.20} }

@article{luc91, title = {The chromatic number of random graphs}, author = {Tomasz Luczak}, journal = {Combinatorica}, year = {1991}, number = {1}, pages = {45-54}, volume = {11}, bibsource = {DBLP, http://dblp.uni-trier.de}, keywords = {graph coloring problem, theoretical analyses} }

@book{MolRee02, title = {Graph colouring and the probabilistic method}, author = {M. Molloy and B. Reed}, publisher = {Springer}, year = {2002}, address = {Berlin}, series = {Algorithms and Combinatorics}, volume = {23}, keywords = {graph coloring problem, theoretical analyses}, pages = {xiv+326} }

@article{RobSanSeyTho96, title = {A new proof of the four-colour theorem}, author = {N. Robertson and D. P. Sanders and P. Seymour and R. Thomas}, journal = {Electronic Research Announcements of the American Mathematical Society}, year = {1996}, number = {1}, pages = {17-25}, volume = {2}, keywords = {graph coloring problem, theoretical analyses} }

@article{Sto73, title = {Planar 3-Colorability is {NP}-Complete}, author = {L.J. Stockmeyer}, journal = {SIGACT News}, year = {1973}, number = {3}, pages = {19--25}, volume = {5}, keywords = {graph coloring problem, theoretical analyses} }

@inproceedings{TakHig06, title = {Vertex Coloring of Comparability+{\it }e and -{\it }e Graphs}, author = {Yasuhiko Takenaga and Kenichi Higashide}, booktitle = {Graph-Theoretic Concepts in Computer Science}, year = {2006}, editor = {Fedor V. Fomin}, pages = {102-112}, publisher = {Springer Verlag, Berlin, Germany}, series = {Lecture Notes in Computer Science}, volume = {4271}, doi = {10.1007/11917496_10}, keywords = {graph coloring problem, theoretical analyses}, optbooktitle = {32nd International Workshop, WG 2006, Bergen, Norway, June 22-24, 2006, Revised Papers} }

@article{Talbi2007, title = {Breaking the search space symmetry in partitioning problems: An application to the graph coloring problem}, author = {El-Ghazali Talbi and Benjamin Weinberg}, journal = {Theoretical Computer Science}, year = {2007}, number = {1}, pages = {78 - 86}, volume = {378}, doi = {10.1016/j.tcs.2007.01.023}, issn = {0304-3975}, keywords = {graph coloring problem, population-based metaheuristics, theoretical analyses}, opturl = {http://www.sciencedirect.com/science/article/B6V1G-4N2TS51-1/2/c0e14c7ab5 b51f7eb823df7840578e48} }

@inproceedings{VenLev88, title = {Random instances of a graph coloring problem are hard}, author = {Ramarathnam Venkatesan and Leonid Levin}, booktitle = {STOC '88: Proceedings of the twentieth annual ACM symposium on Theory of computing}, year = {1988}, address = {New York, NY, USA}, pages = {217--222}, publisher = {ACM Press}, doi = {http://doi.acm.org/10.1145/62212.62231}, isbn = {0-89791-264-0}, keywords = {graph coloring problem, theoretical analyses}, location = {Chicago, Illinois, United States} }

@proceedings{NesWoe05, title = {Graph Colorings, Dagstuhl, Germany, 2003}, year = {2005}, editor = {J. Ne\v{s}et\v{r}il and G. Woeginger}, volume = {349}, booktitle = {Theoretical Computer Science}, keywords = {graph coloring problem, theoretical analyses} }