A structural description of Zykov and Blanche Descartes graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917798515572736 |
|---|---|
| author | Marin, Malory Thomassé, Stéphan Trotignon, Nicolas Watrigant, Rémi |
| author_facet | Marin, Malory Thomassé, Stéphan Trotignon, Nicolas Watrigant, Rémi |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_06917 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A structural description of Zykov and Blanche Descartes graphs Marin, Malory Thomassé, Stéphan Trotignon, Nicolas Watrigant, Rémi Combinatorics Computational Complexity Discrete Mathematics 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. |
| title | A structural description of Zykov and Blanche Descartes graphs |
| topic | Combinatorics Computational Complexity Discrete Mathematics |
| url | https://arxiv.org/abs/2410.06917 |