Volume 27, Number 2, 241-243, DOI: 10.1007/s00493-007-0054-1

On The Chromatic Number Of Pentagon-Free Graphs Of Large Minimum Degree

Carsten Thomassen

View Related Documents

Abstract

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

Fulltext Preview

Image of the first page of the fulltext document