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

DOI10.1016/J.JCSS.2016.09.012MaRDI QIDQ340565zbMATH OpenOpenAlexFDO

Authors 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

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)

Recommendations

• B-chromatic number: beyond NP-hardness
• A complexity dichotomy for critical values of the \(b\)-chromatic number of graphs
• The b-chromatic number of a graph
• On the Grundy and \(b\)-chromatic numbers of a graph

Cites work

• scientific article; zbMATH DE number 1953103 (Why is no real title available?)
• A characterization of \(b\)-chromatic and partial Grundy numbers by induced subgraphs
• A note on approximating the \(b\)-chromatic number
• A note on the complexity of the chromatic number problem
• B-chromatic number: beyond NP-hardness
• Exact and approximate bandwidth
• Exact exponential algorithms.
• Fast multiplication of large numbers
• Fundamentals of parameterized complexity
• On the Grundy and \(b\)-chromatic numbers of a graph
• On the parameterized complexity of vertex cover and edge cover with connectivity constraints
• Parameterized algorithms
• Reducibility among combinatorial problems
• Set partitioning via inclusion-exclusion
• The b-chromatic number of a graph
• \(b\)-coloring of tight graphs

Cited in

(7)

• B-chromatic number: beyond NP-hardness
• Grundy Coloring and friends, half-graphs, bicliques
• On approximating the b-chromatic number
• \(b\)-coloring parameterized by clique-width
• A complexity dichotomy for critical values of the b-chromatic number of graphs
• A note on approximating the \(b\)-chromatic number
• A complexity dichotomy for critical values of the \(b\)-chromatic number of graphs

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

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