The Relaxed Game Chromatic Number of Graphs with Cut-Vertices

Abstract

In the $(r,d)$-relaxed colouring game, two players, Alice and Bob alternately colour the vertices of $G$, using colours from a set $\mathcal{C}$, with $|\mathcal{C}|=r$. A vertex $v$ can be coloured with $c,c\in \mathcal{C}$ if after colouring $v$, the subgraph induced by all vertices with $c$ has maximum degree at most $d$. Alice wins the game if all vertices of the graph are coloured. The $d$-relaxed game chromatic number of $G$, denoted by $\chi _g^{(d)}(G)$, is the least number $r$ for which Alice has a winning strategy for the $(r,d)$-relaxed colouring game on $G$. A $(r,d)$-relaxed edge-colouring game is the version of the $(r,d)$-relaxed colouring game which is played on edges a graph. The parameter associated with the $(r,d)$-relaxed edge-colouring game is called the $d$-relaxed game chromatic index and denoted by $^{(d)}\chi '_g(G)$. We consider the game on graphs containing cut-vertices. For $k\ge 2$ we define a class of graphs $\mathcal{H}_k =\{G|\mathrm{\;every \;block \;of\;} G \; \mathrm{has \;at \;most}\; k \;\mathrm{vertices}\}$. We find upper bounds on the $d$-relaxed game chromatic number of graphs from $\mathcal{H}_k\;(k\ge 5)$. Since the line graph of the forest with maximum degree $k$ belongs to $\mathcal{H}_k$, from results for $\mathcal{H}_k$ we obtain some new results for line graphs of forests, i.e., for the relaxed game chromatic index of forests. We prove that $^{(d)}\chi '_g(T)\le \Delta (T)+2-d$ for any forest $T$. Moreover, we show that for forests with large maximum degree we can derive better bounds. These results improve the upper bound on the relaxed game chromatic index of forests obtained in Dunn (Discrete Math 307:1767–1775, 2007). Furthermore, we determine minimum $d$ that guarantee Alice to win the $(2,d)$-relaxed edge-colouring game on forests.

1 Introduction

Let $G$ be a graph, $d\ge 0$ be an integer and $\mathcal{C}$ be a set of $r$ colours. We consider the $(r,d)$-relaxed colouring game defined as follows. Two players, Alice and Bob alternately colour the vertices of $G$, using colours from the set $\mathcal{C}$. Alice has the first move. A vertex $v$ can be coloured with $c,c\in \mathcal{C}$ if after colouring $v$ with $c$, the subgraph induced by all vertices with $c$ has maximum degree at most $d$. Alice wins the game if all vertices of the graph are coloured, otherwise, Bob wins. The $d$-relaxed game chromatic number, denoted by $\chi _g^{(d)}(G)$, is the least $r$ for which Alice has a winning strategy for the $(r,d)$-relaxed colouring game on $G$. If $d=0$, then the parameter is called the game chromatic number of $G$ and is denoted by $\chi _g(G)$. For a class of graphs $\mathcal{G}$, let $\chi _g^{(d)}(\mathcal{G})=\mathrm{max}\{\chi _g^{(d)}(G):G\in \mathcal{G}\}$. The $(r,d)$-relaxed edge-colouring game is the version of the $(r,d)$-relaxed colouring game which is played on the edge set of the graph $G$ rather than the vertex set $G$. The parameter associated with the $(r,d)$-relaxed edge-colouring game is called the $d$-relaxed game chromatic index and denoted by $^{(d)}\chi '_g(G)$.

The concept of the relaxed game chromatic number was introduced by Chou et al. [2]. Since then, the game chromatic number of various classes of graphs has been studied. In particular, Dunn and Kierstead [4] showed that $\chi _g^{(d)}(G)\le k+1$ for all $d\le 4k-1$, if $G$ is a partial $k$-tree; $\chi _g^{(d)}(G)\le 6$ for all $d\ge 93$, if $G$ is a planar graph. In [5], it was shown that $\chi _g^{(d)}(G)\le 3$ for all $d\ge 132$, if $G$ is a planar graph.

The results for outerplanar graphs proved in the series of papers [2, 7, 8, 11] can be expressed in the following formula.

Theorem 1

([2, 7, 8, 11]) Let $G$ be an outerplanar graph. Then $\chi _g^{(d)}(G)\le 7-d$ for $d\in \{0,1,2,3,4\}$.

The similar uniform formula for forests was proved in series of papers [2, 6, 8].

Theorem 2

([2, 6, 8]) Let $T$ be a forest. Then $\chi _g^{(d)}(T)\le 4-d$ for $d\in \{0,1,2\}$.

In this paper we exhibit a similar formula for the relaxed game colouring index of a forest and the game chromatic number of a special class. For a forest $T$ we prove that $^{(d)}\chi '_g(T)\le \Delta (T)+2-d$ for $d\in \{0,\ldots ,\Delta (T)-1\}$. Moreover, we show that this upper bound can be improved for the forests with large maximum degree. We also find such a formula for the class of graphs $\mathcal{H}_k$, which contains, e.g., forests, line graphs of forests, cactus graphs, Husimi trees.

A block $B$ of a graph $G$ is a maximal subgraph of $G$ that does not contain any cut-vertex. For $k\ge 2$, let

$$\begin{aligned} \mathcal{H}_k =\{G|\mathrm{\;every \;block \;of\;} G \mathrm{\;has \;at \;most}\; k \;\mathrm{vertices}\}. \end{aligned}$$

Since $\mathcal{H}_k$ contains many well-known classes of graphs, it is worth studying. For example $\mathcal{H}_2$, is the class of forests. If $G\in \mathcal{H}_k$ and every block is a complete graph, then $G$ is a Husimi tree. If $G\in \mathcal{H}_k$ and every block is a cycle or $K_2$, then $G$ is a cactus graph. The class $\mathcal{H}_k$ is also interesting because it contains line graphs of forests. If every block of $G\in \mathcal{H}_k$ is a complete graph and every vertex of $G$ is in at most two blocks, then $G$ is the line graph of a forest.

The relaxed colouring game on graphs from $\mathcal{H}_k$ was studied in [9, 10] and the following result was proven:

Theorem 3

([10]) For $k=3,4$ and $0\le d\le k-1$ it holds that $\chi _g^{(d)}(\mathcal{H}_k)\le k+2-d$.

In this paper we generalized this formula for all $k$. The results that we obtain for the relaxed game chromatic index of forest follow from the results for $\mathcal{H}_k$.

It is well-known that the relaxed game chromatic number is not monotone which often causes difficulties in proofs. In this paper as a tool for determining the relaxed chromatic number we use the other invariant (that is monotone)—the unilateral game chromatic number, which was introduced in [10]. It is also defined as two person game—the unilateral colouring game. In Sect. 2 we give the definition of the unilateral colouring game and the unilateral game chromatic number. Next, we give the properties of the unilateral game chromatic number and describe Alice’s winning strategy for this game. In Sect. 3 we introduce the notation that we use in the next sections. In Section 4 we study the game on graphs from $\mathcal{H}_4$. The main result of the paper we give in Sect. 5, we determine an upper bound on the unilateral game chromatic number of $\mathcal{H}_k$ for $k\ge 5$, upper bounds on the relaxed game chromatic number are consequences of this result. In Sect. 6 we give upper bounds on the relaxed game chromatic index of forests. These results improve upper bounds obtained by Dunn in [3]. Most results of Sect. 6 are immediate consequences of the results from Sects. 4 and 5. However, in Sect. 6 we prove the theorem determining minimum $d$ that guarantees Alice to win the $(2,d)$-relaxed edge-colouring game on forests.

2 Unilateral colouring game

The definitions of the unilateral $\mathcal{P}$-colouring game and the $\mathcal{P}$-unilateral game chromatic number for any hereditary property $\mathcal{P}$ were introduced in [10]. In this paper we focus on the unilateral $\mathcal{P}$-colouring when $\mathcal{P}$ is the class of graphs with bounded maximum degree. Let $\mathcal{S}_d$ denote the class of graphs with maximum degree at most $d$. Thus, we consider the unilateral $\mathcal{S}_d$-colouring game. Before we give the formal definition of the unilateral $\mathcal{S}_d$-colouring game we need one more definition. The colour $c$ is called $d$-admissible for $v$ if

• 1. $v$ has at most $d$ neighbours that are coloured with the colour $c$,

