Relaxed game chromatic number of graphs (Q1868839): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
(2 intermediate revisions by one other user not shown) | |||
Property / author | |||
Property / author: Wei Fan Wang / rank | |||
Property / author | |||
Property / author: Xuding Zhu / rank | |||
Property / reviewed by | |||
Property / reviewed by: Ioan Tomescu / 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
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