Colouring games on outerplanar graphs and trees

DOI10.1016/J.DISC.2008.09.015MaRDI QIDQ1025941zbMATH OpenOpenAlexFDO

Authors Hungyung Chang, Xuding Zhu

Publication date 23 June 2009

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

\(f\)-chromatic number\(f\)-game-chromatic numberacyclic chromatic numbercolouring gameouterplanar graphs

Mathematics Subject Classification ID

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

Review text

Let \(f\) be a function which assigns to each graph \(G\) a nonnegative integer \(f(G)\leq |V(G)|\). An \(f\) colouring of a graph \(G\) is mapping \(\varepsilon\) which assigns to each vertex of \(G\) a colour so that any subraph \(H\) of \(G\) receives at least \(f(H)\) colours. The \(f\)-chromatic number \(\chi(f, G)\) is the least number of colours used in an \(f\)-colouring of \(G\). This generalization of the chromatic number of graphs was introduced by Nešetřil and Ossona de Mendez. In the present paper the \(f\)-game chromatic number \(\chi_g(f, G)\) of a graph \(G\) is introduced in terms of a two person colouring game on graphs. \(\chi_g(f, G)\) is the least number of colours in the colour set \(X\) so that the first of the two players has a winning strategy. Moreover, the acyclic game chromatic number of a graph \(G\) is defined. It is proved that every outerplanar graph has an acyclic game chromatic number at least 7. Further results concern the game chromatic number of trees and forests.

Recommendations

• scientific article; zbMATH DE number 431513
• A bound for the game chromatic number of graphs
• Game chromatic number of outerplanar graphs
• Radius two trees specify χ‐bounded classes
• scientific article; zbMATH DE number 398953

Cites work

• A bound for the game chromatic number of graphs
• A simple competitive graph coloring algorithm
• A simple competitive graph coloring algorithm. II.
• A simple competitive graph coloring algorithm. III
• Asymmetric graph coloring games
• Colouring graphs with bounded generalized colouring number
• Competitive colorings of oriented graphs
• Excluding any graph as a minor allows a low tree-width 2-coloring
• Game chromatic number of outerplanar graphs
• Grad and classes with bounded expansion. I: Decompositions
• scientific article; zbMATH DE number 398953 (Why is no real title available?)
• scientific article; zbMATH DE number 5194465 (Why is no real title available?)
• Marking games and the oriented game chromatic number of partial k-trees
• ON THE COMPLEXITY OF SOME COLORING GAMES
• On the oriented game chromatic number
• Radius two trees specify χ‐bounded classes
• Refined activation strategy for the marking game
• Relaxed game chromatic number of graphs
• Relaxed game chromatic number of trees and outerplanar graphs
• The 6-relaxed game chromatic number of outerplanar graphs
• The game coloring number of planar graphs
• The game coloring number of pseudo partial \(k\)-trees
• The relaxed game chromatic number of outerplanar graphs
• Tree-depth, subgraph coloring and homomorphism bounds
• Very asymmetric marking games
• Weak acyclic coloring and asymmetric coloring games

Cited in

(7)

• Relaxed game chromatic number of trees and outerplanar graphs
• The game colouring number of powers of forests
• Colouring game and generalized colouring game on graphs with cut-vertices
• scientific article; zbMATH DE number 431513 (Why is no real title available?)
• Adapted game colouring of graphs
• Game chromatic number of outerplanar graphs
• Abstract colorings, games and ultrafilters

This page was built for publication: Colouring games on outerplanar graphs and trees

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