A complexity dichotomy for critical values of the \(b\)-chromatic number of graphs

DOI10.1016/j.tcs.2020.02.007zbMath1436.68138arXiv1811.03966OpenAlexW2970843578MaRDI QIDQ2310757

Lars Jaffke, Paloma T. Lima

Publication date: 6 April 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1811.03966

zbMATH Keywords

complexity dichotomy\(b\)-coloring\(b\)-chromatic number

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Unnamed Item
• A characterization of \(b\)-chromatic and partial Grundy numbers by induced subgraphs
• On the parameterized complexity of b-\textsc{chromatic number}
• Fundamentals of parameterized complexity
• Some simplified NP-complete graph problems
• The b-chromatic number of a graph
• \(b\)-coloring of tight graphs
• On the Grundy and \(b\)-chromatic numbers of a graph
• Graphs of girth at least 7 have high \(b\)-chromatic number
• On the \(b\)-continuity property of graphs
• Hard coloring problems in low degree planar bipartite graphs
• Filling the Complexity Gaps for Colouring Planar and Bounded Degree Graphs
• Set Partitioning via Inclusion-Exclusion
• Coloring Graphs with Constraints on Connectivity
• Reducibility among Combinatorial Problems
• A complexity dichotomy for critical values of the b-chromatic number of graphs
• Parameterized Algorithms

This page was built for publication: A complexity dichotomy for critical values of the \(b\)-chromatic number of graphs