4-chromatic graphs with large odd girth
For every \(s\geq 1\) and \(t\geq 1\), the graph \(G_{s,t}\) of order \(2st+ t+ 1\) and size \(4st+ 2t\), without short odd cycles is constructed. The authors provide a new purely combinatorial and self-contained proof that the graphs \(G_{s,t}\) are critically 4-chromatic. For \(s\geq 2\) and \(t= 2\) one gets the well-known triangle-free Mycielski graph.
scientific article; zbMATH DE number 744030