Relaxed game chromatic number of graphs (Q1868839): Difference between revisions

From MaRDI portal
Added link to MaRDI item.
RedirectionBot (talk | contribs)
Removed claims
Property / author
 
Property / author: Wei Fan Wang / rank
Normal rank
 
Property / author
 
Property / author: Xuding Zhu / rank
Normal rank
 
Property / reviewed by
 
Property / reviewed by: Ioan Tomescu / rank
Normal rank
 

Revision as of 02:17, 10 February 2024

scientific article
Language Label Description Also known as
English
Relaxed game chromatic number of graphs
scientific article

    Statements

    Relaxed game chromatic number of graphs (English)
    0 references
    0 references
    28 April 2003
    0 references
    This paper discusses the following coloring game on graphs: Let \(k,d\) be non-negative integers and \(C\) a set of \(k\) colors. Two persons, A and B, alternately color the vertices of \(G\) with colors from \(C\), with A having the first move. A color \(i\) is legal for an uncolored vertex \(x\) if by coloring \(x\) with color \(i\), the subgraph of \(G\) induced by those vertices of color \(i\) has maximum degree at most \(d\). Each move of A or B colors an uncolored vertex with a legal color. The game is over if either all vertices are colored, or no more vertices can be colored with a legal color. A's goal is to produce a legal coloring which colors all the vertices of \(G\), and B's goal is to prevent this from happening. It is proved that A has a winning strategy if \(G\) is a forest for \(k=3\) and \(d\geq 1\) or \(G\) is an outerplanar graph for \(k=6\) and \(d\geq 1\).
    0 references
    relaxed game chromatic number
    0 references
    game coloring number
    0 references
    outerplanar graph
    0 references
    maximum degree
    0 references

    Identifiers