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
    Commented Feb 5, 2018 at 22:34
  • $\begingroup$ Note: The paper finds 80 graphs but doesn’t claim completeness. $\endgroup$
    – Charles
    Commented 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
    Commented Feb 6, 2018 at 7:42
  • $\begingroup$ @GordonRoyle Do you mind if I quote you on that? $\endgroup$
    – Charles
    Commented Feb 13, 2018 at 21:04
  • $\begingroup$ @Charles, feel free to quote me. $\endgroup$
    – Gordon Royle
    Commented Feb 13, 2018 at 23:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .