Small graphs with chromatic number 5: A computer search
Tommy R. Jensen, Gordon Royle · Journal of Graph Theory · 1995
Abstract In this article we give examples of a triangle‐free graph on 22 vertices with chromatic number 5 and a K4‐free graph on 11 vertices with chromatic number 5. We very briefly describe the computer searches demonstrating that these are the smallest possible such graphs. All 5‐critical graphs on 9 vertices are exhibited. © 1995 John Wiley & Sons, Inc.