A Structural Description of Zykov and Blanche Descartes Graphs

ABSTRACT Around 1950, Zykov and Blanche Descartes proposed the two first explicit constructions of triangle‐free graphs with arbitrarily large chromatic number. We define a Zykov (resp. Blanche Descartes) graph as any induced subgraph of a graph created using Zykov's construction (resp. Blanche Descartes's). We give a structural characterization of Zykov graphs based on a specific type of stable set, that we call splitting stable set. It implies that recognizing this class is NP‐complete. We provide similar results for Blanche Descartes graphs. We also observe that any Blanche Descartes graph is a Zykov graph.