On the oriented game chromatic number

MaRDI QIDQ5942568zbMATH OpenFDO

Authors J. Nešetřil, Éric Sopena

Publication date 16 October 2001

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/121694, http://www.emis.de/journals/EJC/Volume_8/Abstracts/v8i2r14.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

coloring gamesoriented graph coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Combinatorics in computer science (68R05)

Review text

The oriented graph coloring game can be seen as the game version of the oriented chromatic number of a graph. In this game, an oriented graph \(G\) and an oriented graph \(H\) are given. Players alternatingly color an uncolored vertex of \(G\) with a vertex of \(H\), such that for every arc \((v,w)\), if \(v\) is colored \(\alpha\), and \(w\) is colored \(\beta\), then \((\alpha,\beta)\) is an arc in \(H\), and every directed path of length two has its endpoints differently colored. The first player wins if the game ends with \(G\) colored; the second player wins when there are vertices that cannot be colored. The oriented game chromatic number of \(G\) is the minimum size of a graph \(H\) such that there is a winning strategy for the first player. In this paper, it is proved that the notion is well defined, that every oriented path or oriented cycle has oriented game chromatic number at most 7, which is a tight bound, that every oriented tree has oriented game chromatic number at most 19, and that outerplanar graphs have oriented game chromatic number bounded by some fixed constant.

Recommendations

• Marking games and the oriented game chromatic number of partial k-trees
• scientific article; zbMATH DE number 398953
• Competitive colorings of oriented graphs
• The game chromatic number and the game colouring number of classes of oriented cactuses
• The chromatic number of oriented graphs

Cited in

(35)

• Lightness of digraphs in surfaces and directed game chromatic number
• Colouring games on outerplanar graphs and trees
• Circular game chromatic number of graphs
• Colorings and girth of oriented planar graphs
• Marking games and the oriented game chromatic number of partial k-trees
• A simple competitive graph coloring algorithm. II.
• Majority coloring game
• A simple competitive graph coloring algorithm. III
• Game-perfect digraphs
• The game chromatic number and the game colouring number of classes of oriented cactuses
• The strong game colouring number of directed graphs
• The game Grundy number of graphs
• On game chromatic vertex-critical graphs
• Indicated coloring game on Cartesian products of graphs
• Chromatic polynomials of oriented graphs
• On the game chromatic number of splitting graphs of path and cycle
• The orthogonal colouring game
• Game colouring directed graphs
• Disproof of a conjecture of Neumann-Lara
• Refined activation strategy for the marking game
• Weak acyclic coloring and asymmetric coloring games
• Homomorphisms and colourings of oriented graphs: an updated survey
• The graph distance game and some graph operations
• The oriented path game
• Miscellaneous digraph classes
• scientific article; zbMATH DE number 5128851 (Why is no real title available?)
• Impartial coloring games
• Adapted game colouring of graphs
• Competitive colorings of oriented graphs
• On the oriented achromatic number of graphs
• The game chromatic index of wheels
• The game chromatic number and the game colouring number of cactuses
• Generalised game colouring of graphs
• Directed defective asymmetric graph coloring games
• The 6-relaxed game chromatic number of outerplanar graphs

This page was built for publication: On the oriented game chromatic number

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