The Grötzsch graph is triangle-free and has chromatic number 4. At 11 vertices it is the (unique) smallest graph with these properties.

What is the smallest number of vertices needed for a triangle-free graph with chromatic number 5? The Mycielskian of the Grötzsch graph has 23 vertices, so it's not larger than that.

There are far too many triangle-free connected graphs for enumeration to be a viable strategy. This question may well be unsolved; if so, I'd love a citation saying as much (if such exists).

Reed's conjecture implies that any such graph has max degree $\Delta\ge6.$


22 vertices, there are 80 of them.

Jensen and Royle, Small graphs with chromatic number 5 : a computer search Journal of Graph Theory, 1995.

  • 2
    $\begingroup$ Volume 19, Issue 1, January 1995, pp 107-116. $\endgroup$ – Gerry Myerson Feb 5 '18 at 22:34
  • $\begingroup$ Note: The paper finds 80 graphs but doesn’t claim completeness. $\endgroup$ – Charles Feb 6 '18 at 7:27
  • 2
    $\begingroup$ I’ve redone it recently and confirmed that 80 is correct (should have said that in original answer, but can’t type well on small screen). $\endgroup$ – Gordon Royle Feb 6 '18 at 7:42
  • $\begingroup$ @GordonRoyle Do you mind if I quote you on that? $\endgroup$ – Charles Feb 13 '18 at 21:04
  • $\begingroup$ @Charles, feel free to quote me. $\endgroup$ – Gordon Royle Feb 13 '18 at 23:17

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.