A characterization of \(b\)-chromatic and partial Grundy numbers by induced subgraphs

DOI10.1016/j.disc.2016.03.011zbMath1337.05040arXiv1505.07780OpenAlexW1930585892MaRDI QIDQ284759

Olivier Togni, Nicolas Gastineau, Brice Effantin

Publication date: 18 May 2016

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

Full work available at URL: https://arxiv.org/abs/1505.07780

zbMATH Keywords

parameterized complexity\(b\)-coloringGrundy numberpartial Grundy number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (8)

On the parameterized complexity of b-\textsc{chromatic number} ⋮ On Grundy and b-chromatic number of some families of graphs: a comparative study ⋮ More results on the \(z\)-chromatic number of graphs ⋮ A new vertex coloring heuristic and corresponding chromatic number ⋮ A comparison of the Grundy and b-chromatic number of \(K_{2,t}\)-free graphs ⋮ Grundy Coloring and friends, half-graphs, bicliques ⋮ Some comparative results concerning the Grundy and \(b\)-chromatic number of graphs ⋮ A complexity dichotomy for critical values of the \(b\)-chromatic number of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bounds for the \(b\)-chromatic number of \(G-v\)
• On the \(b\)-chromatic number of regular graphs without 4-cycle
• On edge-\(b\)-critical graphs
• The b-chromatic number of cubic graphs
• Results on the Grundy chromatic number of graphs
• On minimally \(b\)-imperfect graphs
• The b-chromatic number of a graph
• On-line 3-chromatic graphs. II: Critical graphs
• \(b\)-coloring of tight graphs
• Modular representations of Loewy length two.
• \(b\)-colouring the Cartesian product of trees and some other graphs
• On the \(b\)-chromatic number of regular graphs
• On the \(b\)-coloring of \(G - e\)
• Graphs of girth at least 7 have high \(b\)-chromatic number
• On the \(b\)-continuity property of graphs
• On vertex b-critical trees
• A Characterization of b-Perfect Graphs

This page was built for publication: A characterization of \(b\)-chromatic and partial Grundy numbers by induced subgraphs