Optimal b-Colourings and Fall Colourings in $H$-Free Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915983148449792 |
|---|---|
| author | Ahn, Jungho Eagling-Vose, Tala Lucke, Felicia Manlove, David Mendoza, Fabricio Paulusma, Daniël |
| author_facet | Ahn, Jungho Eagling-Vose, Tala Lucke, Felicia Manlove, David Mendoza, Fabricio Paulusma, Daniël |
| contents | In a colouring of a graph, a vertex is b-chromatic if it is adjacent to a vertex of every other colour. We consider four well-studied colouring problems: b-Chromatic Number, Tight b-Chromatic Number, Fall Chromatic Number and Fall Achromatic Number, which fit into a framework based on whether every colour class has (i) at least one b-chromatic vertex, (ii) exactly one b-chromatic vertex, or (iii) all of its vertices being b-chromatic. By combining known and new results, we fully classify the computational complexity of b-Chromatic Number, Fall Chromatic Number and Fall Achromatic Number in $H$-free graphs. For Tight b-Chromatic Number in $H$-free graphs, we develop a general technique to determine new graphs $H$, for which the problem is polynomial-time solvable, and we also determine new graphs $H$, for which the problem is still NP-complete. We show, for the first time, the existence of a graph $H$ such that in $H$-free graphs, b-Chromatic Number is NP-hard, while Tight b-Chromatic Number is polynomial-time solvable. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_26214 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Optimal b-Colourings and Fall Colourings in $H$-Free Graphs Ahn, Jungho Eagling-Vose, Tala Lucke, Felicia Manlove, David Mendoza, Fabricio Paulusma, Daniël Combinatorics Computational Complexity Discrete Mathematics Data Structures and Algorithms In a colouring of a graph, a vertex is b-chromatic if it is adjacent to a vertex of every other colour. We consider four well-studied colouring problems: b-Chromatic Number, Tight b-Chromatic Number, Fall Chromatic Number and Fall Achromatic Number, which fit into a framework based on whether every colour class has (i) at least one b-chromatic vertex, (ii) exactly one b-chromatic vertex, or (iii) all of its vertices being b-chromatic. By combining known and new results, we fully classify the computational complexity of b-Chromatic Number, Fall Chromatic Number and Fall Achromatic Number in $H$-free graphs. For Tight b-Chromatic Number in $H$-free graphs, we develop a general technique to determine new graphs $H$, for which the problem is polynomial-time solvable, and we also determine new graphs $H$, for which the problem is still NP-complete. We show, for the first time, the existence of a graph $H$ such that in $H$-free graphs, b-Chromatic Number is NP-hard, while Tight b-Chromatic Number is polynomial-time solvable. |
| title | Optimal b-Colourings and Fall Colourings in $H$-Free Graphs |
| topic | Combinatorics Computational Complexity Discrete Mathematics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2603.26214 |