2026-07-26T00:33:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19342 2024-03-06T11:03:49Z ddc:004 open_access

Structural Parameterizations of b-Coloring Jaffke, Lars Lima, Paloma T. Sharma, Roohani b-coloring structural parameterization XNLP pathwidth neighborhood diversity twin cover 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 𝖶[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 𝖶[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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lars Jaffke and Paloma T. Lima and Roohani Sharma 2023 Is Part Of LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2023.40 urn:nbn:de:0030-drops-193429 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.40 eng https://creativecommons.org/licenses/by/4.0/legalcode