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.
No takes yet. Share an insight, caveat, or question.
Marin et al. (2026) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: