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

DOI10.1007/s00453-011-9604-4zbMath1263.05030MaRDI 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 complexity; NP-completeness; Grundy number; greedy colouring; \(b\)-colourings; online colouring

Mathematics Subject Classification ID

05C15: Coloring of graphs and hypergraphs

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

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

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