Complexity of Grundy coloring and its variants
From MaRDI portal
Publication:1752449
DOI10.1016/j.dam.2017.12.022zbMath1441.05070arXiv1407.5336OpenAlexW3021022417MaRDI QIDQ1752449
Florian Sikora, Eun Jung Kim, Édouard Bonnet, Florent Foucaud
Publication date: 24 May 2018
Published in: Discrete Applied Mathematics, Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1407.5336
computational complexityexact algorithmparameterized complexityGrundy coloringconnected Grundy coloringweak Grundy coloring
Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
On the Grundy number of Cameron graphs ⋮ Grundy Distinguishes Treewidth from Pathwidth ⋮ On b-acyclic chromatic number of a graph ⋮ A new vertex coloring heuristic and corresponding chromatic number ⋮ Unnamed Item ⋮ Grundy Coloring and friends, half-graphs, bicliques ⋮ A note on connected greedy edge colouring ⋮ Complexity of Grundy coloring and its variants ⋮ Ruling out FPT algorithms for weighted coloring on forests ⋮ Connected greedy coloring of \(H\)-free graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- First-fit chromatic numbers of \(d\)-degenerate graphs
- First-fit coloring of bounded tolerance graphs
- Results on the Grundy chromatic number of graphs
- A note on first-fit coloring of interval graphs
- Some perfect coloring properties of graphs
- A note on the complexity of the chromatic number problem
- On-line 3-chromatic graphs. II: Critical graphs
- Diameter and treewidth in minor-closed graph families
- Which problems have strongly exponential complexity?
- Complexity of Grundy coloring and its variants
- On the Grundy number of graphs with few \(P_4\)'s
- On the Grundy and \(b\)-chromatic numbers of a graph
- Homomorphieeigenschaften und mittlere Kantendichte von Graphen
- Fixed-Parameter Tractability, Definability, and Model-Checking
- Known Algorithms for Edge Clique Cover are Probably Optimal
- On the equality of the grundy and ochromatic numbers of a graph
- Fourier meets M\"{o}bius: fast subset convolution
- On-line and first fit colorings of graphs
- Color-coding
- Algorithms for Vertex Partitioning Problems on Partial k-Trees
- Combinatorial bounds via measure and conquer
- Connected Greedy Colourings
- Bounding the Running Time of Algorithms for Scheduling and Packing Problems
- On cliques in graphs
