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

DOI10.1016/J.JCSS.2016.09.012zbMATH Open1353.68136OpenAlexW2531852766MaRDI QIDQ340565FDOQ340565

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

Recommendations

• B-chromatic number: beyond NP-hardness
• A complexity dichotomy for critical values of the \(b\)-chromatic number of graphs
• \(b\)-coloring is NP-hard on co-bipartite graphs and polytime solvable on tree-cographs
• The b-chromatic number of a graph
• On the Grundy and \(b\)-chromatic numbers of a graph

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)

Cites Work

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

Cited In (5)

• Grundy Coloring and friends, half-graphs, bicliques
• A complexity dichotomy for critical values of the b-chromatic number of graphs
• \(b\)-coloring parameterized by clique-width
• 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)