A note on approximating the \(b\)-chromatic number

DOI10.1016/J.DAM.2012.11.008zbMath1262.05051OpenAlexW2068187455MaRDI QIDQ1949121

František Galčík, Ján Katrenič

Publication date: 25 April 2013

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2012.11.008

zbMATH Keywords

approximationNP-hard\(b\)-coloring\(b\)-chromatic number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• Unnamed Item
• Unnamed Item
• The b-chromatic number of cubic graphs
• On the b-chromatic number of Kneser graphs
• On \(b\)-colorings in regular graphs
• On the b-coloring of cographs and \(P_{4}\)-sparse graphs
• The b-chromatic number of a graph
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• On approximating the b-chromatic number
• b-coloring of m-tight graphs
• b-chromatic number of cacti

Related Items (6)

On the parameterized complexity of b-\textsc{chromatic number} ⋮ The \(b\)-chromatic number and related topics -- a survey ⋮ On the \(b\)-chromatic number of Cartesian products ⋮ A matheuristic approach for the \(b\)-coloring problem using integer programming and a multi-start multi-greedy randomized metaheuristic ⋮ On the hardness of approximating the chromatic number ⋮ Additive non-approximability of chromatic number in proper minor-closed classes

This page was built for publication: A note on approximating the \(b\)-chromatic number