The size of a minimum five-chromatic K_ 4-free graph

DOI10.1016/0012-365X(93)90309-HMaRDI QIDQ1313876zbMATH OpenOpenAlexFDO

Authors D. Hanson, Gary MacGillivray, Dale Youngs

Publication date 6 June 1994

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(93)90309-h

zbMATH Keywords

chromatic numberfive-chromatic graphGrötzsch graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Review text

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.

Recommendations

• Small graphs with chromatic number 5: A computer search
• Triangle-free four-chromatic graphs
• The minimum number of vertices for a triangle-free graph with \(\chi _l(G)=4\) is \(11\)
• THE CHROMATIC NUMBER OF -FREE GRAPHS
• On minimal triangle-free 6-chromatic graphs

Cites work

• Graph theory
• scientific article; zbMATH DE number 4134067 (Why is no real title available?)
• scientific article; zbMATH DE number 3871392 (Why is no real title available?)
• Small graphs with chromatic number 5: A computer search

Cited in

(4)

• On the small graphs with chromatic number 5 without 4-cliques
• The total coloring of \(K_5\)-minor-free graphs
• Small graphs with chromatic number 5: A computer search
• The minimum number of vertices for a triangle-free graph with \(\chi _l(G)=4\) is \(11\)

This page was built for publication: The size of a minimum five-chromatic \(K_ 4\)-free graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1313876)