On the Grundy and \(b\)-chromatic numbers of a graph

DOI10.1007/S00453-011-9604-4zbMath1263.05030OpenAlexW2127573381MaRDI QIDQ1949739

Frédéric Havet, Leonardo Sampaio

Publication date: 16 May 2013

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-011-9604-4

zbMATH Keywords

fixed parameter complexityNP-completenessGrundy numbergreedy colouring\(b\)-colouringsonline colouring

Mathematics Subject Classification ID

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

Related Items (19)

On the parameterized complexity of b-\textsc{chromatic number} ⋮ On Grundy and b-chromatic number of some families of graphs: a comparative study ⋮ On the Grundy number of Cameron graphs ⋮ Grundy Distinguishes Treewidth from Pathwidth ⋮ The \(b\)-chromatic number and related topics -- a survey ⋮ Bounds for the Grundy chromatic number of graphs in terms of domination number ⋮ 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 in some subclasses of bipartite graphs and their complements ⋮ Grundy Coloring and friends, half-graphs, bicliques ⋮ On the family of \(r\)-regular graphs with Grundy number \(r+1\) ⋮ Dual parameterization of Weighted Coloring ⋮ Some comparative results concerning the Grundy and \(b\)-chromatic number of graphs ⋮ Complexity of Grundy coloring and its variants ⋮ 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 ⋮ A Reconfigurations Analogue of Brooks' Theorem and Its Consequences ⋮ Dual parameterization of weighted coloring

Cites Work

• Unnamed Item
• Unnamed Item
• Results on the Grundy chromatic number of graphs
• On an upper bound of the graph's chromatic number, depending on the graph's degree and density
• Some simplified NP-complete graph problems
• The b-chromatic number of a graph
• A strengthening of Brooks' theorem
• \(b\)-coloring of tight graphs
• (\(\Delta-k\))-critical graphs
• The NP-Completeness of Edge-Coloring
• Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
• Colouring graphs when the number of colours is nearly the maximum degree
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

This page was built for publication: On the Grundy and \(b\)-chromatic numbers of a graph