Properties of Descartes' Construction of Triangle-Free Graphs with High Chromatic Number
Alexandr V. Kostochka, Jaroslav Nešetřil · Combinatorics Probability Computing · 1999
We present some nice properties of the classical construction of triangle-free graphs with high chromatic number given by Blanche Descartes and its modifications. In particular, we construct colour-critical graphs and hypergraphs of high girth with moderate average degree.