• 2. if $w$ is a neighbor of $v$ coloured with $c$, then $w$ has at most $d-1$ neighbours that are coloured with $c$.

Let be given a graph $G$, $d\ge 0$ be an integer and a set $\mathcal{C}$ of $r$ colours. Two players, Alice and Bob colour vertices of $G$. Alice starts the game. The players play alternately, but Bob is allowed to pass. In addition, Bob is allowed to use any colour from $\mathcal{C}$ (not necessarily $d$-admissible) for colouring a vertex, while Alice must colour a vertex with a $d$-admissible colour from $\mathcal{C}$. If after $|V(G)|$ moves the vertices of $G$ are all coloured, then Alice wins the game, otherwise Bob wins. Thus, Bob wins the game if after a move of some player there is an uncoloured vertex $v$ for which there is no $d$-admissible colour. The above game is called the unilateral $\mathcal{S}_d$-colouring game. The $\mathcal{S}_d$-unilateral game chromatic number, denoted by $\chi _{ug}^{(d)}(G)$, is the least number $r$ such that Alice has a winning strategy, when playing the unilateral $\mathcal{S}_d$-colouring game with $r$ colours on $G$.

The unilateral $\mathcal{S}_d$-colouring game with $r$ colours is a version of the $(r,d)$-relaxed colouring game in which Bob is more powerful than Alice. This implies that the $\mathcal{S}_d$-unilateral game chromatic number is an upper bound on the $d$-relaxed game chromatic number.

Lemma 1

([10]) For any graph $G$, it holds $\chi _{g}^{(d)}(G)\le \chi _{ug}^{(d)}(G)$.

Moreover, in [10] the following monotone properties of the $\mathcal{S}_d$-unilateral game chromatic number and the $\mathcal{P}$-unilateral game chromatic number were proved:

Lemma 2

([10]) Let $d\ge 1$. Then $\chi _{ug}^{(t)}(G)\le \chi _{ug}^{(d)}(G)$ for every $t\ge d$.

Lemma 3

([10]) If $G'$ is a subgraph of $G$, then $\chi _{ug}^{(d)}(G')\le \chi _{ug}^{(d)}(G)$.

Lemma 4

([10]) If Alice has a winning strategy for the unilateral $\mathcal{S}_d$-colouring game on $G$ with $r$ colours, then she also has a winning strategy for the unilateral $\mathcal{S}_d$-colouring game on $G$ with $t$ colours for any $t\ge r$.

From Lemmas 1 and 2 it follows:

Lemma 5

([10]) Let $d\ge 1$. Then $\chi _{g}^{(t)}(G)\le \chi _{ug}^{(d)}(G)$ for every $t\ge d$.

Now, we describe the winning strategy for Alice to play the unilateral $\mathcal{S}_d$-colouring game. Briefly, in the winning strategy Alice creates a family of partially coloured graphs containing the uncoloured graph $G$ and next she plays in such a way that each time after her move the resulting graph belongs to this family. To be more precise, let $G$ be a graph, $S\subseteq V(G)$ and $|\mathcal{C}|=r$. A partial $r$-colouring of $G$ is a function $c_r:S\rightarrow \mathcal{C}$. The pair $(G,c_r)$ is called a partially $r$-coloured graph. If the vertices of the graph are all uncoloured or the vertices of the graph are all coloured, then we also say that the graph is partially $r$-coloured.

Let $\gamma (G)$ be a family of partially $r$-coloured graphs $(G,c_r)$.

Definition 1

($(\mathcal{S}_d,r)$-game closed family) The family $\gamma (G)$ is $(\mathcal{S}_d,r)$-game closed if for every graph $(G,c_r)\in \gamma (G)$ the following conditions hold:

