On the Grundy Number of a Graph

DOI10.1007/978-3-642-17493-3_17zbMath1253.68174OpenAlexW2136052264MaRDI 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-completenessfixed-parameter complexitygreedy colouringonline colouring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (5)

First-fit colorings of graphs with no cycles of a prescribed even length ⋮ Maximization coloring problems on graphs with few \(P_4\) ⋮ Minimum order of graphs with given coloring parameters ⋮ The potential of greed for independence ⋮ New potential functions for greedy independence and 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
• 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

This page was built for publication: On the Grundy Number of a Graph