A new game chromatic number (Q5961458): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 02:27, 30 January 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