A new game chromatic number (Q5961458): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set OpenAlex properties. |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1006/eujc.1994.0071 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2056369722 / rank | |||
Normal rank |
Latest revision as of 00:39, 20 March 2024
scientific article; zbMATH DE number 980794
Language | Label | Description | Also known as |
---|---|---|---|
English | A new game chromatic number |
scientific article; zbMATH DE number 980794 |
Statements
A new game chromatic number (English)
0 references
31 August 1997
0 references
A new game chromatic number \(\chi^*_g(G)\) of a graph \(G\) is introduced. The authors first show that (i) if \(G\) is a connected bipartite graph with bipartition \((V_1,V_2)\), then \(\chi^*_g(G)= 2\) if and only if \(G\) has a vertex \(v\in V_1\) (say) such that \(N(v)= V_2\); and (ii) \(\chi^*_g(G)= \chi(G)\) (the chromatic number of \(G\)) if \(G\) is the Petersen graph or \(G\) is \(P_4\)-free. Further they show that \(\chi^*_g(T)\leq 3\) for any tree \(T\). Finally, they obtain some upper bounds and lower bounds for \(\chi^*_g(G)\), where \(G\) is a ``\(k\)-inductive'' graph.
0 references
game chromatic number
0 references
tree
0 references