Optimal b-Colourings and Fall Colourings in $H$-Free Graphs
This work addresses theoretical computer science problems in graph theory, providing incremental complexity classifications for specific graph classes.
The paper tackles the computational complexity of four graph coloring problems (b-Chromatic Number, Tight b-Chromatic Number, Fall Chromatic Number, Fall Achromatic Number) in H-free graphs, fully classifying three problems and developing techniques to determine polynomial-time solvable and NP-complete cases for the fourth, including a novel separation where b-Chromatic Number is NP-hard but Tight b-Chromatic Number is polynomial-time solvable in H-free graphs.
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.