dc.contributor.author | Jaffke, Lars | |
dc.contributor.author | Lima, Paloma Thome de | |
dc.contributor.author | Sharma, Roohani | |
dc.date.accessioned | 2024-04-17T08:13:37Z | |
dc.date.available | 2024-04-17T08:13:37Z | |
dc.date.created | 2024-01-12T13:56:23Z | |
dc.date.issued | 2023 | |
dc.identifier.issn | 1868-8969 | |
dc.identifier.uri | https://hdl.handle.net/11250/3126925 | |
dc.description.abstract | 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. | en_US |
dc.language.iso | eng | en_US |
dc.publisher | Dagstuhl Publishing | en_US |
dc.rights | Navngivelse 4.0 Internasjonal | * |
dc.rights.uri | http://creativecommons.org/licenses/by/4.0/deed.no | * |
dc.title | Structural Parameterizations of b-Coloring | en_US |
dc.type | Journal article | en_US |
dc.type | Peer reviewed | en_US |
dc.description.version | publishedVersion | en_US |
dc.rights.holder | Copyright 2023 The Author(s) | en_US |
cristin.ispublished | true | |
cristin.fulltext | original | |
cristin.qualitycode | 1 | |
dc.identifier.doi | 10.4230/LIPIcs.ISAAC.2023.40 | |
dc.identifier.cristin | 2225482 | |
dc.source.journal | Leibniz International Proceedings in Informatics | en_US |
dc.source.pagenumber | 40:1-40:14 | en_US |
dc.identifier.citation | Leibniz International Proceedings in Informatics. 2023, 283, 40:1-40:14. | en_US |
dc.source.volume | 283 | en_US |