$b$-Coloring Parameterized by Pathwidth is XNLP-complete

Lars Jaffke, Paloma T. Lima, Roohani Sharma

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 complexit…