Game chromatic index of graphs with given restrictions on degrees

DOI10.1016/J.TCS.2008.05.026MaRDI QIDQ954995zbMATH OpenOpenAlexWikidataFDO

Authors Andrew Beveridge, Tom Bohman, Oleg Pikhurko, Alan Frieze

Publication date 18 November 2008

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2008.05.026

zbMATH Keywords

Edge coloring on graphsGame chromatic indexGames on graphsRandom strategies

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Games involving graphs (91A43)

Review text

The paper is oriented on two-person games on graphs, where players alternatively color its edges. The problem to be analyzed regards the minimal number of colors ensuring that all edges will be colored. More precisely, the minimum number of colors for which the first player has a strategy with the above properties is estimated. This number is called the game chromatic index, and the main results of the paper regard the estimation of its lower and upper bounds.

Recommendations

• A note on the game chromatic index of graphs
• Game chromatic index of \(k\)-degenerate graphs
• A new upper bound on the game chromatic index of graphs
• The game chromatic and chromatic number of some graphs
• A bound for the game chromatic number of graphs
• Game chromatic number of some network graphs
• scientific article; zbMATH DE number 398953
• The relaxed game chromatic index of k-degenerate graphs
• scientific article; zbMATH DE number 6843195
• Game chromatic number of graphs with locally bounded number of cycles

Cites work

• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• A note on the game chromatic index of graphs
• Biased positional games for which random strategies are nearly optimal
• Deterministic Graph Games and a Probabilistic Intuition
• Game chromatic index of \(k\)-degenerate graphs
• Note on the game chromatic index of trees
• Randomization, derandomization and antirandomization: Three games
• The game chromatic index of forests of maximum degree \(\Delta \geqslant 5\)
• The game chromatic number of random graphs

Cited in

(10)

• On the game coloring index of \(F^+\)-decomposable graphs
• A new upper bound on the game chromatic index of graphs
• The incidence game chromatic number of \((a,d)\)-decomposable graphs
• scientific article; zbMATH DE number 431513 (Why is no real title available?)
• Game chromatic number of graphs with locally bounded number of cycles
• scientific article; zbMATH DE number 6438421 (Why is no real title available?)
• The game chromatic index of wheels
• A biased edge coloring game
• The relaxed game chromatic index of k-degenerate graphs
• A note on the game chromatic index of graphs

This page was built for publication: Game chromatic index of graphs with given restrictions on degrees

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