A structural description of Zykov and Blanche Descartes graphs
<|reference_start|>A structural description of Zykov and Blanche Descartes graphs: In 1949, Zykov proposed the first explicit construction of triangle-free graphs with arbitrarily large chromatic number. We define a Zykov graph as any induced subgraph of a graph created using Zykov's construction. 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, while being FPT in the treewidth of the input graph. We provide similar results for the Blanche Descartes construction.<|reference_end|>
@article{marin2024a,
    title={A structural description of Zykov and Blanche Descartes graphs},
    author={Malory Marin, St'ephan Thomass'e, Nicolas Trotignon and R'emi
  Watrigant},
    journal={arXiv preprint arXiv:2410.06917},
    year={2024},
    archivePrefix={arXiv},
    eprint={2410.06917},
    primaryClass={math.CO cs.CC cs.DM}
}