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

From MaRDI portal
Added link to MaRDI item.
Import240304020342 (talk | contribs)
Set profile property.
 
(2 intermediate revisions by one other user not shown)
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
 
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
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank

Latest revision as of 05:00, 5 March 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
    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
    0 references

    Identifiers