A new game chromatic number (Q5961458): Difference between revisions

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.