On the Grundy Number of a Graph

DOI10.1007/978-3-642-17493-3_17zbMath1253.68174MaRDI QIDQ3058701

Leonardo Sampaio, Frédéric Havet

Publication date: 7 December 2010

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-17493-3_17

zbMATH Keywords

NP-completeness; fixed-parameter complexity; greedy colouring; online colouring

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

05C15: Coloring of graphs and hypergraphs

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

Related Items

The potential of greed for independence, First-fit colorings of graphs with no cycles of a prescribed even length, Minimum order of graphs with given coloring parameters, New potential functions for greedy independence and coloring, Maximization coloring problems on graphs with few \(P_4\)

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
• A strengthening of Brooks' theorem
• (\(\Delta-k\))-critical graphs
• Algorithms and Data Structures for Sparse Symmetric Gaussian Elimination
• 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