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



Smallest triangle-free graph with chromatic number 5
22 vertices, there are 80 of them.


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