• (i) If $(G,c_r)$ has uncoloured vertices, then there is a vertex that can be coloured by Alice with a $d$-admissible colour from $\mathcal{C}$ in such a way that the resulting graph $(G,c'_r)$ is in $\gamma (G)$. and

• (ii) If Bob colours a vertex of $(G,c_r)$ with an arbitrary colour $c,\;c\in \mathcal{C}$ and after his move there are still uncoloured vertices, then there is a vertex that can be coloured by Alice with a $d$-admissible colour from $C$ in such a way that the resulting graph $(G,c''_r)$ is in $\gamma (G)$.

Definition 2

$((G;\mathcal{S}_d,r)$-strategy)

• (1) Alice creates an $(\mathcal{S}_d,r)$-game closed family $\gamma (G)$ containing the uncoloured graph $G$.

• (2) Alice plays in such a way that each time after her move the resulting graph $(G,c_r)$ belongs to $\gamma (G)$.

Remark 1

The $(G;\mathcal{S}_d,r)$-strategy exists if and only if the $(\mathcal{S}_d,r)$-game closed family containing the uncoloured $G$ exists.

Theorem 4

([10]) Let $\gamma (G)$ be an $(\mathcal{S}_d,r)$-game closed family and $G\in \gamma (G)$. Assume that Alice and Bob play the unilateral $\mathcal{S}_d$-colouring game with $r$ colours on $G$. If Alice uses the $(G;\mathcal{S}_d,r)$-strategy, then she wins the game.

3 Notation

Let $G\in \mathcal{H}_k$ and $G$ be a connected partially $r$-coloured graph. Recall that $G\in \mathcal{H}_k$ if every block of $G$ has at most $k$ vertices.

Let $u\in V(G)$. Each component of $G-u$ is called a stem of $u$. A coloured stem of $u$ is a stem of $u$ that has at least one coloured vertex. If the vertices of a stem are all uncoloured, then the stem is called an uncoloured. A graph with a monochromatic center is a graph with at least one coloured vertex in which a maximal connected monochromatic subgraph is fixed. This fixed connected monochromatic subgraph is called the monochromatic center of the graph.

Example 1

Let $G$ be a partially 3-coloured graph (see Fig. 1). Each maximal connected monochromatic subgraph of $G$ can be a monochromatic center of $G$. Thus, we can choose a subgraph induced by one of the sets: $\{3,4,5\}$, $\{9,10\}$ or $\{26\}$ to be a monochromatic center of $G$.

Fig. 1

The partially 3-coloured graph G in Example 1

The next definitions concern graphs with monochromatic centers. Let $S$ be a monochromatic center of $G$. Let $B$ be a block of $G$ with at most one vertex in $S$. If the block $B$ has exactly one vertex in $S$, then a block-cut-vertex of $B$ is the vertex in $B\cap S$, otherwise a block-cut-vertex of $B$ is a vertex $w\in B$ such that in the graph $G-w$ vertices of $S$ and the remaining vertices of $B$ are in distinct components. If a block has more than one vertex in $S$, then it has no block-cut-vertex. Let $v\in V(G){\setminus } S$. The back-stem of $v$ is the stem of $v$ containing $S$. A front-stem of $v$ is a stem of $v$ that does not contain $S$. The back-block of $v$, denoted by $B_b(v)$, is the block containing $v$ and vertices of the back-stem of $v$. Note that every vertex has exactly one back-block (back-stem). Let $B_b'(v)=B_b(v){\setminus } T$, where $T$ is the block-cut-vertex of $B_b(v)$ or $S$ whenever $B_b(v)$ has no block-cut-vertex. A front-block of $v$ is a block containing $v$ and vertices of a front-stem of $v$. The family of all front-blocks of $v$ we denote by $\mathcal{B}_f(v)$. The vertex $v$ is the block-cut-vertex of every block from $\mathcal{B}_f(v)$. A back-neighbor (front-neighbor) of $v$ is a neighbor of $v$ belonging to the back-block (a front-block) of $v$. The set of vertices that are front-neighbours (back-neighbours) of $v$ we denote by $N_f(v)\; (N_b(v))$, respectively.

The vertices $v$ and $u$ are similar if they are coloured and $c(v)=c(u)$. In the proofs the vertices that have similar front-neighbours play an important role. Let $A,\; A\cap S=\emptyset$ be the set of coloured vertices, by $N^s_f(A)$ we denote the set of similar front-neighbours of $A$, i.e., $N^s_f(A)=\cup _{x\in A} \{y:y\in N_f(x)\;\mathrm{and}\;c(y)=c(x)\}$ and $N^s_f[A]=N^s_f(A)\cup A$.

Example 2

Let $G$ be a partially 3-coloured graph with the monochromatic center $S=\{3,4,5\}$ (see Fig. 1). The block $\{1,2,3,4\}$ has no block-cut-vertex, since it contains two vertices of $S$, similarly the block $\{4,5,6,7\}$. All other blocks have block-cut-vertices. For example, for the block $\{3,19,20,21\}$ vertex 3 is the block-cut-vertex, vertex 1 is the block-cut-vertex of $\{1,24,25,26\}$, vertex 11 is the block-cut-vertex of two blocks: $\{11,12,13\}$ and $\{11,16,17,18\}$. Vertex 1 has exactly one front-stem $\{24,\ldots ,31\}$ and exactly one back-stem $\{2,\ldots , 23\}$. $B_b(1)=\{1,2,3,4\}$ is the back-block of 1. $B_b(1)$ has no cut-block-vertex and hence $B'_b(1)=\{1,2\}$. Vertex 1 has the exactly one front-block $\mathcal{B}_f(1)=\{1,24,25,26\}$. Vertex 29 has one front-stem $\{30,31\}$, the remaining vertices of $G-\{29\}$ form the back-stem of 29. $B_b(29)=\{26,27,28,29\}$ is the back-block of 29, the block-cut-vertex of $B_b(29)$ is vertex 26 and $B'_b(29)=\{27,28,29\}$. Vertex 11 has two front-stems: $\{16,17,18\}$ and $\{12,13,14,15\}$, the remaining vertices of $G-\{11\}$ form the back-stem of 11. $B_b(11)=\{2,9,10,11\}$ is the back-block of 11 and $B'_b(11)=\{9,10,11\}$. Vertex 18 has neither a front-stem nor a front-block. All vertices of $G-\{18\}$ form the back-stem and hence $B_b(18)=\{11,16,17,18\}$, $B'_b(18)=\{16,17,18\}$.

4 The relaxed game chromatic number of $\mathcal{H}_4$

In this section we prove the following theorem:

Theorem 5

If $d\ge 1$, then $\chi _{g}^{(d)}(\mathcal{H}_4)\le 4$.

To prove the upper bound on $\chi _{g}^{(d)}(\mathcal{H}_4)$, we consider the unilateral $\mathcal{S}_1$-colouring game on graphs from $\mathcal{H}_4$. The crucial point of the proof is to construct the game closed family. Since the unilateral game chromatic number is monotone under taking subgraphs (by Lemma 3), we consider only connected graphs such that each block is isomorphic to $K_4$.

Let $G\in \mathcal{H}_4$ and $G$ be a connected graph such that each block of $G$ is isomorphic to $K_4$.

Definition 3

(Family $\alpha _4^1(G)$) The family $\alpha _4^1(G)$ contains the uncoloured graph $G$ and the partially $4$-coloured graphs $(G,c_4)$ with monochromatic center $S$ such that every uncoloured vertex $u$ has one of the following properties:

• (1) $u$ has exactly one coloured stem, or

• (2) $u$ has exactly two coloured stems and

  • (a) in $\mathcal{B}_f(u){\setminus } \{u\}$ there is exactly one vertex $v$ not having the property (1) (i.e., $v$ is uncoloured and has two coloured stems or $v$ is coloured), moreover, if the vertex $v$ is coloured, then it has no similar front-neighbor;

  • (b) in $B'_b(u){\setminus } \{u\}$ there is at most one vertex $x$ such that

    • $x$ is uncoloured and has two coloured stems, or

    • $x$ is coloured and has one similar front-neighbor.

The following example illustrates Definition 3 and the idea of the proof of Lemma 6.

Example 3

To prove that the family $\alpha _4^1(G)$ is $(\mathcal{S}_1,4)$-game closed we must show that Conditions (i) and (ii) of Definition 1 hold. In the other words, for each $(G,c_4)\in \alpha _4^1 (G)$ we must prove that Alice can colour a vertex of $(G,c_4)$ in such a way that after her move each uncoloured vertex of the resulting graph has either the property (1) or (2) of Definition 3 and if Bob colours a vertex of $(G,c_4)$ and after his move there are uncoloured vertices, then there is a vertex that can be coloured by Alice in such a way that the resulting graph belongs to $\alpha _4^1(G)$. Let $G$ be an uncoloured graph isomorphic to the graph in Fig. 2. Observe that a partially 4-coloured graph $(G,c_4)$ (see Fig. 2) belongs to $\alpha _4^1(G)$: let us choose the vertices $\{s_1,s_2,s_3,s_4\}$ to be the monochromatic center $S$, then all uncoloured vertices have either the property (1) or (2); the vertices $\{u_3,u_4,u_5,u_6\}$ have the property (2), the remaining uncoloured vertices have the property (1). Alice can colour vertex $u_1$ with 4, then the resulting graph is in $\alpha _1^4(G)$, so for $(G,c_4)$ the condition (i) of Definition 1 holds. Now, we consider some possible moves of Bob. Suppose that Bob colours vertex $b_1$ with any colour. Thus, he destroys the property (1) of $u_1$ and $u_2$. However, now vertex $u_2$ has the property (2) while vertex $u_1$ has neither the property (1) nor (2), since $u_1$ has two coloured stems and in $B'_b(u_1)$ there are two vertices $x_1,x_3$ with similar front-neighbours. Then, Alice colours $u_1$ with colour 4. Suppose that Bob colours $b_2$ with 2. Now, $u_4$ has neither the property (1) nor (2) because it has three coloured stems. Observe that $u_3$ still has the property (2). If Alice coloured $u_4$ with either 2 or 4, then she would destroy the property (2) of $u_3$. Thus, Alice must colour $u_4$ with a colour distinct from 2 and 4. Suppose that Bob colours $b_3$ with 2, so he destroys the property (2) of $u_5$. Alice colours $u_5$ with a colour distinct from 2 and 4.

Fig. 2

The partially 4-coloured graph G in Example 3

Remark 2

Suppose that in her strategy Alice has to colour a vertex $u$ such that the block-cut-vertex $w$ of $B_b(u)$ is coloured. Suppose that Alice colours $u$ with colour $c(w)$. If $B_b(u)$ had had the uncoloured vertex having the property (2), then Alice would have destroyed this property. To avoid such a circumstance Alice never colours $u$ with colour $c(w)$.

Lemma 6

The family $\alpha _4^1(G)$ is $(\mathcal{S}_1,4)$-game closed.

Proof

Let $G\in \alpha _4^1(G)$. We show that Conditions (i) and (ii) of Definition 1 hold. Assume that Alice starts. If the vertices of $G$ are all uncoloured, then Alice colours an arbitrary vertex. Thus, after Alice’s move the coloured vertex is the monochromatic center $S$ and every uncoloured vertex of $G$ satisfies either the property (1) or the property (2). Suppose that $G$ has at least one coloured vertex. Thus, $G$ has the monochromatic center $S$ such that every uncoloured vertex of $G$ with $S$ satisfies either the property (1) or the property (2). We show that Alice can colour a vertex in such a way that every uncoloured vertex of the resulting graph with the same monochromatic center $S$ has the property (1) or the property (2). Let $B$ be a block that contains at least one uncoloured vertex and such that $B$ has the coloured block-cut-vertex $w$ or $B$ has no block-cut-vertex. Let $c_s=c(w)$ or $c_s=c(S)$, whenever $B$ has no block-cut-vertex. Suppose that in $B$ there is an uncoloured vertex $u$ with the property (1). Thus, Alice colours $u$ with a colour $c$ such that $c\notin c(N(u))$. Observe that such a colour $c$ is admissible for $u$. Since all coloured neighbours of $u$ are in $B$ and in $B$ there are at most $3$ coloured vertices, such a colour $c$ exists. Observe that the vertex $u$ affects only on the property of uncoloured vertices of $B$ and $B_b(w)$ (whenever $B$ has the block-cut-vertex $w$). Since Alice uses a colour distinct from the colours of the neighbours of $u$, after Alice’s move all uncoloured vertices have the same property as they had had before Bob’s move. If in $B$ there is no vertex with the property (1), then Alice colours a vertex $u$ with the property (2). Suppose that in $B{\setminus } \{u\}$ there are uncoloured vertices. By our assumption all uncoloured vertices of $B$ have the property (2), it follows that in $B{\setminus } \{u\}$ there is at most one uncoloured vertex. Then Alice colours $u$ with colour $c$ such that $c\notin c(N(u))$. Such a colour $c$ exists, since $u$ has at most $2$ coloured neighbours in $B$ (back-neighbours) and at most one coloured neighbor in $\mathcal{B}_f(u)$ (a front-neighbor). After Alice’s move all vertices that had had the property (1) before Alice’s move, still have the property (1) after her move and all vertices that had had the property (2) still have the property (2). This implies that the resulting graph is in $\alpha _4^1(G))$. Suppose that all vertices in $B{\setminus } \{u\}$ are coloured. Then, Alice colours $u$ with any admissible colour $c$ distinct from $c_s$. Observe that $u$ has at most $4$ coloured neighbours. Moreover, in $B'_b(u)$ there is at most one coloured vertex with the similar front-neighbor and in $\mathcal{B}_f(u)$ there is no vertex with the similar front-neighbor, from these we conclude that the colour $c$ exists. The vertex $u$ affects only the property of the uncoloured vertices in $B_b(w)$. Since Alice colours $u$ with the colour distinct from $c_s$, after her move $w$ has no similar front-neighbor. Thus, after Alice’s move all uncoloured vertices have the same property (either the property (1) or the property (2)) as they had had before Alice’s move.

