B-chromatic number: beyond NP-hardness

DOI10.4230/LIPICS.IPEC.2015.389zbMATH Open1378.68090OpenAlexW2257542862MaRDI QIDQ5363791FDOQ5363791

Authors: Fahad Panolan, Geevarghese Philip, Saket Saurabh 

Publication date: 29 September 2017

Full work available at URL: https://doi.org/10.4230/LIPIcs.IPEC.2015.389

Recommendations

• On the parameterized complexity of b-\textsc{chromatic number}
• A complexity dichotomy for critical values of the \(b\)-chromatic number of graphs
• On approximating the b-chromatic number
• The b-chromatic number of a graph

zbMATH Keywords

exact algorithmparameterized complexity\(b\)-chromatic number

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)

Cited In (11)

• The \(b\)-chromatic index of graphs
• Harmonious coloring: parameterized algorithms and upper bounds
• \(b\)-coloring parameterized by clique-width
• Parameterized and exact algorithms for class domination coloring
• Parameterized and exact algorithms for class domination coloring
• Harmonious coloring: parameterized algorithms and upper bounds
• On the parameterized complexity of b-\textsc{chromatic number}
• On approximating the b-chromatic number
• A complexity dichotomy for critical values of the \(b\)-chromatic number of graphs
• A note on approximating the \(b\)-chromatic number
• Hybrid evolutionary algorithm for the b-chromatic number

This page was built for publication: B-chromatic number: beyond NP-hardness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5363791)