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.
Mathematics Subject Classification (2000): 05C15