b-Coloring Parameterized by Pathwidth is XNLP-complete

09/16/2022

∙

by   Lars Jaffke, et al.

∙

0

∙

share

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.