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

DOI10.1016/J.DAM.2022.02.025MaRDI QIDQ2127607zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

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)