b-Coloring Parameterized by Clique-Width

Lars Jaffke, Paloma Thomé de Lima, Daniel Lokshtanov

Research output: Journal Article or Conference Article in JournalJournal articleResearchpeer-review


We provide a polynomial-time algorithm for b -COLORING on graphs of constant clique-width. This unifies and extends nearly all previously known polynomial time results on graph classes, and answers open questions posed by Campos and Silva (Algorithmica 80(1), 104–115, 2018) and Bonomo et al. (Graphs and Combinatorics 25(2), 153–167, 2009). This constitutes the first result concerning structural parameterizations of this problem. We show that the problem is
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. The running times of the clique-width based algorithms for
-COLORING and FALL COLORING are tight under the Exponential Time Hypothesis.
Original languageEnglish
JournalTheory of Computing Systems
Publication statusPublished - 23 Sept 2023


  • B-coloring
  • Clique-width
  • Vertex cover
  • Structural parameterization


Dive into the research topics of 'b-Coloring Parameterized by Clique-Width'. Together they form a unique fingerprint.

Cite this