4-chromatic graphs with large odd girth (Q1842185)

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.