theor.bib

@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}
}