English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
  Local TagsRelease HistoryDetailsSummary

Released
Paper

b-Coloring Parameterized by Pathwidth is XNLP-complete

MPS-Authors
/persons/resource/persons255161

Sharma,  Roohani
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

arXiv:2209.07772.pdf
(Preprint), 433KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Jaffke, L., Lima, P. T., & Sharma, R. (2022). b-Coloring Parameterized by Pathwidth is XNLP-complete. Retrieved from https://arxiv.org/abs/2209.07772.


Cite as: https://hdl.handle.net/21.11116/0000-000C-1E7E-7
Abstract
We show that the $b$-Coloring problem is complete for the class XNLP 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.