On the parameterized complexity of b-\textsc{chromatic number}

DOI10.1016/j.jcss.2016.09.012zbMath1353.68136OpenAlexW2531852766MaRDI QIDQ340565

Fahad Panolan, Geevarghese Philip, Saket Saurabh

Publication date: 14 November 2016

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2016.09.012

zbMATH Keywords

exact algorithmparameterized complexityb-chromatic number

Mathematics Subject Classification ID

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

Related Items (3)

Grundy Coloring and friends, half-graphs, bicliques ⋮ A complexity dichotomy for critical values of the \(b\)-chromatic number of graphs ⋮ A complexity dichotomy for critical values of the b-chromatic number of graphs

Cites Work

• Unnamed Item
• A characterization of \(b\)-chromatic and partial Grundy numbers by induced subgraphs
• Fundamentals of parameterized complexity
• On the parameterized complexity of vertex cover and edge cover with connectivity constraints
• Exact exponential algorithms.
• Exact and approximate bandwidth
• A note on the complexity of the chromatic number problem
• The b-chromatic number of a graph
• \(b\)-coloring of tight graphs
• A note on approximating the \(b\)-chromatic number
• On the Grundy and \(b\)-chromatic numbers of a graph
• Fast multiplication of large numbers
• Set Partitioning via Inclusion-Exclusion
• Reducibility among Combinatorial Problems
• B-chromatic number: Beyond NP-hardness
• Parameterized Algorithms

This page was built for publication: On the parameterized complexity of b-\textsc{chromatic number}