Structural Parameterizations of b-Coloring
Journal article, Peer reviewed
Published version
View/ Open
Date
2023Metadata
Show full item recordCollections
- Department of Informatics [925]
- Registrations from Cristin [9688]
Original version
Leibniz International Proceedings in Informatics. 2023, 283, 40:1-40:14. 10.4230/LIPIcs.ISAAC.2023.40Abstract
The b-Coloring problem, which given a graph G and an integer k asks whether G has a proper k-coloring such that each color class has a vertex adjacent to all color classes except its own, is known to be FPT parameterized by the vertex cover number and XP and W[1]-hard parameterized by clique-width. Its complexity when parameterized by the treewidth of the input graph remained an open problem. We settle this question by showing that b-Coloring is XNLP-complete when parameterized by the pathwidth of the input graph. Besides determining the precise parameterized complexity of this problem, this implies that b-Coloring parameterized by pathwidth is W[t]-hard for all t, and resolves the parameterized complexity of b-Coloring parameterized by treewidth. We complement this result by showing that b-Coloring is FPT when parameterized by neighborhood diversity and by twin cover, two parameters that generalize vertex cover to more dense graphs, but are incomparable to pathwidth.