b-Coloring Parameterized by Clique-Width
share
We provide a polynomial-time algorithm for b-Coloring on graphs of constant clique-width. This unifies and extends previously known polynomial-time results on several graph classes, and answers open questions posed by Campos and Silva [Algorithmica, 2018] and Bonomo et al. [Graphs Combin., 2009]. This constitutes the first result concerning structural parameterizations of this problem. We show that the problem is FPT when parameterized by the vertex cover number on general graphs, and on chordal graphs when parameterized by the number of colors. Additionally, we observe that our algorithm for graphs of bounded clique-width can be adapted to solve the Fall Coloring problem within the same runtime bound.
READ FULL TEXT