On the Nash number and the diminishing Grundy number of a graph

DOI10.1016/J.DAM.2022.02.025zbMATH Open1487.05093OpenAlexW4220817013MaRDI QIDQ2127607FDOQ2127607

Authors: Allen Ibiapina, Leonardo Rocha, Frédéric Havet 

Publication date: 20 April 2022

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2022.02.025

Recommendations

• Playing a game to bound the chromatic number
• A Game Theoretic Approach for Efficient Graph Coloring
• On the Grundy number of a graph
• The game Grundy number of graphs
• On the Grundy and \(b\)-chromatic numbers of a graph

zbMATH Keywords

game theorycomplexitycolouringcolouring parametersGrundy colouring

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43)

Cites Work

• Graph theory
• Reducibility among combinatorial problems
• Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
• Sur le coloriage des graphs
• Linear degree extractors and the inapproximability of max clique and chromatic number
• The NP-Completeness of Edge-Coloring
• Title not available (Why is that?)
• Grundy number and products of graphs
• Results on the Grundy chromatic number of graphs
• On-line and first fit colorings of graphs
• Title not available (Why is that?)
• Strategic coloring of a graph
• A Game Theoretic Approach for Efficient Graph Coloring
• On the list coloring version of Reed's conjecture
• A short proof that \(\chi\) can be bounded \(\epsilon\) away from \(\Delta + 1\) toward \(\omega\)

Cited In (1)

• On \(b\)-greedy colourings and \(z\)-colourings

This page was built for publication: On the Nash number and the diminishing Grundy number of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2127607)