{"ID":2828507,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.14390","arxiv_id":"2512.14390","title":"Finding $b$-colorings Using Feedback Edges","abstract":"A $b$-coloring of a graph is a proper vertex coloring such that each color class contains a vertex that sees all other colors in its neighborhood. The $b$-coloring problem, in which the task is to decide whether a graph admits a $b$-coloring with $k$ colors, is NP-complete in general but polytime solvable on trees. Moreover, it is known that $b$-coloring is in XP but W[$t$]-hard for all $t \\in \\mathbb{N}$ when parameterized by tree-width. In fact, only very few parameters, such as the vertex cover number, were known to admit an FPT algorithm for $b$-coloring. In this paper, we consider a more restrictive parameter measuring similarity to trees than tree-width, namely the feedback edge number, and show that $b$-coloring is fixed-parameter tractable under this parameterization. Our algorithm combines standard techniques used in parameterized algorithmics with the problem-specific ideas used in the polytime algorithm for trees. In addition, we present an FPT algorithm for $b$-coloring parameterized by distance to co-cluster, which is a parameter measuring similarity to complete multipartite graphs. Finally, we make several observations based on known results, including that $b$-coloring is W[$1$]-hard when parameterized by tree-depth.","short_abstract":"A $b$-coloring of a graph is a proper vertex coloring such that each color class contains a vertex that sees all other colors in its neighborhood. The $b$-coloring problem, in which the task is to decide whether a graph admits a $b$-coloring with $k$ colors, is NP-complete in general but polytime solvable on trees. Mor...","url_abs":"https://arxiv.org/abs/2512.14390","url_pdf":"https://arxiv.org/pdf/2512.14390v1","authors":"[\"Jakub Balabán\"]","published":"2025-12-16T13:28:29Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}