On game chromatic vertex-critical graphs

Abstract

Several games that arise from graph coloring have been introduced and studied. Let $\phi$ denote a graph invariant that arises from such a game. If $G$ is a graph and $\phi (G-x)\ne \phi (G)=k$, $k\ge 1$, holds true for every vertex $x\in V(G)$, then $G$ is called a $k$-$\phi$-game-vertex-critical graph. We study the concept of $\phi$-game-vertex-criticality for $\phi \in \{{\chi }_g,{\chi }_i,{\chi }_{ig}^A,{\chi }_{ig}^{AB}\}$, where ${\chi }_g$ denotes the standard game chromatic number, ${\chi }_i$ denotes the indicated game chromatic number and ${\chi }_{ig}^A$, ${\chi }_{ig}^{AB}$ denote two versions of the independence game chromatic number. Since the game chromatic number $\phi (G-x)$ can either decrease or increase with respect to $\phi (G)$, we distinguish between lower, upper and mixed vertex-criticality. We show that for $\phi \in \{{\chi }_g,{\chi }_{ig}^A,{\chi }_{ig}^{AB}\}$ the difference $\phi (G)-\phi (G-x)$, $x\in V(G)$, can be arbitrarily large. A characterization of $2$-$\phi$-game-vertex-critical and (connected) $3$-$\phi$-lower-game-vertex-critical graphs for all $\phi \in \{{\chi }_g,{\chi }_i,{\chi }_{ig}^A,{\chi }_{ig}^{AB}\}$ is given. It is shown that ${\chi }_g$-game-vertex-critical, ${\chi }_{ig}^A$-game-vertex-critical and ${\chi }_{ig}^{AB}$-game-vertex-critical graphs are not necessarily connected. However, it is also shown that ${\chi }_i$-lower-game-vertex-critical graphs are always connected.