2020/03/09 by Lars Jaffke, Paloma T. Lima, Jaffke, Lars +3 · 4 citations
Computer Science · Engineering · Mathematics · #05C15 #05C85 #1-planar graph #Advanced Graph Theory Research #Bounded function #Brooks' theorem #Chordal graph #Clique #Clique problem #Combinatorics #Complete coloring #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #Discrete mathematics #Edge coloring #Exponential time hypothesis #F.2.2 #FOS: Computer and information sciences #Fractional coloring #G.2.2 #Graph #Graph coloring #Graph power #Indifference graph #Line graph #Mathematics #Parameterized complexity #Pathwidth #Scheduling and Optimization Algorithms #Split graph #Time complexity #Treewidth #Vertex (graph theory) #Vertex cover #acm:05C15 #acm:05C85 #cs.DM #cs.DS #msc:05C15 #msc:05C85
paper · pdf · open access · doi:10.48550/arxiv.2003.04254
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2020/03/09 · arxiv created 2022/07/19 · arxiv updated 2022/07/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We provide a polynomial-time algorithm for b-Coloring on graphs of constant clique-width. This unifies and extends nearly all previously known polynomial time results on graph classes, and answers open questions posed by Campos and Silva [Algorithmica, 2018] and Bonomo et al. [Graphs Combin., 2009]. This constitutes the first result concerning structural parameterizations of this problem. We show that the problem is FPT when parameterized by the vertex cover number on general graphs, and on chordal graphs when parameterized by the number of colors. Additionally, we observe that our algorithm for graphs of bounded clique-width can be adapted to solve the Fall Coloring problem within the same runtime bound. The running times of the clique-width based algorithms for b-Coloring and Fall Coloring are tight under the Exponential Time Hypothesis.