Now, we consider the case when Bob starts. If after his move $G\in \alpha _4^1(G)$, then obviously Alice can colour a vertex in such a way that also after her move $G$ is in $\alpha _4^1(G)$. Thus, assume that after Bob’s move $G\notin \alpha _4^1(G)$. Before Bob’s move every uncoloured vertex of $G$ with the monochromatic center $S$ had satisfied either the property (1) or the property (2), we show that after Bob’s move Alice can colour a vertex in such a way that again every uncoloured vertex of the resulting graph with the same monochromatic center $S$ has the property (1) or the property (2). Assume that after Bob’s move a vertex $u$ has neither the property (1) nor (2). We consider two cases regarding the property of $u$ before Bob’s move.

Case 1 $u$ had the property (1).

Thus, Bob has coloured the vertex $b$ of an uncoloured front-stem of $u$. Since $u$ does not have the property (2), it follows that in $B'_b(u){\setminus }\{u\}$ there are

• two vertices with two coloured stems, or

• one uncoloured vertex with two coloured stems and one coloured vertex with a similar front-neighbor, or

• $|N_f^s(B'_b(u)\cap C)|\ge 2$.

Arguments above imply that the block-cut-vertex $w$ of $B_b(u)$ is coloured or does not exist. Let $c_s=c(B_b(u)-B'_b(u))$. First, suppose that in $B_b(u)$ there is an uncoloured vertex. Alice colours $u$ with a colour $c$ such that $c\notin c(N(u))$. The vertex $u$ affects only properties of uncoloured vertices in $B_b(u)$ and $B_b(w)$. After Alice’s move $u$ has no similar front-neighbor. Furthermore, if the block-cut-vertex $w$ of $B_b(u)$ exists, then $c(u)\ne c(w)$ and hence the vertices in $B_b(u)$ and $B_b(w)$ that had had the property (2) still have the property (2). Hence, all uncoloured vertices have the same property as they had had before Bob’s move. Now, suppose that the vertices of $B_b(u)$ are all coloured. Then Alice colours $u$ with an admissible colour distinct from $c_s$. Since there is at most one coloured vertex in $B_f(u)$ and it does not have any similar neighbor, the admissible colour $c$ for $u$ exists. Again after such a move all uncoloured vertices have the same property as they had had before Bob’s move.

Case 2 $u$ had the property (2).

Let us consider the following subcases:

Subcase 2.1 $u$ has three coloured stems.

Thus, Bob has coloured a vertex $b$ of an uncoloured front-stem of $u$. First assume that $B_b(u)$ has the uncoloured block-cut-vertex $w$. This assumption implies that each vertex of $B'_b(u){\setminus } \{u\}$ is uncoloured and has the property (1). Alice colours $u$ with a colour $c$ such that $c\notin c(N(u))$. After such a move $w$ still has the property (2), each vertex of $B'_b(u){\setminus } \{u\}$ has the property (1) and hence the resulting graph is in $\alpha _4^1(G)$. Assume that $B_b(u)$ has the coloured block-cut-vertex $w$ or has no block-cut-vertex. Let $c_s=c(B_b(u)-B'_b(u))$. In this case at most one coloured vertex of $B'_b(u)$ has a similar front neighbor. Alice colours $u$ with any admissible colour $c$ distinct from $c_s$. Observe that such a colour $c$ exists: $u$ has at most 4 neighbours with colour distinct from $c_s$ (two back-neighbours and two front-neighbours) and at most one of them (one of back-neighbours) has a similar front-neighbor, since Alice can use three colours, one of them must be admissible for $u$. After such a move the resulting graph is in $\alpha _4^1(G)$.

Subcase 2.2 In $\mathcal{B}_f(u){\setminus } \{u\}$ there are two vertices not having the property (1) or there is a vertex with a similar front-neighbor.

Thus, Bob has coloured the vertex $b$ belonging to a front-stem of $u$. Since we are not in Subcase 2.1 we may assume that $u$ has one coloured front-stem. Let $B_f(u)$ be the front-block belonging to the coloured front-stem. Since before Bob’s move the graph was in $\alpha _4^1(G)$, it follows that in $B_f(u)$:

• there are two coloured vertices, or

• there are two uncoloured vertices with the property (2), or

• there is one coloured vertex and one uncoloured vertex with the property (2), or

• there is one coloured vertex with a similar neighbor.

First, assume that $B_b(u)$ has the uncoloured block-cut-vertex $w$. Hence, each vertex of $B_b(u)$ is uncoloured. Alice colours $u$ with a colour $c,\;c\notin c(N(u))$. Assume that $B_b(u)$ has the coloured block-cut-vertex $w$ or has no block-cut-vertex. Let $c_s=c(B_b(u)-B'_b(u))$. Alice colours $u$ with an admissible colour distinct from $c_s$. Since at most one coloured vertex of $B'_b(u)$ has a similar front-neighbor and Alice can use three colours, it follows that Alice can find an admissible colour for $u$ distinct from $c_s$.

Subcase 2.3 In $B'_b(u){\setminus } \{u\}$ there are two uncoloured vertices with two coloured stems.

Thus, the vertices of $B'_b(u)$ are all uncoloured and have two coloured stems. Before Bob’s move in $B'_b(u)$ there had been two uncoloured vertices with two coloured stems, this implies that the block-cut-vertex $w$ of $B_b(u)$ is coloured or does not exist. Hence $u$ has at most two coloured neighbours. Alice colours $u$ with a colour $c$ such that $c\notin c(N(u))$. After her move $u$ has no similar front-neighbor and hence any vertex of $B'_b(u)$ with two coloured stems has the property (2).

Subcase 2.4 $|N_f^s(B'_b(u)\cap C)|=2$.

Thus, before Bob’s move in $B'_b(u)$ there had been a coloured vertex with a similar front neighbor. This implies that the block-cut-vertex $w$ of $B_b(u)$ is coloured or does not exist, and each uncoloured vertex of $B_b(u)$ has the property (1). Let $c_s=c(B_b(u)-B'_b(u))$. Alice colours $u$ with an admissible colour $c$ such that $c\ne c_s$.

Subcase 2.5 In $B'_b(u){\setminus } \{u\}$ there is a coloured vertex with a similar front-neighbor and an uncoloured vertex with two coloured stems.

Note that also in this case the block-cut-vertex $w$ of $B_b(u)$ is coloured or does not exist. Alice colours $u$ with a colour $c$ such that $c\notin c(N(u))$. Since $u$ has at most $3$ coloured neighbours, such a colour exists. $\square$

Theorem 6

Let $G\in \mathcal{H}_4$. Then $\chi _{ug}^{(1)}(G)\le 4$.

Proof

Let $G\in \mathcal{H}_4$. Let $G'$ be a connected graph such that each block of $G'$ is $K_4$ and $G\subseteq G'$. Lemma 6 implies that there exists an $(\mathcal{S}_1,4)$-game closed family containing $G'$. Thus, Alice has a winning strategy for the unilateral $\mathcal{S}_1$-game on $G'$ with $4$ colours, she can play in such a way that after her move the partially $4$-coloured graph $G'$ always belongs to $\alpha _4^1(G')$. Thus, $\chi _{ug}^{1}(G')\le 4$. Furthermore, by Lemma 3 $\chi _{ug}^{(1)}(G)\le 4$. $\square$

From Theorem 6, Lemmas 1 and 5 it immediately follows the proof of Theorem 5.

5 The relaxed game chromatic number of $\mathcal{H}_k$

In this section we consider the game on graphs from $\mathcal{H}_k$ where $k\ge 5$. The main result is the following theorem:

Theorem 7

Let $k\ge 5,\; 1\le d\le k-2$. Then $\chi _{g}^{(d)}(\mathcal{H}_k)\le k+1-d$.

Similarly as in the previous section we use the $\mathcal{S}_d$-unilateral game chromatic number, i.e., we prove that $\chi _{ug}^{(d)}(\mathcal{H}_k)\le k+1-d$ for $k\ge 5,\; 1\le d\le k-2$. At the end of the section we give some corollaries that combine this result with known results for $\mathcal{H}_k$.

First, we construct the game closed family. Since the unilateral game chromatic number is monotone, we can focus only on connected graphs such that each block is isomorphic to $K_k$.

Let $k\ge 5,\;r\le k,\;G\in \mathcal{H}_k$ and $G$ be a connected graph such that each block of $G$ is isomorphic to $K_k$.

Definition 4

(Family $\alpha _{k,r}^d(G)$) The family $\alpha _{k,r}^d(G)$ contains the uncoloured graph $G$ and the partially $r$-coloured graphs $(G,c_r)$ with monochromatic center $S$ such that each uncoloured vertex $u$ has one of the following properties:

• (1) $u$ has exactly one coloured stem and

  $$\begin{aligned} |N_f^s(B'_b(u)\cap C)|\le |B'_b(u)\cap C|, \qquad (*) \end{aligned}$$

  where $C$ is the set of coloured vertices of $(G,c_r)$

• (2) $u$ has exactly two coloured stems and

  • (a) in $\mathcal{B}_f(u){\setminus } \{u\}$ there is exactly one vertex $v$ not having the property (1), moreover, if the vertex $v$ is coloured, then it has no similar front-neighbor;

  • (b) in $B'_b(u){\setminus } \{u\}$ there is at most one vertex $x$ such that

    • $x$ is uncoloured and has two coloured stems, or

    • $x$ is coloured and has one similar front-neighbor.

Lemma 7

Let $k\ge 5,\; 1\le d\le k-2$. If $r=k+1-d$, then the family $\alpha _{k,r}^d(G)$ is $(\mathcal{S}_d,r)$-game closed.

Proof

Let $G\in \alpha _{k,r}^d(G)$. Observe that by our assumptions the players use at least three colours, i.e., $r\ge 3$ . We must show that Conditions (i) and (ii) of Definition 1 hold. Assume that Alice starts. If the vertices of $G$ are all uncoloured, then Alice colours an arbitrary vertex. Thus, after Alice’s move the coloured vertex is the monochromatic center $S$ and every uncoloured vertex of $G$ satisfies either the property (1) or the property (2). Suppose that $G$ has at least one coloured vertex. Thus, $G$ has the monochromatic center $S$ such that every uncoloured vertex of $G$ with $S$ satisfies either the property (1) or the property (2). Let $B$ be a block that contains at least one uncoloured vertex and such that $B$ has a coloured block-cut-vertex $w$ or $B$ has no block-cut-vertex. Let $T=w$ or $T=S$, whenever a block-cut-vertex of $B$ does not exist and $c_s=c(T)$. Suppose that in $B$ there is an uncoloured vertex $u$ with the property (1). Observe that if Alice colours $u$ with any admissible colour distinct from $c_s$, then the resulting graph is in $\alpha _{k,r}^d(G)$. Indeed, the vertex $u$ affects only the properties of uncoloured vertices in $B$. Since $u$ has no coloured front-neighbours, after Alice’s move for each vertex that had the property (1) the inequality $(*)$ still holds and hence the vertex still has the property (1). Similarly, if a vertex had the property (2), it still has the property (2). Next, we must show that there is an admissible colour for $u$ distinct from $c_s$. Observe the following $\square$

Claim 1

Let $u$ be an uncoloured vertex and $T=B_b(u){\setminus } B'_b(u)$. Let $c\in \{1,\ldots ,r\}{\setminus } c(T)$, whenever $T$ is coloured. If in $N^s_f[(N(u){\setminus } T)\cap C]$ there are fewer than $d+1$ vertices with $c$, then $c$ is admissible for $u$.

Claim 2

Let $1\le d\le k-2,\;r=k+1-d$ and $k\ge 4$. Then the following inequalities are valid:

• (1) $2k-3<(r-1)(d+1)$;

• (2) $k-2<(r-2)(d+1)$.

In $B{\setminus } T$ there are at most $k-2$ coloured vertices and the inequality $(*)$ implies that they have at most $k-2$ coloured front-neighbours. Assume that in $\{1,\ldots ,r\}{\setminus } c_s$ there is no admissible colour for $u$. Thus, in $N^s_f[(B{\setminus } T)\cap C]$ there are $d+1$ vertices with a colour $c$ for every $c\in \{1,\ldots ,r\}{\setminus } c_s$. However, it follows from the inequality (1) of Claim 2 that $2(k-2)<(r-1)(d+1)$, so we conclude that there must be a colour $c$ that is assigned to fewer than $d+1$ vertices and this colour is admissible for $u$.

If there is no vertex with the property (1) in $B$, then Alice colours a vertex $u$ with the property (2). In this case in $B{\setminus } \{u\}$ there is at most one uncoloured vertex and it has the property (2), moreover, in $B{\setminus } T$ there is at most one coloured vertex with a similar front-neighbor. Similarly as above Alice colours $u$ with any admissible colour distinct from $c_s$. Observe that after Alice’s move $u$ may have a similar front-neighbor. If in $B{\setminus } \{u\}$ there was an uncoloured vertex, then in $B{\setminus } T$ there was no vertex with a similar front-neighbor. Thus, the resulting graph is in $\alpha _{k,r}^d(G)$. Now, we show that in $\{1,\ldots ,r\}{\setminus } c_s$ there is an admissible colour for $u$. In the contrary case in $N^s_f[(B{\setminus } T)\cap C]$ there are $d+1$ vertices coloured with a colour $c$ for every $c\in \{1,\ldots ,r\}{\setminus } c_s$. In $B{\setminus } T$ there are at most $k-2$ coloured vertices and at most one vertex has one similar front-neighbor. It follows from the inequality (1) of Claim 2 that $k-1<(r-1)(d+1)$ and hence we obtain a contradiction.

Now, we consider the case when Bob starts. Assume that after Bob’s move $G\notin \alpha _{k,r}^d(G)$. Before Bob’s move every uncoloured vertex of $G$ with the monochromatic center $S$ had satisfied either the property (1) or the property (2), we show that after Bob’s move Alice can colour a vertex in such a way that again every uncoloured vertex of the resulting graph with the same monochromatic center $S$ has the property (1) or the property (2). Assume that after Bob’s move a vertex $u$ has neither the property (1) nor (2). We consider two cases regarding the property of $u$ before Bob’s move.

Case 1 $u$ had the property (1).

Thus, Bob has coloured a vertex $b$ such that $b$ was in an uncoloured front-stem of $u$ or $b$ was a front-neighbor of a coloured vertex of $B'_b(u)$. First, assume that $b$ was in an uncoloured front stem of $u$. Since $u$ does not have the property (2), it follows that in $B'_b(u){\setminus }\{u\}$ there are

• (i) two vertices with two coloured stems, or

• (ii) one uncoloured vertex with two coloured stems and one coloured vertex with a similar front-neighbor, or

• (iii) $|N_f^s(B'_b(u)\cap C)|\ge 2$.

Let $w$ be the block-cut-vertex of $B_b(u)$. The items (i)–(iii) imply that $w$ is coloured or does not exist. Let $c_s=c(B_b(u)-B'_b(u))$. First, suppose that in $B_b(u){\setminus } \{u\}$ there is an uncoloured vertex with two coloured stems (either the item (i) or the item (ii)). If Alice colours $u$ with an admissible colour distinct from $c_s$ and distinct from the colour $c_0$ of its front-neighbor (whenever a coloured front-neighbor of $u$ exists), then the resulting graph is in $\alpha _{k,r}^d(G)$: any vertex of $B'_b(u)$ that had had the property (1), still has the property (1); any vertex of $B'_b(u)$ that had had the property (2), still has the property (2). Now, we show that the colour $c\in \{1,\ldots t\}{\setminus } \{c_s,c_0\}$ that is admissible for $u$ exists. Since in $N^s_f[B'_b(u)\cap C]$ there are at most $k-2$ coloured vertices and by Claim 2 it holds $k-2<(r-2)(d+1)$, it follows that there must be colour $c\in \{r,\ldots ,r\}{\setminus } \{c_s,c_0\}$ such that in $N^s_f[B'_b(u)\cap C]$ there are fewer than $d+1$ vertices with $c$.

Now, suppose that in $B_b(u){\setminus } \{u\}$ there is no uncoloured vertex with two coloured stems (the item (iii)). If Alice colours $u$ with an admissible colour distinct from $c_s$, then for any uncoloured vertex of $B'_b(u)$ the inequality $(*)$ still holds and hence any uncoloured vertex of $B'_b(u)$ has the property (1) after Alice’s move, so the resulting graph is in $\alpha _{k,r}^d(G)$. We show that an admissible colour for $u$ distinct from $c_s$ exists. Assume the contrary that for any colour $c\in \{1,\ldots ,r\}{\setminus } \{c_s\}$ there are at least $d+1$ vertices with $c$ in $N^s_f[B'_b(u)\cap C]\cup (N_f(u)\cap C)$. Since in $B'_b(u)$ there are at most $k-2$ coloured vertices and $B'_b(u)$ has at most $k-2$ similar front-neighbours (by the inequality $(*)$) and $u$ has at most one coloured front-neighbor, we have $|N^s_f[B'_b(u)\cap C]\cup (N_f(u)\cap C)|\le 2k-3$. However, $2k-3<(r-1)(d+1)$ holds by Claim 2, which contradicts our assumption.

Now, assume that $b$ is a front-neighbor of a coloured vertex of $B'_b(u)$. Since $u$ does not have the property (1), the inequality $(*)$ for $u$ does not hold. Observe that if before Bob’s move in $B'_b(u)$ there had been an uncoloured vertex $v$ with the property (2), then after Bob’s move in $B'_b(u)$ there is exactly one coloured vertex and it has two similar front-neighbours. Moreover, in $B'_b(u){\setminus } \{v\}$ there is no uncoloured vertex with the property (2). In this case Alice colours $v$. Let $c_1$ be the colour of the vertex in $B'_b(u)$ and $c_2$ be the colour of the coloured vertex in $\mathcal{B}_f(v)$ whenever such a vertex exists. If $c_1=c_2$, then Alice colours $v$ with a colour distinct from $c_s$ and $c_1$, since players use at least tree colours such a colour exists. If $c_1\ne c_2$ and players use more than three colours, then Alice can colour $v$ with a colour distinct from $c_s,c_1$ and $c_2$. Assume that $c_1\ne c_2$ and players use exactly three colours. In this case $d\ge 3$ this implies that the colour $c_1$ is admissible for $v$. Thus, Alice colours $v$ with $c_1$. After such a move for any uncoloured vertex of $B'_b(u)$ the inequality $(*)$ holds and hence the resulting graph is in $\alpha _{k,r}^d(G)$. If before Bob’s move all uncoloured vertices of $B'_b(u)$ had the property (1), then Alice colours $u$ with any admissible colour distinct from $c_s$. Since $|N^s_f[B'_b(u)\cap C]\cup (N_f(u)\cap C)|\le 2k-3$ and the inequality $2k-3<(r-1)(d+1)$ holds, it follows that such an admissible colour exists.

Case 2 $u$ had the property (2).

Let us consider the following subcases:

Subcase 2.1 $u$ has three coloured stems.

Thus, Bob has coloured a vertex $b$ of an uncoloured front-stem of $u$. First assume that $B_b(u)$ has the uncoloured block-cut-vertex $w$. This assumption implies that each vertex of $B'_b(u){\setminus } \{u\}$ is uncoloured and has the property (1). Alice colours $u$ with a colour $c$ such that $c\notin c(N(u))$. After such a move $w$ still has the property (2), each vertex of $B'_b(u){\setminus } \{u\}$ has the property (1) and hence the resulting graph is in $\alpha _{k,r}^d(G)$. Assume that $B_b(u)$ has the coloured block-cut-vertex $w$ or has no block-cut-vertex. Let $c_s=c(B_b(u)-B'_b(u))$. If in $B'_b(u){\setminus } \{u\}$ there is an uncoloured vertex with two coloured stems, then any coloured vertex of $B'_b(u)$ has no similar front neighbor. Alice colours $u$ with a colour distinct from $c_s$ and $c(b)$. After such a move $u$ has at most one similar front-neighbor and hence the vertex of $B'_b(u){\setminus } \{u\}$ with two coloured stems has the property (2). Since in $B'_b(u)$ there are at most $k-3$ coloured vertices and none of them has the similar front neighbor and $k-3<(r-2)(d+1)$ holds, it follows that there is an admissible colour for $u$ distinct from $c_s$ and $c(b)$. If each vertex of $B'_b(u){\setminus } \{u\}$ has one coloured stem, then at most one coloured vertex of $B'_b(u)$ has a similar front neighbor. Similarly as above, Alice colours $u$ with a colour distinct from $c_s$ and $c(b)$. After such a move $u$ has at most one similar front-neighbor and hence any uncoloured vertex of $B'_b(u){\setminus } \{u\}$ has the property (1). Since $|N^s_f[B'_b(u)\cap C]\cup (N_f(u)\cap C)|\le k-2$ and the inequality $k-2<(r-2)(d+1)$ holds, it follows that such a colour exists.

Subcase 2.2 In $\mathcal{B}_f(u){\setminus } \{u\}$ there are two vertices not having the property (1) or there is a vertex with a similar front-neighbor.

Thus, Bob has coloured a vertex $b$ belonging to a front-stem of $u$. Since we are not in Subcase 2.1 we may assume that $u$ has one coloured front-stem. Let $B_f(u)$ be the front-block belonging to the coloured front-stem. Since before Bob’s move $(G,c_r)$ was in $\alpha _{k,r}^d(G)$ this implies that in $B_f(u)$:

• there are two coloured vertices, or

• there are two uncoloured vertices with the property (2), or

• there is one coloured vertex and one uncoloured vertex with the property (2), or

• there is one coloured vertex with a similar neighbor.

First, assume that $B_b(u)$ has the uncoloured block-cut-vertex $w$. Hence, each vertex of $B_b(u)$ is uncoloured. Alice colours $u$ with a colour $c,\;c\notin c(N(u))$. Assume that $B_b(u)$ has the coloured block-cut-vertex $w$ or has no block-cut-vertex. Let $c_s=c(B_b(u)-B'_b(u))$. Alice colours $u$ with an admissible colour distinct from $c_s$ and $c(b)$. After such a move $u$ has at most one similar front-neighbor so if in $B'_b(u)$ there is a vertex with two coloured stems, then it has the property (2). All uncoloured vertices of $B'_b(u)$ with one coloured front-stem have the property (1). All uncoloured vertices of $B_f(u)$ have either the property (1) or (2). Similarly as above we can show that an admissible colour for $u$ distinct from $c_s$ and $c(b)$ exists.

Subcase 2.3 In $B'_b(u){\setminus } \{u\}$ there are two uncoloured vertices with two coloured stems.

Before Bob’s move $u$ had the property (2) and hence it had two coloured stems. Thus, before Bob’s move in $B'_b(u)$ there had been two uncoloured vertices with two coloured stems. This implies that the block-cut-vertex $w$ of $B_b(u)$ is coloured or does not exist. Let $c_s=c(B_b(u)-B'_b(u))$. Alice colours $u$ with an admissible colour $c\ne c_s$ and $c\notin c(N_f(u))$. After her move $u$ has no similar front-neighbor and hence each vertex of $B'_b(u)$ with two coloured stems has the property (2). Since in $B'_b(u)$ there are at most $k-4$ coloured vertices and none of them has similar front neighbours, such a colour exists.

Subcase 2.4 In $B'_b(u){\setminus } \{u\}$ there is a coloured vertex with one similar front-neighbor and an uncoloured vertex with two coloured stems.

Thus, before Bob’s move in $B'_b(u)$ there had been either a coloured vertex with a similar front neighbor or two uncoloured vertices with two coloured stems. This implies that the block-cut-vertex $w$ of $B_b(u)$ is coloured or does not exist. Let $c_s=c(B_b(u)-B'_b(u))$. Alice colours $u$ with a colour distinct from $c_s$ and $c(N_f(u))$. Since $|N^s_f[B'_b(u)\cap C]|\le k-2$ and the inequality $k-2<(r-2)(d+1)$ holds, it follows that such a colour exists.

Subcase 2.5 $|N_f^s(B'_b(u)\cap C)|=2$

Thus, before Bob’s move in $B'_b(u)$ there had been a coloured vertex with a similar front neighbor. This implies that the block-cut-vertex $w$ of $B_b(u)$ is coloured or does not exist, and each uncoloured vertex of $B_b(u){\setminus } \{u\}$ has the property (1). Let $c_s=c(B_b(u)-B'_b(u))$. Alice colours $u$ with an admissible colour $c$ such that $c\ne c_s$. After Alice’s move each uncoloured vertex of $B_b(u){\setminus } \{u\}$ still has the property (1). Since $|N^s_f[B'_b(u)\cap C]\cup (N_f(u)\cap C)|\le k+1$ and the inequality $k+1<(r-1)(d+1)$ holds, it follows that such a colour exists.

Remark 3

Observe that Lemma 7 is not true for $k=4$. The only point where the proof for $k=4$ does not work is the end of Case 1, when $c_1\ne c_2$ and players use exactly three colours.

Theorem 8

Let $k\ge 5,\;1\le d\le k-2$ and $G\in \mathcal{H}_k$. Then $\chi _{ug}^{(d)}(G)\le k+1-d$.

Proof

Let $G\in \mathcal{H}_k$. Let $G'$ be a connected graph such that each block of $G'$ is $K_k$ and $G\subseteq G'$. Lemma 7 implies that there exists an $(\mathcal{S}_d,k+1-d)$-game closed family containing $G'$. Thus, Alice has a winning strategy for the unilateral $\mathcal{S}_d$-game on $G'$ with $k+1-d$ colours, she can play in such a way that after her move the partially $(k+1-d)$-coloured graph $G'$ always belongs to $\alpha _{k,r}^d(G')$. Thus, $\chi _{ug}^{(d)}(G')\le k+1-d$, so by Lemma 3 $\chi _{ug}^{(d)}(G)\le k+1-d$. $\square$

The proof of Theorem 7 immediately follows from Lemma 5, Theorem 8 and Lemma 1.

We finish this section with results that combine Theorem 5 with known results for $\mathcal{H}_k$. In [9] was proved that $\chi _g(\mathcal{H}_k)\le k+2$. This result with Theorems 2, 3 and 7 give the following:

Corollary 1

Let $k\ge 2$ and $0\le d\le k-1$. Then $\chi _{g}^{(d)}(\mathcal{H}_k)\le k+2-d$.

We can improve the upper bound if $k$ is large enough. In [9] was proved that for $k\ge 6$ it holds $\chi _g(\mathcal{H}_k)\le k+1$. Thus,

Corollary 2

Let $k\ge 6,\;0\le d\le k-2$. Then $\chi _{g}^{(d)}(\mathcal{H}_k)\le k+1-d$.

Observe that according to our assumptions on $d$, all results say about games in which players use at least three colours. The problem how large must $d$ be to guarantee Alice to win the relaxed colouring game with two colours remains open.

6 The relaxed game chromatic number of forests

In this section we present some results about the game on forests. The $(r,d)$-relaxed edge-colouring game on $G$ could be seen as the $(r,d)$-relaxed colouring game on the line graph of $G$. Since $\mathcal{H}_k$ contains the line graphs of trees with maximum degree $k$, Corollary 1 implies the following:

Corollary 3

Let $T$ be a forest and $0\le d \le \Delta (T)-1$. Then $^{(d)}\chi '_g(T)\le \Delta (T)+2-d$.

Andres [1] proved that $\chi '_g(T)\le \Delta (T)+1$ for any forest with $\Delta (T)\ge 5$. Thus, by Corollary 1 we can improve previous result for a forest with maximum degree at least 5.

Corollary 4

Let $T$ be a forest with $\Delta (T)\ge 5$ and $0\le d \le \Delta (T)-2$. Then $^{(d)}\chi '_g(T)\le \Delta (T)+1-d$.

Dunn ([3]) studied the $(r,d)$-relaxed edge-colouring game and he proved the following results for forests.

Theorem 9

([3]) Let $T$ be a forest. If $d\ge 1$, then $^{(d)}\chi '_g(T)\le \Delta (T) +1$.

Theorem 10

([3]) Let $T$ be a forest. If $d\ge 3$, then $^{(d)}\chi '_g(T)\le \Delta (T)$.

We can improve these results in the following way:

Theorem 11

Let $T$ be a forest and $\Delta (T)\ne 3$. If $d\ge 1$, then $^{(d)}\chi '_g(T)\le \Delta (T)$.

Theorem 12

Let $T$ be a forest of maximum degree at least 5. If $d\ge 2$, then $^{(d)}\chi '_g(T)\le \Delta (T)-1$.

Theorem 13

Let $T$ be a forest. If $d\ge 3$, then $^{(d)}\chi '_g(T)\le \Delta (T)-1$.

Theorem 12 immediately follows from Theorem 8. The proof of Theorem 11 for a forest of maximum degree at least $4$ follows from Theorems 6 and 8. To complete the proof we must prove that $^{(d)}\chi '_g(P)\le 2$ for $d\ge 1$ where $P$ is a forest with maximum degree at most 2 it holds. We show this in Proposition 5. One can observe that the upper bound in Theorem 13 is obviously true for a forest with maximum degree at most 2. The proof of Theorem 13 for a forest of maximum degree at least 4 follows from Theorems 3 and 8. Thus, to complete the proof of Theorem 13 we need the result proving that this upper bound is also true for a forest of maximum degree 3, i.e., we must show that Alice has a winning strategy for the $(2,d)$-relaxed edge-colouring game on any forest of maximum degree 3 for $d\ge 3$. We give in Corollary 5 this result. We prove the more general result—Theorem 14, in which we consider the relaxed colouring game on a graph $G\in \mathcal{H}_k$ such that each vertex is in at most two blocks. We answer the following question: how large must $d$ be to guarantee Alice to win the game in which both players use only two colours.

Let us consider the unilateral $\mathcal{S}_1$-colouring game on a forest with maximum degree at most 2, i.e., a linear forest. We show that Alice has a winning strategy for this game with two colours. Similarly as in previous sections we construct the family of partially coloured graphs and we prove that this family is game closed. Let $P$ be a path with vertex set $V=\{v_1,\ldots ,v_n\}$ and edge set $E=\{v_iv_{i+1}|i=1,\ldots n-1\}$.

Definition 5

(Family $\alpha (P)$) The family $\alpha (P)$ contains the partially $2$-coloured graphs $(P,c_2)$ with the following property:

($\bullet$) Let $P'=v_i\ldots v_j\;(1\le i\le j\le n)$ be any maximal connected subpath induced by coloured vertices.

• If $i=j$, then either in $\{v_1,\ldots ,v_{i-1}\}$ there is no coloured vertex or in $\{v_{j+1},\ldots ,v_n\}$ there is no coloured vertex .

• If $i\ne j$ and $c(v_i)=c(v_{i+1})$, then in $\{v_1,\ldots ,v_{i-1}\}$ there is no coloured vertex.

• If $i\ne j$ and $c(v_{j-1})=c(v_{j})$, then in $\{v_{j+1},\ldots ,v_n\}$ there is no coloured vertex.

Remark 4

In Definition 5 we assume that for $i=1$ the set $\{v_1,\ldots ,v_{i-1}\}$ is empty and similarly for $j=n$ the set $\{v_{j+1},\ldots ,v_n\}$ is empty.

Lemma 8

The family $\alpha (P)$ is $(\mathcal{S}_1,2)$-game closed.

Proof

Let $P\in \alpha (P)$. We must show that Conditions (i) and (ii) of Definition 1 hold. It is easy to see that if Alice starts, then she can colour a vertex in such a way that after her move the graph belongs to $\alpha (P)$. Thus, assume that Bob has coloured a vertex in such a way that the resulting graph is not in $\alpha (P)$. Since before Bob’s move the graph $P$ had been in $\alpha (P)$, it follows that one of the following cases holds:

• There is a coloured vertex $v_i$ whose neighbours are uncoloured and such that in the set $\{v_1,\ldots ,v_{i-1}\}$ there is a coloured vertex and in the set $\{v_{j+1},\ldots ,v_n\}$ there is a coloured vertex.

• There is a maximal connected subpath $P'=v_i\ldots v_j\;(1\le i< j\le n)$ induced by coloured vertices such that $c(v_i)=c(v_{i+1})$ and there is a coloured vertex in $\{v_1,\ldots ,v_{i-1}\}$.

• There is a maximal connected subpath $P'=v_i\ldots v_j\;(1\le i< j\le n)$ induced by coloured vertices such that $c(v_{j-1})=c(v_{j})$ and there is a coloured vertex in $\{v_{j+1},\ldots ,v_n\}$.

In the first case Alice can colour either $v_{i-1}$ or $v_{i+1}$. For both vertices the colour $c$ distinct from $c(v_i)$ is admissible and after colouring one of these vertices with $c$ the resulting graph is in $\alpha (P)$. In the second case Alice colours $v_{i-1}$ with a colour distinct from $c(v_i)$ and in the last case Alice colours $v_{j+1}$ with a colour distinct from $c(v_j)$. $\square$

From Lemma 8 it follows that $\chi ^{(1)}_{ug}(P)\le 2$ for any linear forest $P$. Then, we immediately have the following:

Proposition 5

If $P$ is a linear forest and $d\ge 1$, then $^{(d)}\chi '_g(P)\le 2$.

Now, we consider the unilateral $\mathcal{S}_d$-colouring game with two colours on a graph belonging to $\mathcal{H}_k$ such that each vertex of the graph is in at most two blocks. We give the winning strategy for Alice when $d=k-1+\left\lfloor \frac{k-1}{2}\right\rfloor$.

Let $k\ge 3$, $G\in \mathcal{H}_k$ and $G$ be a connected graph such that each block of $G$ is isomorphic to $K_k$ and each vertex is in at most two blocks.

Definition 6

(Family $\alpha _{k,2}(G)$) The family $\alpha _{k,2}(G)$ contains the uncoloured graph $G$ and the partially $2$-coloured graphs $(G,c_2)$ with monochromatic center $S$ such that every uncoloured vertex $u$ has one of the following properties:

• (1) $u$ has exactly one coloured stem,

• (2) $u$ has exactly two coloured stems and any coloured vertex of $\mathcal{B}_f(u)$ has at most $\left\lfloor \frac{k-1}{2}\right\rfloor$ similar front-neighbours. Moreover, a coloured vertex of $\mathcal{B}_f(u)$ has exactly $\left\lfloor \frac{k-1}{2}\right\rfloor$ similar front-neighbours only if all vertices of its front-block are coloured.

Lemma 9

Let $k\ge 3$ and $d=k-1+\left\lfloor \frac{k-1}{2}\right\rfloor$. Then the family $\alpha _{k,2}(G)$ is $(\mathcal{S}_d,2)$-game closed.

Proof

Let $G\in \alpha _{k,2}(G)$. Assume that Alice starts and $G$ has at least one coloured vertex. Thus, $G$ has the monochromatic center $S$ such that every uncoloured vertex of $G$ with $S$ satisfies either the property (1) or the property (2). We show that Alice can colour a vertex in such a way that every uncoloured vertex of the resulting graph with the same monochromatic center $S$ has the property (1) or the property (2). Let $B$ be a block that contains at least one uncoloured vertex and such that $B$ has a coloured block-cut-vertex $w$ or $B$ has no block-cut-vertex. Let $T=w$ or $T=S$, whenever a block-cut-vertex of $B$ does not exist. Let $u$ be an uncoloured vertex of $B$. First, assume that $T=S$. Observe that in this case, if Alice colours $u$ with any admissible colour, then the resulting graph is in $\alpha _{k,2}(G)$. Without loss of generality we may assume that in $B$ the number of vertices coloured with 1 is smaller or equal to the number of vertices coloured with 2. Thus, $|\{x:x\in B,c(x)=1\}|\le \left\lfloor \frac{k-1}{2}\right\rfloor$. We claim that the colour 1 is admissible for $u$: if $u$ has the property (1), then no vertex of $B_f(u)$ is coloured, moreover, any coloured vertex of $B=B_b(u)$ has at most $k-1+\left\lfloor \frac{k-1}{2}\right\rfloor -1$ neighbours with 1 and $u$ has at most $\left\lfloor \frac{k-1}{2}\right\rfloor$ neighbours with 1; if $u$ has the property (2), then any coloured vertex of $B_f(u)$ has at most $k-2+\left\lfloor \frac{k-1}{2}\right\rfloor$ neighbours with 1 (by the condition (2)), any coloured vertex of $B=B_b(u)$ has at most $k-1+\left\lfloor \frac{k-1}{2}\right\rfloor -1$ neighbours with 1 and $u$ has at most $k-1+\left\lfloor \frac{k-1}{2}\right\rfloor$ neighbours with 1. Now, assume that $T=w$. Let $v$ be the block-cut vertex of $B_b(w)$. Observe that the colouring of $u$ affects only the property of $v$ (whenever $v$ is uncoloured). Thus, Alice must colour $u$ in such a way that after her move $w$ (the front-neighbor of $v$) has at most $\left\lfloor \frac{k-1}{2}\right\rfloor$ similar front-neighbours and $w$ has exactly $\left\lfloor \frac{k-1}{2}\right\rfloor$ similar front-neighbours only if all vertices of $B$ are coloured. Assume that $c(w)=1$. If in $B$ there are fewer than $\left\lfloor \frac{k-1}{2}\right\rfloor$ vertices with 1, then Alice colours $u$ with 1. Similarly as above, we see that the colour 1 is admissible for $u$ and after Alice’s move the resulting graph is in $\alpha _{k,2}(G)$, since $w$ has at most $\left\lfloor \frac{k-1}{2}\right\rfloor -1$ similar front-neighbours. If in $B$ there are more than $\left\lfloor \frac{k-1}{2}\right\rfloor$ vertices with 1, then Alice colours $u$ with 2. Since in $B$ there are at most $\left\lfloor \frac{k-1}{2}\right\rfloor$ vertices with 2, the colour 2 is admissible for $u$. Now, assume that in $B$ there are exactly $\left\lfloor \frac{k-1}{2}\right\rfloor$ vertices with 1. If all vertices of $B{\setminus } \{u\}$ are coloured, then Alice can colour $u$ with 1 and after her move the resulting graph is in $\alpha _{k,2}(G)$. If in $B{\setminus } \{u\}$ there is any uncoloured vertex, then in $B$ there are fewer than $\left\lfloor \frac{k-1}{2}\right\rfloor$ vertices with 2 and hence the colour 2 is admissible for $u$.

Now, we consider the case when Bob starts. Assume that after Bob’s move $G\notin \alpha _{k,2}(G)$. If before Bob’s move a vertex had had the property (1), then after Bob’s move it has either the property (1) or (2). Thus, there must be a vertex $u$ such that before Bob’s move it had had the property (2) and after Bob’s move it has neither the property (1) nor (2). This implies that in $B_f(u)$ there is a coloured vertex $x$ having $\left\lfloor \frac{k-1}{2}\right\rfloor$ similar front-neighbours and in $B_f(x)$ there is any uncoloured vertex. Alice colours $u$. Let $w$ be a block-cut-vertex of $B_b(u)$, whenever a block-cut-vertex of $B_b(u)$ exists. Similarly as above we see that the colour of $u$ affects only the property of an uncoloured block-cut-vertex of $B_b(w)$. Thus, Alice must colour $u$ in such a way that after her move $w$ has at most $\left\lfloor \frac{k-1}{2}\right\rfloor$ similar front-neighbours and $w$ has exactly $\left\lfloor \frac{k-1}{2}\right\rfloor$ similar front-neighbours only if each vertex of $B$ is coloured. Using the same arguments as above we can prove that Alice can always colour $u$ in such a way. $\square$

From Lemmas 5 and 9 it immediately follows:

Theorem 14

Let $k\ge 3$ and $G\in \mathcal{H}_k$ such that each vertex is in at most two blocks and $d\ge k-1+\left\lfloor \frac{k-1}{2}\right\rfloor$. Then $\chi _{ug}^{(d)}(G)\le 2$.

Theorem 14 implies the corollary that completes the proof of Theorem 13.

Corollary 5

For any forest $T$ of maximum degree 3, it holds $^{(d)}\chi '_g(T)\le 2$ for $d\ge 3$.