We prove that, for each fixed real number c > 0, the pentagon-free graphs of minimum degree at least cn (where n is the number of vertices) have bounded chromatic number. This problem was raised by Erdős and Simonovits in 1973. A similar result holds for any other fixed odd cycle, except the triangle for which there is no such result for c<1/3.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Thomassen, C. On The Chromatic Number Of Pentagon-Free Graphs Of Large Minimum Degree. Combinatorica 27, 241–243 (2007). https://doi.org/10.1007/s00493-007-0054-1
Received:
Issue Date:
DOI: https://doi.org/10.1007/s00493-007-0054-1