Generalised game colouring of graphs

DOI10.1016/J.DISC.2005.11.060MaRDI QIDQ878606zbMATH OpenOpenAlexFDO

Authors Mieczysław Borowiecki, Elżbieta Sidorowicz

Publication date 26 April 2007

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2005.11.060

zbMATH Keywords

game reducible propertyGeneralised game coloringhereditary property

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Review text

There are two players, Alice and Bob, and they colour alternatively the vertices of a graph \(G\), with Alice having the first move. For a given set of hereditary properties \(\mathcal P_1,\mathcal P_2,\dots,\mathcal P_k\), the players take turns colouring \(G\) with colours from \(\{1,2,\dots,k\}\), such that for each \(i=1,2,\dots,k\) the subgraph induced by colour \(i\) has property \(\mathcal P_i\) after each move. If after \(| V(G)| \) moves the graph \(G\) is \((\mathcal P_1,\mathcal P_2,\dots,\mathcal P_k)\)-partitioned then Alice wins. In this case the graph \(G\) has property \(\mathcal P_1\square\mathcal P_2\square\cdots\square\mathcal P_k\). In the paper the class \(\mathcal O\square\mathcal O\) of graphs is characterized, where \(\mathcal O\) is the property that a graph is totally disconnected. A strategy for Alice for playing \((\mathcal O\square\mathcal O\square\mathcal O_1)\)-game on acyclic graphs (where \(\mathcal O_1\) is the property that the graph consists of isolated edges and vertices) is described.

Recommendations

• Game list colouring of graphs
• A simple competitive graph coloring algorithm. III
• A simple competitive graph coloring algorithm. II.
• Two graph-colouring games
• Colouring game and generalized colouring game on graphs with cut-vertices

Cites work

• 25 pretty graph colouring problems
• A bound for the game chromatic number of graphs
• A simple competitive graph coloring algorithm
• A survey of hereditary properties of graphs
• Game chromatic index of \(k\)-degenerate graphs
• Game chromatic number of outerplanar graphs
• scientific article; zbMATH DE number 4089545 (Why is no real title available?)
• scientific article; zbMATH DE number 398953 (Why is no real title available?)
• ON THE COMPLEXITY OF SOME COLORING GAMES
• On the oriented game chromatic number
• Radius two trees specify χ‐bounded classes
• Relaxed game chromatic number of graphs
• The game coloring number of planar graphs

Cited in

(13)

• Proper colouring painter-builder game
• On the game coloring index of \(F^+\)-decomposable graphs
• PSPACE-hardness of two graph coloring games
• The edge coloring game on trees with the number of colors greater than the game chromatic index
• Hypergraph Coloring Games and Voter Models
• Colouring game and generalized colouring game on graphs with cut-vertices
• Two graph-colouring games
• A Game Theoretic Approach for Efficient Graph Coloring
• Adapted game colouring of graphs
• Hypergraph Coloring Games and Voter Models
• Abstract colorings, games and ultrafilters
• On the relaxed colouring game and the unilateral colouring game
• Game list colouring of graphs

This page was built for publication: Generalised game colouring of graphs

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