On minimal triangle‐free 6‐chromatic graphs
Jan Goedgebeur · Journal of Graph Theory · 2019
Abstract A graph with chromatic number is called ‐chromatic. Using computational methods, we show that the smallest triangle‐free 6‐chromatic graphs have at least 32 and at most 40 vertices. We also determine the complete set of all triangle‐free 5‐chromatic graphs up to 24 vertices. This implies that Reed's conjecture holds for triangle‐free graphs up to at least this order. We also establish that a smallest regular triangle‐free 5‐chromatic graph has 24 vertices. Finally, we show that the smallest 5‐chromatic graphs of girth at least 5 have at least 29 vertices and that the smallest 4‐chromatic graphs of girth at least 6 have at least 25 vertices.