Article ID Journal Published Year Pages File Type
4649829 Discrete Mathematics 2009 12 Pages PDF
Abstract

Let ff be a graph function which assigns to each graph HH a non-negative integer f(H)≤|V(H)|f(H)≤|V(H)|. The ff-game chromatic number of a graph GG is defined through a two-person game. Let XX be a set of colours. Two players, Alice and Bob, take turns colouring the vertices of GG with colours from XX. A partial colouring cc of GG is legal (with respect to graph function ff) if for any subgraph HH of GG, the sum of the number of colours used in HH and the number of uncoloured vertices of HH is at least f(H)f(H). Both Alice and Bob must colour legally (i.e., the partial colouring produced needs to be legal). The game ends if either all the vertices are coloured or there are uncoloured vertices with no legal colour. In the former case, Alice wins the game. In the latter case, Bob wins the game. The ff-game chromatic number of GG, χg(f,G)χg(f,G), is the least number of colours that the colour set XX needs to contain so that Alice has a winning strategy. Let Acy be the graph function defined as Acy(K2)=2, Acy(Cn)=3 for any n≥3n≥3 and Acy(H)=0 otherwise. Then χg(Acy,G) is called the acyclic game chromatic number of GG. In this paper, we prove that any outerplanar graph GG has acyclic game chromatic number at most 7. For any integer kk, let ϕkϕk be the graph function defined as ϕk(K2)=2ϕk(K2)=2 and ϕk(Pk)=3ϕk(Pk)=3 (PkPk is the path on kk vertices) and ϕk(H)=0ϕk(H)=0 otherwise. This paper proves that if k≥8k≥8 then for any tree TT, χg(ϕk,T)≤9χg(ϕk,T)≤9. On the other hand, if k≤6k≤6, then for any integer nn, there is a tree TT such that χg(ϕk,T)≥nχg(ϕk,T)≥n.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,