The size of a minimum five-chromatic \(K_ 4\)-free graph (Q1313876): Difference between revisions

The minimum number of vertices in a five-chromatic graph that does not contain \(K_ 4\) is determined. \textit{N. D. Nenov} [C. R. Acad. Bulg. Sci. 37, 301-304 (1984; Zbl 0547.05030)] has shown that the chromatic number of any ten-vertex graph without \(K_ 4\) is at most four. A well-known construction of Mycielski leads to the Grötzsch graph, an eleven- vertex, four-chromatic, triangle-free graph. Adding a new vertex adjacent to all the vertices of the Grötzsch graph creates a twelve-vertex, five-chromatic graph, not containing \(K_ 4\). Thus the minimum number of vertices in a five-chromatic, \(K_ 4\)-free graph is either eleven or twelve. We show that the correct answer is eleven by describing two examples.