3
$\begingroup$

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.$

Improve this question
$\endgroup$

1 Answer 1

Reset to default
8
$\begingroup$

22 vertices, there are 80 of them.

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

Improve this answer
$\endgroup$
6
  • 2
    $\begingroup$ Volume 19, Issue 1, January 1995, pp 107-116. $\endgroup$
    – Gerry Myerson
    Feb 5, 2018 at 22:34
  • $\begingroup$ Note: The paper finds 80 graphs but doesn’t claim completeness. $\endgroup$
    – Charles
    Feb 6, 2018 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, 2018 at 7:42
  • $\begingroup$ @GordonRoyle Do you mind if I quote you on that? $\endgroup$
    – Charles
    Feb 13, 2018 at 21:04
  • $\begingroup$ @Charles, feel free to quote me. $\endgroup$
    – Gordon Royle
    Feb 13, 2018 at 23:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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