Advanced search
Publication Cover
Optimization
A Journal of Mathematical Programming and Operations Research
Volume 57, 2008 - Issue 1: In Celebration of Prof. Dr Dr H. Th. Jongen's 60th Birthday, Guest Editors: Diethard Pallaschke and Oliver Stein
Submit an article Journal homepage
58
Views
0
CrossRef citations to date
0
Altmetric
Original Articles

Algorithmic bounds for the chromatic numberFootnote†

Ingo Schiermeyer Technische Universität Bergakademie Freiberg, 09596 Freiberg, GermanyCorrespondence[email protected]
Pages 153-158 | Received 15 Sep 2006, Accepted 03 Apr 2007, Published online: 27 Oct 2009

References

  • Baetz , B and Wood , DR . 2001 . Brooks' Vertex Colouring Theorem in Linear Time, TR CS-AAG-2001-05 , 4 Sydney : Basser Dep. Comput. Sci., Univ. .
  • Berge , C . 1960 . Les problèms de coloration en théorie des graphes . Publ. Inst. Statist. Univ. Paris , 9 : 123 – 160 .
  • Berge , C . 1963 . “ Perfect graphs ” . In in Six papers on graph theory , 1 – 21 . Calcutta : Indian Statistical Institute .
  • Beutelsbacher , A and Hering , PR . 1984 . Minimal graphs for which the chromatic number equals the maximal degree . Ars Combin. , 18 : 201 – 216 .
  • Brooks , RL . 1941 . On colouring the nodes of a network . Proc. Cambridge Phil. Soc. , 37 : 194 – 197 .
  • Chvátal , V . 1970 . The smallest triangle-free, 4-chromatic, 4-regular graph . J. Combin. Theory , 9 : 93 – 94 .
  • Chudnovsky , M . 2003 . Progress on perfect graphs . Math. Program. Ser. B , 97 : 405 – 422 .
  • —— . 2006 . The strong perfect graph theorem . Ann. Math. (2) , 164 ( 1 ) : 51 – 229 .
  • Chudnovsky , M . 2005 . Recognizing Berge Graphs . Combinatorica , 25 ( 2 ) : 143 – 186 .
  • Erdős , P . 1959 . Graph theory and probability . Canad. J. Math. , 11 : 34 – 38 .
  • Gross , JL and Yellen , J . 2004 . Handbook of Graph Theory , Boca Raton : CRC Press .
  • Johansson , AR . 1996 . Asymptotic choice number for triangle-free graphs . Preprint DIMACS ,
  • Kim , JH . 1995 . On Brooks' theorem for sparse graphs . Combin. Prob. Comput. , 4 : 97 – 132 .
  • Lovász , L . 1975 . Three short proofs in graph theory . J. Combin. Theory Ser. B , 19 : 269 – 271 .
  • Molloy , M and Reed , B . 2002 . “ eds. ” . In Graph Colourings and the Probabilistc Method, Algorithms and Combinatorics 23 , Berlin : Springer-Verlag .
  • Randerath , B and Schiermeyer , I . 2004 . Vertex colouring and forbidden subgraphs - a survey . Graphs Combinatorics , 20 ( 1 ) : 1 – 40 .
  • Randerath , B and Schiermeyer , I . 2006 . “ On Reed's Conjecture about ω, Δ and χ ” . In in Graph Theory, Trends in Mathematics , Edited by: Bondy , A. 337 – 344 . Basel/Switzerland : Birkhäuser Verlag .
  • Reed , BA . 1998 . ω, Δ and χ . J. Graph Theory , 27 ( 4 ) : 177 – 212 .
  • Reed , BA . 1999 . A Strengthening of Brooks' Theorem . J. Combin. Theory Ser. B , 76 ( 2 ) : 136 – 149 .
  • Stacho , L . 2001 . New Upper Bounds for the Chromatic Number of a Graph . J. Graph Theory , 36 : 117 – 120 .
  • Welsh , DJ and Powell , MB . 1967/68 . An upper bound for the chromatic number of a graph and its application to time tabling problems . Computer J. , 10 : 85 – 86 .

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Order Reprints Request Corporate Permissions

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

Request Academic Permissions

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.

Related research

People also read lists articles that other readers of this article have read.

Recommended articles lists articles that we recommend and is powered by our AI driven recommendation engine.

Cited by lists all citing articles based on Crossref citations.
Articles with the Crossref icon will open in a new tab.