A 4-colour problem for dense triangle-free graphs Original Research Article

Triangle-free graphs of order n with minimum degree exceeding n/3 satisfy strong structural properties in several respects. Nevertheless, it is not known whether those graphs can have arbitrarily large chromatic number. We conjecture that these graphs are 4-colourable and give an affirmative answer for regular maximal triangle-free graphs satisfying the degree bound. Moreover, we show that the vertex transitive members of this class are 3-colourable. The indicated problem has a fractional appeal and we present several related conjectures in fractional terms.