b-Coloring Parameterized by Clique-Width

Lars Jaffke; Paloma Thomé de Lima; Daniel Lokshtanov

doi:10.1007/s00224-023-10132-0

b-Coloring Parameterized by Clique-Width

Lars Jaffke, Paloma Thomé de Lima, Daniel Lokshtanov

Algorithms

Research output: Journal Article or Conference Article in Journal › Journal article › Research › peer-review

Abstract

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 language	English
Journal	Theory of Computing Systems
ISSN	1432-4350
DOIs	https://doi.org/10.1007/s00224-023-10132-0
Publication status	Published - 23 Sept 2023

Keywords

B-coloring
Clique-width
Vertex cover
Structural parameterization

Access to Document

10.1007/s00224-023-10132-0Licence: CC BY

https://link.springer.com/content/pdf/10.1007/s00224-023-10132-0.pdfLicence: CC BY

Cite this

@article{c6f9e82c0b0d4d6a8775367130b1014a,

title = "b-Coloring Parameterized by Clique-Width",

abstract = "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.",

keywords = "B-coloring, Clique-width, Vertex cover, Structural parameterization, B-coloring, Clique-width, Vertex cover, Structural parameterization",

author = "Lars Jaffke and {Thom{\'e} de Lima}, Paloma and Daniel Lokshtanov",

year = "2023",

month = sep,

day = "23",

doi = "10.1007/s00224-023-10132-0",

language = "English",

journal = "Theory of Computing Systems",

issn = "1432-4350",

publisher = "Springer New York LLC",

}

TY - JOUR

T1 - b-Coloring Parameterized by Clique-Width

AU - Jaffke, Lars

AU - Thomé de Lima, Paloma

AU - Lokshtanov, Daniel

PY - 2023/9/23

Y1 - 2023/9/23

N2 - 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.

AB - 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.

KW - B-coloring

KW - Clique-width

KW - Vertex cover

KW - Structural parameterization

KW - B-coloring

KW - Clique-width

KW - Vertex cover

KW - Structural parameterization

U2 - 10.1007/s00224-023-10132-0

DO - 10.1007/s00224-023-10132-0

M3 - Journal article

SN - 1432-4350

JO - Theory of Computing Systems

JF - Theory of Computing Systems

ER -

b-Coloring Parameterized by Clique-Width

Abstract

Keywords

Access to Document

Fingerprint

Cite this