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