\publicationdata

vol. 26:220241210.46298/dmtcs.109712023-02-17; 2023-02-17; 2024-02-152024-05-24

Line game-perfect graphs

Stephan Dominique Andres\affiliationmark1 Wai Lam Fong\affiliationmark2 Institute of Mathematics and Computer Science, University of Greifswald, Germany
Department of Mathematics, The University of Hong Kong, Hong Kong SAR, China

Abstract

.
The $[X,Y]$ -edge colouring game is played with a set of $k\in{\mathbb{N}}$ colours on a graph $G$ with initially uncoloured edges by two players, Alice (A) and Bob (B). The players move alternately. Player $X\in\{A,B\}$ has the first move. $Y\in\{A,B,-\}$ . If $Y\in\{A,B\}$ , then only player $Y$ may skip any move, otherwise skipping is not allowed for any player. A move consists of colouring an uncoloured edge with one of the $k$ colours such that adjacent edges have distinct colours. When no more moves are possible, the game ends. If every edge is coloured in the end, Alice wins; otherwise, Bob wins.

The $[X,Y]$ -game chromatic index $\chi_{[X,Y]}^{\prime}(G)$ is the smallest nonnegative integer $k$ such that Alice has a winning strategy for the $[X,Y]$ -edge colouring game played on $G$ with $k$ colours. The graph $G$ is called line $[X,Y]$ -perfect if, for any edge-induced subgraph $H$ of $G$ ,

\chi_{[X,Y]}^{\prime}(H)=\omega(L(H)),

where $\omega(L(H))$ denotes the clique number of the line graph of $H$ .

For each of the six possibilities $(X,Y)\in\{A,B\}\times\{A,B,-\}$ , we characterise line $[X,Y]$ -perfect graphs by forbidden edge-induced subgraphs and by explicit structural descriptions, respectively.

keywords:

line graph, line perfect graph, edge colouring game, game-perfect graph, graph colouring game, perfect graph, forbidden subgraph characterisation

1 Introduction

A subgraph $H$ of a graph $G$ is an induced subgraph of $G$ if every edge of $G$ whose two end-vertices are in the vertex set of $H$ is also an edge of $H$ . A subgraph $H$ of a graph $G$ is an edge-induced subgraph of $G$ if the vertex set of $H$ consists of all end-vertices of edges of $H$ . Equivalently, an edge-induced subgraph of $G$ is a subgraph of $G$ that contains no isolated vertices.

The line graph $L(G)$ of a graph $G=(V,E)$ is the graph $(V^{\prime},E^{\prime})$ with $V^{\prime}=E$ and where the edge set $E^{\prime}$ of $L(G)$ is the set of all unordered pairs $\{e_{1},e_{2}\}$ of elements in $E$ such that $e_{1}$ and $e_{2}$ are adjacent as edges in $G$ .

Edge colouring of a graph $G$ is equivalent to vertex colouring of its line graph $L(G)$ . Moreover, the colouring parameter for edge colouring, the chromatic index $\chi^{\prime}(G)$ of $G$ , equals the chromatic number $\chi(L(G))$ of the line graph $L(G)$ .

In this sense, the well-established concept of perfectness for vertex colouring has an interesting analog for edge colouring, namely line perfectness, which was first defined by Trotter (1977). A graph $G$ is line perfect if, for any edge-induced subgraph $H$ of $G$ ,

\chi^{\prime}(H)=\omega(L(H)),

where $\omega(L(H))$ , the clique number of the line graph of $H$ , is the maximum number of mutually adjacent edges in $H$ . Equivalently, as remarked by Trotter (1977), a graph is line perfect if its line graph is a perfect graph. The reason for this equivalence is the fact that, for any graph $G$ , the set of the line graphs of the edge-induced subgraphs of $G$ is the same as the set of the induced subgraphs of $L(G)$ .

It is known that line perfect graphs are perfect:

Theorem 1 (Trotter (1977)).

Line perfect graphs are perfect.

Trotter (1977) gave a characterisation of line perfect graphs by a set of forbidden edge-induced subgraphs:

Theorem 2 (Trotter (1977)).

A graph is line perfect if and only if it contains no odd cycles of length at least 5 as edge-induced subgraphs.

Maffray (1992) gave a complete characterisation of the structure of line perfect graphs:

Theorem 3 (Maffray (1992)).

A graph $G$ is line perfect if and only if each of its blocks is either bipartite or a complete graph $K_{4}$ on 4 vertices or a triangular book $K_{1,1,n}$ for some positive integer $n$ .

Since bipartite graphs, $K_{4}$ , and triangular books are perfect, the powerful Theorem 3 implies the result of Theorem 1.

In this paper we combine the idea of line perfect graphs with graph colouring games. For each such game, we define a notion of line game-perfectness and give a characterisation of the structure of such line game-perfect graphs. These characterisations include two equivalent descriptions: a characterisation by forbidden edge-induced subgraphs analog to the Theorem of Trotter (Theorem 2) and a characterisation by an explicit structural description analog to the Theorem of Maffray (Theorem 3).

1.1 Vertex colouring games

A vertex colouring game is played with a set of $k$ colours ( $k\in{\mathbb{N}}$ ) on a graph $G=(V,E)$ whose vertices are initially uncoloured by two players, Alice (A) and Bob (B). The players move alternately. A move consists in colouring an uncoloured vertex with one of the $k$ colours such that adjacent vertices receive distinct colours. The game ends when such a move is not possible. If every vertex is coloured in the end, Alice wins. Otherwise, i.e., in the case that an uncoloured vertex is adjacent to vertices of all $k$ colours, Bob wins.

Such a graph colouring game, defined by Brams, appeared in a mathematical games column by Gardner (1981). Later it was reinvented by Bodlaender (1991) who defined the game chromatic number $\chi_{g}(G)$ as the smallest nonnegative integer $k$ such that Alice has a winning strategy for the vertex colouring game played on $G$ . Since Alice always wins if $k\geq|V|$ , the parameter is well-defined.

To be precise, two more rules have to be fixed to make the game well-defined. Firstly, we have to fix the player $X\in\{A,B\}$ who moves first. Secondly, we have to fix whether skipping (any) moves is allowed for some player $Y\in\{A,B\}$ or not allowed (which we denote by $Y\in\{-\}$ ). Thus we have six different games, one game for any of the pairs

(X,Y)\in\{A,B\}\times\{A,B,-\},

and we call such a game the $[X,Y]$ -colouring game and denote its game chromatic number by $\chi_{[X,Y]}(G)$ .

The distinction of the six games is important when we discuss game-theoretic analogs of perfect graphs, the game-perfect graphs.

1.2 Game-perfect graphs

A graph $G$ is $[X,Y]$ -perfect (or game-perfect for the $[X,Y]$ -colouring game) if, for any induced subgraph $H$ of $G$ ,

\chi_{[X,Y]}(H)=\omega(H),

where $\omega(H)$ , the clique number of $H$ , is the maximum number of mutually adjacent vertices in $H$ .

The concept of game-perfect graphs was introduced by Andres (2007, 2009). For four of the six games, structural characterisations of game-perfect graphs by forbidden induced subgraphs and by an explicit structural description are known. The characterisation by forbidden induced subgraphs of two of these characterisations will be extremely useful as basis for two of our main theorems in the following sections:

$P_{4}$

$C_{4}$

triangle star

$\Xi$ -graph

two split 3-stars

mixed graph

two double fans

Figure 1: Forbidden induced subgraphs for

[A,-]

-perfect graphs

chair

$P_{4}\cup K_{1}$

$C_{4}\cup K_{1}$

split 3-star

$P_{5}$

$C_{5}$

double fan

4-fan

4-wheel

$F_{10}$

$F_{11}$

$F_{12}$

$F_{13}$

$F_{14}$

$F_{15}$

Figure 2: Forbidden induced subgraphs for

[B,-]

-perfect graphs

Theorem 4 (Andres (2012)).

A graph is $[A,-]$ -perfect if and only if it contains none of the seven graphs depicted in Figure 1 as an induced subgraph.

Theorem 5 (Lock (2016); Andres and Lock (2019)).

A graph is $[B,-]$ -perfect if and only if it contains none of the fifteen graphs depicted in Figure 2 as an induced subgraph.

Furthermore, Andres (2012) characterised the class of $[B,B]$ -perfect graphs by an explicit structural description. An ear animal is a graph of the form

K_{1}\vee((K_{a}\vee(K_{b}\cup K_{c}))\cup K_{d_{1}}\cup K_{d_{2}}\cup\ldots\cup K_{d_{k}})

with $k\geq 0$ and $a,b,c,d_{1},d_{2},\ldots,d_{k}\geq 0$ . Here, $G_{1}\cup G_{2}$ (resp., $G_{1}\vee G_{2}$ ) denotes the disjoint union (resp., the join) of two graphs $G_{1}$ and $G_{2}$ .

Theorem 6 (Andres (2012)).

A graph is $[B,B]$ -perfect if and only if each of its components is an ear animal.

We will use this result in order to simplify the proof of one of our main theorems (Theorem 12).

Lock (2016) and Andres and Lock (2019) characterised the class of $[B,-]$ -perfect graphs by a (very large) explicit structural description. From this description we will need only two partial results, given in Proposition 7 and Proposition 8, in order to simplify the proof of another one of our main theorems (Theorem 11).

An expanded cocobi is a graph of the type depicted in Figure 3 with $k\geq 1$ , $a,d\geq 0$ , and $b_{1},\ldots,b_{k}\geq 1$ , $c_{1},\ldots,c_{k}\geq 1$ . An expanded cocobi consists of $2k$ nonempty cliques $B_{1},\ldots,B_{k},C_{1},\ldots,C_{k}$ and two (possibly empty) cliques $A$ and $D$ with cardinalities $|B_{i}|=b_{i}$ , $|C_{i}|=c_{i}$ , $|A|=a$ , and $|D|=d$ , for $1\leq i\leq k$ , respectively, such that between all pairs of cliques in $\{A,B_{1},\ldots,B_{k}\}$ there is a complete join, between all pairs of cliques in $\{D,C_{1},\ldots,C_{k}\}$ there is a complete join, and, for any $i\in\{1,\ldots,k\}$ , there is a complete join between the cliques $B_{i}$ and $C_{i}$ (and no further edges are allowed). The dashed lines in Figure 3 indicate that $k$ may be arbitrarily large. An expanded bull is a graph of the type depicted in Figure 4 with $a,b,d\geq 1$ and $c\geq 0$ . In both figures, pairs of lines indicate complete joins of the cliques.

Proposition 7 (Lock (2016); Andres and Lock (2019)).

Every expanded cocobi is $[B,-]$ -perfect.

Proposition 8 (Lock (2016); Andres and Lock (2019)).

Every expanded bull is $[B,-]$ -perfect.

1.3 The edge colouring game

An edge colouring game has the same rules as a vertex colouring game, except that the players have to colour uncoloured edges (instead of uncoloured vertices) such that adjacent edges receive distinct colours. And Alice wins if every edge (instead of vertex) is coloured in the end.

The game chromatic index $\chi_{g}^{\prime}(G)$ of $G$ is the smallest nonnegative integer $k$ such that Alice has a winning strategy for the edge colouring game played on $G$ with $k$ colours.

Thus, the edge colouring game on $G$ is equivalent to the vertex colouring game on the line graph $L(G)$ of $G$ ; and the game chromatic index and the game chromatic number are related by

\chi_{g}^{\prime}(G)=\chi_{g}(L(G)).

(1)

The edge colouring game was introduced by Lam et al. (1999) and Cai and Zhu (2001). Determining the maximum game chromatic index of some classes of graphs has been the subject of several papers (cf. Andres (2006); Andres et al. (2011); Bartnicki and Grytczuk (2008); Cai and Zhu (2001); Chan and Nong (2014); Charpentier et al. (2018); Fong and Chan (2019a, b); Fong et al. (2018); Lam et al. (1999)) as well as the game chromatic index of random graphs (cf. Beveridge et al. (2008); Keusch (2018)) as well as different types of edge-colouring based games (cf. Boudon et al. (2017); Dunn (2007); Dunn et al. (2015)).

Originally, in the edge colouring game Alice moves first and skipping is not allowed. However, we will distinguish here six variants as in the vertex colouring game. Namely, in the $[X,Y]$ -edge colouring game player $X$ has the first move and player $Y$ may skip moves (in case $Y\in\{A,B\}$ ) or none of the players is allowed to skip (in case $Y\in\{-\})$ . Its corresponding game chromatic index is denoted by $\chi_{[X,Y]}^{\prime}(G)$ .

1.4 Combining the setting: line game-perfect graphs

A graph $G$ is line $[X,Y]$ -perfect (or line game-perfect for the $[X,Y]$ -edge colouring game) if, for any edge-induced subgraph $H$ of $G$ ,

\chi_{[X,Y]}^{\prime}(H)=\omega(L(H)).

In this paper, we characterise line game-perfect graphs

•

for the games $[B,B]$ , $[A,B]$ , and $[A,-]$ (Theorem 12);
•

for game $[B,-]$ (Theorem 11);
•

for game $[B,A]$ (Theorem 10);
•

for game $[A,A]$ (Theorem 9).

1.5 Main results

Theorem 9.

The following are equivalent for a graph $G$ .

(1)

$G$ is line $[A,A]$ -perfect.
(2)

None of the following configurations (depicted in Figure 5) is an edge-induced subgraph of $G$ : $P_{6}$ , $C_{5}$ , mini lobster $F_{2}$ , trigraph $F_{3}$ , or two 3-caterpillars $F_{1}\cup F_{1}$ .
(3)

At most one component of $G$ is a full tree of type $E_{1}$ or a satellite of type $E_{2}$ , and every other component is a single galaxy, a double galaxy, a candy, a star book, a diamond of flowers, or a tetrahedron of flowers (described in Sections 5.3 and 5.4).

Theorem 10.

The following are equivalent for a graph $G$ .

(1)

$G$ is line $[B,A]$ -perfect.
(2)

None of the following configurations (depicted in Figure 6) is an edge-induced subgraph of $G$ : $P_{6}$ , $C_{5}$ , or 3-caterpillar $F_{1}$ .
(3)

Every component of $G$ is a single galaxy, a double galaxy, a candy, a star book, a diamond of flowers, or a tetrahedron of flowers (described in Sections 5.2 and 5.3).

Theorem 11.

The following are equivalent for a graph $G$ .

(1)

$G$ is line $[B,-]$ -perfect.
(2)

None of the following configurations (depicted in Figure 7) is an edge-induced subgraph of $G$ : $P_{5}\cup P_{2}$ , $C_{4}\cup P_{2}$ , $P_{6}$ , $C_{5}$ , bull, diamond, or 3-caterpillar $F_{1}$ .
(3)

Every component of $G$ is a double star, a vase of flowers, or an isolated vertex, or $G$ contains exactly one nontrivial component and this component is a double star, a vase of flowers, a candy, a shooting star, a double vase, or an amaryllis (described in Sections 5.1 and 5.2).

Theorem 12.

The following are equivalent for a graph $G$ .

(1)

$G$ is line $[B,B]$ -perfect.
(2)

$G$ is line $[A,B]$ -perfect.
(3)

$G$ is line $[A,-]$ -perfect.
(4)

None of the following configurations (depicted in Figure 8) is an edge-induced subgraph of $G$ : $P_{5}$ or $C_{4}$ .
(5)

Every component of $G$ is either a vase of flowers or a double star or an isolated vertex (described in Section 5.1).

1.6 Idea of the proof

In order to prove Theorem 9, first, in Section 4, we show that Bob has a winning strategy for the $[A,A]$ -edge colouring game played on each of the forbidden configurations, which proves the implication (1) $\Longrightarrow$ (2); then, in Section 5, we show that Alice has a winning strategy for the $[A,A]$ -edge colouring game played on each of the permitted types from (3) and, in Section 6, we show that the permitted types are hereditary (i.e., every edge-induced subgraph of such a permitted type is in one of the permitted types), which together proves the implication (3) $\Longrightarrow$ (1); finally, in Section 6, using Theorem 3 we prove the structural description (i.e., the permitted types are exactly those graphs that do not contain any of the forbidden configurations as an edge-induced subgraph), which settles the implication (2) $\Longrightarrow$ (3).

The proofs of Theorems 10, 11 and 12 have the same structure, however the structural implication (i.e., (2) $\Longrightarrow$ (3) in Theorem 10 and Theorem 11, respectively, (4) $\Longrightarrow$ (5) in Theorem 12) can be simplified by using the structural result from Theorem 9.

Furthermore, the other implications in Theorem 11 (respectively, Theorem 12) can be obtained in an easy way by using the structural results known for $[B,-]$ -perfect (respectively, $[A,-]$ -, $[A,B]$ - and $[B,B]$ -perfect) graphs, namely Theorem 5 and Propositions 7 and 8 (respectively, Theorem 4 and Theorem 6). The method for this last simplification will be described in Section 3.

1.7 Structure of this paper

In Section 2 we give some basic definitions and fix notation. A general idea to simplify the proofs concerning those games where a structural characterisation for game-perfectness is known is given in Section 3. In Section 4 we show that the forbidden configurations are not line game-perfect. In Section 5 we describe winning strategies for Alice on the permitted types for the different games. After these preparations, Section 6 is devoted to the proofs of the four main theorems. We conclude with an open question and a related problem in Section 7.

2 Preliminaries

We start by giving some definitions, easy observations and some results from the literature that we will use.

2.1 Notation

All graphs considered in this paper are simple, i.e., they contain neither loops nor multiple edges. Let $G$ be a graph. We denote by

•

${\mathbb{N}}:=\{0,1,2,3,\ldots\}$ the set of nonnegative integers;
•

$\Delta(G)$ the maximum degree of $G$ ;
•

$\omega(G)$ the clique number of $G$ ;
•

$L(G)$ the line graph of $G$ ;
•

$\chi^{\prime}(G)$ the chromatic index of $G$ ;
•

$\chi(G)$ the chromatic number of $G$ ;
•

$\chi_{[X,Y]}^{\prime}(G)$ the game chromatic index w.r.t. edge game $[X,Y]$ ;
•

$\chi_{[X,Y]}(G)$ the game chromatic number w.r.t. vertex game $[X,Y]$ .

Let $m,n\in{\mathbb{N}}$ . By $P_{n}$ ( $n\geq 1$ ), $C_{n}$ ( $n\geq 3$ ), $K_{n}$ , and $K_{m,n}$ , we denote the path, cycle and complete graph on $n$ vertices, and the complete bipartite graph with partite sets of $m$ and $n$ vertices, respectively.

Definition 13.

Let $G$ be a graph. An edge of $G$ is called unsafe if it is adjacent to at least $\omega(L(G))$ edges.

2.2 Basic observations

The different vertex colouring games are related as follows:

Observation 14 (Andres (2009)).

For any graph $G$ ,

	$\displaystyle\omega(G)\leq\chi(G)\leq\chi_{[A,A]}(G)\leq\chi_{[A,-]}(G)\leq\chi_{[A,B]}(G)\leq\chi_{[B,B]}(G)$
	$\displaystyle\omega(G)\leq\chi(G)\leq\chi_{[A,A]}(G)\leq\chi_{[B,A]}(G)\leq\chi_{[B,-]}(G)\leq\chi_{[B,B]}(G)$

The same holds for the edge colouring games:

Observation 15 (Andres (2006)).

For any graph $G$ ,

	$\displaystyle\omega(L(G))\leq\chi^{\prime}(G)\leq\chi_{[A,A]}^{\prime}(G)\leq\chi_{[A,-]}^{\prime}(G)\leq\chi_{[A,B]}^{\prime}(G)\leq\chi_{[B,B]}^{\prime}(G)$
	$\displaystyle\omega(L(G))\leq\chi^{\prime}(G)\leq\chi_{[A,A]}^{\prime}(G)\leq\chi_{[B,A]}^{\prime}(G)\leq\chi_{[B,-]}^{\prime}(G)\leq\chi_{[B,B]}^{\prime}(G)$

2.3 Basic definitions and observations

Recall that the line graph $L(G)$ of a graph $G=(V,E)$ is the graph $(E,E^{\prime})$ where, for any $e_{1},e_{2}\in E$ , $e_{1}e_{2}$ is an edge in $L(G)$ (i.e., $e_{1}e_{2}\in E^{\prime}$ ) if and only if the edges $e_{1}$ and $e_{2}$ are adjacent in $G$ .

Observation 16.

For any graph $G$ and any game $[X,Y]$ with $X\in\{A,B\}$ and $Y\in\{A,B,-\}$ , we have

	$\displaystyle\chi^{\prime}(G)$	$\displaystyle=$	$\displaystyle\chi(L(G)),$
	$\displaystyle\chi_{[X,Y]}^{\prime}(G)$	$\displaystyle=$	$\displaystyle\chi_{[X,Y]}(L(G)).$

Observation 16 implies the two following observations, which can be taken as alternative definitions of line perfect graphs and line game-perfect graphs, respectively.

Observation 17 (Trotter (1977)).

A graph $G$ is line perfect if $L(G)$ is perfect, i.e., for any vertex-induced subgraph $H^{\prime}$ of $L(G)$ ,

\chi(H^{\prime})=\omega(H^{\prime}).

Observation 18.

A graph $G$ is line $[X,Y]$ -perfect if $L(G)$ is $[X,Y]$ -perfect, i.e., for any vertex-induced subgraph $H^{\prime}$ of $L(G)$ ,

\chi_{[X,Y]}(H^{\prime})=\omega(H^{\prime}).

Let ${\cal LP}[X,Y]$ be the class of line $[X,Y]$ -perfect graphs and ${\cal LP}$ be the class of line perfect graphs. Then, by the definition of line perfect graphs and line game-perfect graphs, Observation 15 directly implies (or, alternatively, by Observation 17 and Observation 18, Observation 14 directly implies) the following.

Observation 19.

	$\displaystyle{\cal LP}[B,B]\subseteq{\cal LP}[A,B]\subseteq{\cal LP}[A,-]\subseteq{\cal LP}[A,A]\subseteq{\cal LP}$
	$\displaystyle{\cal LP}[B,B]\subseteq{\cal LP}[B,-]\subseteq{\cal LP}[B,A]\subseteq{\cal LP}[A,A]\subseteq{\cal LP}$

In particular, Observation 19 says that every line $[X,Y]$ -perfect graph is line perfect.

Using Theorem 1 and Observation 19 we get the following.

Corollary 20.

The classes of line $[X,Y]$ -perfect graphs are subclasses of the class of perfect graphs.

Definition 21.

A graph $G$ is line $[X,Y]$ -nice if

\chi_{[X,Y]}^{\prime}(G)=\omega(L(G)),

i.e., if Alice has a winning strategy with $\omega(L(G))$ colours for the $[X,Y]$ -edge colouring game played on $G$ .

The definition of line game-perfect graphs and Definition 21 have an obvious relation, given in Observation 22.

Observation 22.

A graph $G$ is line $[X,Y]$ -perfect if and only if each of its edge-induced subgraphs is line $[X,Y]$ -nice.

2.4 Characterisations of line graphs

The following well-known theorem will be used in our proofs.

Theorem 23 (Whitney (1932)).

Two connected nonempty graphs $G_{1}$ and $G_{2}$ are isomorphic if and only if their line graphs $L(G_{1})$ and $L(G_{2})$ are isomorphic, with the single exception of the two graphs $K_{3}$ and $K_{1,3}$ , which have the same line graph

L(K_{3})=L(K_{1,3})=K_{3}.

Corollary 24.

For any graph $G$ ,

{\omega(L(G))=\left\{\begin{array}[]{ll}3&\text{if}\ \Delta(G)=2\ \text{and}\ G\ \text{contains\ a\ component}\ K_{3}\\ 0&\text{if}\ G\ \text{is empty}\\ \Delta(G)&\text{otherwise}\end{array}\right.}

of Corollary 24.

Let $G$ be nonempty. By Theorem 23, cliques $K_{n}$ with $n\geq 1$ in $L(G)$ originate only from edge-induced stars $K_{1,n}$ or the $K_{3}$ in $G$ . Thus, either a star of maximum degree $\Delta(G)$ leads to the value of $\omega(L(G))$ or the three mutually adjacent edges in a $K_{3}$ . ∎

Using Observation 16 and Corollary 24, we may reformulate Definition 21 for a graph $G$ with maximum degree $\Delta(G)\geq 3$ as follows.

Observation 25.

A graph $G$ with $\Delta(G)\geq 3$ is line $[X,Y]$ -nice if

\chi_{[X,Y]}^{\prime}(G)=\Delta(G).

The precondition “nonempty” in Theorem 23 is essential as the line graphs of an isolated vertex $K_{1}$ and an empty graph $K_{0}$ are both the empty graph. Therefore, considering line graphs, it is convenient to exclude isolated vertices, which motivates the following definition.

Definition 26.

A graph is iso-free if it has no isolated vertices.

Beineke (1970) gave a characterisation of line graphs by forbidden induced subgraphs, which will be used in our proofs.

Theorem 27 (Beineke (1970)).

A graph $G$ is a line graph if and only if it contains none of the nine graphs $N_{1},\ldots,N_{9}$ from Figure 9 as an induced subgraph.

$N_{1}$ : claw

$N_{2}$ : $\overline{P_{2}\cup P_{3}}$

$N_{3}$ : $K_{5}-e$

$N_{4}$ :

$N5$ :

$N_{6}$ :

$N_{7}$ :

$N_{8}$ : triangular 3-ladder

$N_{9}$ : 5-wheel

Figure 9: The nine forbidden induced subgraphs for line graphs

3 A plan for characterising line game-perfect graphs

Let $g=[X,Y]$ with $(X,Y)\in\{A,B\}\times\{A,B,-\}$ .

•

For some games $g$ , we have a characterisation of game-perfect graphs by a list ${\cal F}_{g}$ of forbidden induced subgraphs.
•

Let red $({\cal F}_{g})$ be the maximal subset of ${\cal F}_{g}$ such that no graph in red $({\cal F}_{g})$ contains an induced $N_{1},\ldots,N_{9}$ .
•

Let $L^{-1}({\cal F}_{g})$ the set of all iso-free graphs $H$ such that $L(H)\in{\cal F}_{g}$ .
•

Let $L^{-1}({\rm red}({\cal F}_{g}))$ (which we call the reduced list) be the set of all iso-free graphs $H$ such that $L(H)\in{\rm red}({\cal F}_{g})$ .

Then we have following fundamental theorem (which gives us the basic idea how to characterise game-perfect line graphs).

Theorem 28.

The following are equivalent for a graph $G$ and a game $g=[X,Y]$ with $X\in\{A,B\}$ and $Y\in\{A,B,-\}$ .

(1)

$G$ is line $g$ -perfect.
(2)

No graph in $L^{-1}({\cal F}_{g})$ is an edge-induced subgraph of $G$ .
(3)

No graph in $L^{-1}({\rm red}({\cal F}_{g}))$ is an edge-induced subgraph of $G$ .

Proof.

(1) $\Longrightarrow$ (2): Let $G$ be a line $g$ -perfect graph. Then $U:=L(G)$ is $g$ -game-perfect. By the characterisation of (vertex) $g$ -perfectness (e.g., by Theorem 4 or Theorem 5) $U$ does not contain a graph from the list ${\cal F}_{g}$ as an induced subgraph. That means that $G$ does not contain a graph from the list $L^{-1}({\cal F}_{g})$ as an edge-induced subgraph.

(2) $\Longrightarrow$ (1): Let $G$ not contain any graph from the list $L^{-1}({\cal F}_{g})$ as an edge-induced subgraph. Then $U:=L(G)$ does not contain any graph from the list ${\cal F}_{g}$ as an induced subgraph. By the characterisation of $g$ -perfect graphs (e.g., by Theorem 4 or Theorem 5), this means that $U$ is $g$ -game-perfect. By definition this means that $G$ is line $g$ -perfect.

(2) $\Longrightarrow$ (3): holds trivially.

(3) $\Longrightarrow$ (2): Let $H\in L^{-1}({\cal F}_{g})$ . Then there is a graph $F\in{\cal F}_{g}$ with $F=L(H)$ . Since $F$ is a line graph, by Theorem 27 $F$ does not contain any of the forbidden configurations $N_{1},\ldots,N_{9}$ as an induced subgraph. Thus $F\in{\rm red}({\cal F}_{g})$ . Thus

H\in L^{-1}({\rm red}({\cal F}_{g})).

∎

General strategy to characterise $g$ -game line perfect graphs.

We do the following steps

1.

Determine ${\cal F}_{g}$ (known from literature for 4 games):
2.

Determine red $({\cal F}_{g})$ .
3.

Determine $L^{-1}({\rm red}({\cal F}_{g}))$ .
4.

Characterise the class of graph which do not contain any member of $L^{-1}({\rm red}({\cal F}_{g}))$ as an edge-induced subgraph.

The above idea is used for the proofs of Theorem 12 and Theorem 11. In Theorem 10 and Theorem 9 we use different methods since, for the games $[B,A]$ and $[A,A]$ , no explicit characterisation of the game-perfect graphs is known.

4 The forbidden subgraphs

4.1 Forbidden subgraphs for game $[A,-]$

The following basic lemma is implied by Theorem 23.

Lemma 29.

We have:

•

$P_{5}$ is the only iso-free graph whose line graph is $P_{4}$ .
•

$C_{4}$ is the only iso-free graph whose line graph is $C_{4}$ .

From the lemma above we conclude the following.

Proposition 30.

A graph is line $[A,-]$ -perfect if and only if it contains no $P_{5}$ or $C_{4}$ as an edge-induced subgraph.

Proof.

Let $G$ be a graph. By Theorem 28, the graph $G$ is line $[A,-]$ -perfect if and only if no graph in the reduced list $L^{-1}({\rm red}({\cal F}_{[A,-]}))$ is an edge-induced subgraph of $G$ . Thus, it is sufficient to prove that

L^{-1}({\rm red}({\cal F}_{[A,-]}))=\{P_{5},C_{4}\}.

By Theorem 4 we know that ${\cal F}_{[A,-]}$ consists of the seven graphs depicted in Figure 1.

Since $N_{1}$ is an induced subgraph of the split 3-star and of the double fan, it is an induced subgraph of the triangle star, the $\Xi$ -graph, the two split 3-stars, the two double fans, and the mixed graph. Thus we have

{\rm red}({\cal F}_{[A,-]})=\{P_{4},C_{4}\}

Since, by Lemma 29, the only iso-free graph whose line graph is $P_{4}$ is the $P_{5}$ , and the only iso-free graph whose line graph is $C_{4}$ is the $C_{4}$ , we have

L^{-1}({\rm red}({\cal F}_{[A,-]}))=\{P_{5},C_{4}\}.

∎

4.2 Forbidden subgraphs for game $[B,-]$

We obtain the following characterisation of line $[B,-]$ -perfect graphs.

Proposition 31.

A graph is line $[B,-]$ -perfect if and only if it contains no $P_{5}\cup P_{2}$ , $C_{4}\cup P_{2}$ , $P_{6}$ , $C_{5}$ , bull, diamond, or 3-caterpillar $F_{1}$ as an edge-induced subgraph.

Proof.

Let $G$ be a graph . By Theorem 28, $G$ is line $[B,-]$ -perfect if and only if no graph in the reduced list $L^{-1}({\rm red}({\cal F}_{[B,-]}))$ is an edge-induced subgraph of $G$ . Thus, to finish the proof it is sufficient to show that the reduced list $L^{-1}({\rm red}({\cal F}_{[B,-]}))$ consists of the forbidden graphs mentioned in the proposition.

By Theorem 5 we know that ${\cal F}_{[B,-]}$ consists of the 15 graphs depicted in Figure 2.

Since $N_{1}$ is an induced subgraph of the chair, the split 3-star, the double fan, the $F_{10}$ , the $F_{12}$ , the $F_{13}$ , the $F_{14}$ , and the $F_{15}$ , we have

{\rm red}({\cal F}_{[B,-]})=\{P_{4}\cup K_{1},C_{4}\cup K_{1},P_{5},C_{5},\text{4-fan},\text{4-wheel},F_{11}\}.

Furthermore, the following observations are implied by Theorem 23.

•

$P_{5}\cup P_{2}$ is the only iso-free graph whose line graph is $P_{4}\cup K_{1}$ .
•

$C_{4}\cup P_{2}$ is the only iso-free graph whose line graph is $C_{4}\cup K_{1}$ .
•

$P_{6}$ is the only iso-free graph whose line graph is $P_{5}$ .
•

$C_{5}$ is the only iso-free graph whose line graph is $C_{5}$ .
•

The bull is the only iso-free graph whose line graph is the 4-fan.
•

The diamond is the only iso-free graph whose line graph is the 4-wheel.
•

The 3-caterpillar $F_{1}$ is the only iso-free graph whose line graph is the graph $F_{11}$ depicted in Figure 2.

By these observations we conclude that

L^{-1}({\rm red}({\cal F}_{[B,-]}))=\{P_{5}\cup P_{2},C_{4}\cup P_{2},P_{6},C_{5},\text{bull},\text{diamond},\text{3-caterpillar}\}.

∎

4.3 Forbidden subgraphs for game $[B,A]$

The next lemma is an auxiliary result that will be used to simplify some strategies in the forthcoming Lemma 33, Lemma 36, and Lemma 39.

Figure 10: The precoloured configuration

F_{1}^{1}

: the middle edge is precoloured by colour 1.

Lemma 32.

Bob has a winning strategy with 3 colours in the $[X,A]$ -edge colouring game on the precoloured graph $F_{1}^{1}$ where the middle edge is precoloured by colour 1 (depicted in Figure 10) if it is Alice’s turn.

Proof.

Assume the colour set is $\{1,2,3\}$ . By symmetry, Alice has four possible types of moves: she can colour $e_{1}$ with colour 2, she can colour $f_{1,1}$ with colour 2 or with colour 1, or she can miss her turn.

•

If Alice colours $e_{1}$ with colour 2, Bob colours $f_{2,2}$ with colour 3. Then there is no feasible colour for $e_{2}$ any more.
•

If Alice colours $f_{1,1}$ with colour 2, Bob colours $f_{1,2}$ with colour 3. Then there is no feasible colour for $e_{1}$ any more.
•

If Alice colours $f_{1,1}$ with colour 1 or skips, then Bob colours $f_{2,1}$ with colour 2. If Bob will be able to colour $f_{2,2}$ or $e_{1}$ with colour 3 in his next move, he will win, since there would be no feasible colour for $e_{2}$ in both cases. In order to avoid both threats simultaneously, Alice has only one possibility: she must colour $e_{2}$ with colour 3. But then Bob colours $f_{1,2}$ with colour 2, so that there is no feasible colour for $e_{1}$ any more.

Thus, in any case, Bob will win. ∎

Lemma 33.

The 3-caterpillar is not line $[B,A]$ -nice.

Proof.

Bob’s winning strategy with 3 colours on the 3-caterpillar is to colour the central leaf edge $e_{0}$ (see Figure 14) with colour 1 in his first move. Then we have the situation from Figure 10. Thus Bob wins by Lemma 32. ∎

4.4 Forbidden subgraphs for game $[A,A]$

The first two of the following lemmata are trivial. We list them for the sake of completeness.

Lemma 34.

The graph $P_{6}$ is not line $[A,A]$ -nice.

Proof.

We describe a winning strategy with 2 colours for Bob in the $[A,A]$ -edge colouring game on the path $P_{6}$ .

If Alice colours an edge in her first move, then Bob colours an edge at distance 1 with the other colour, and the mutual adjacent edge of these two edges cannot be coloured with any of the two colours.

Otherwise, if Alice misses her first turn, then Bob’s winning strategy with 2 colours on the $P_{6}$ is to colour the central edge $e$ in colour 1 in his first move and one of the leaf edges with colour 2 in his second move. Bob can colour at least one such leaf edge $f$ , since Alice has coloured at most one edge. Then the mutual adjacent edge of the two edges $e$ and $f$ cannot be coloured, and Bob wins.

Thus the $P_{6}$ is not line $[A,A]$ -nice. ∎

Lemma 35.

The graph $C_{5}$ is not line $[A,A]$ -nice.

Proof.

The $C_{5}$ (is the smallest graph that) is not line perfect, thus it is not line $[A,A]$ -nice. ∎

Figure 11: The mini lobster

F_{2}

Lemma 36.

The mini lobster $F_{2}$ is not line $[A,A]$ -nice.

Proof.

By exhausting all possible first moves of Alice we show that Bob has a winning strategy with 3 colours for the $[A,A]$ -edge colouring game played on $F_{2}$ . We use the edge labels from Figure 11. By symmetry, it is sufficient to consider the cases that Alice colours $f_{0}$ , $e_{0}$ , $f_{1,1}$ , or $e_{2}$ in her first move, or skips her first turn.

•

If Alice skips or colours $f_{0}$ , then Bob colours $e_{0}$ and thus creates a configuration $F_{1}^{1}$ . In the same way, if Alice colours $e_{0}$ , then Bob colours $f_{0}$ and creates a configuration $F_{1}^{1}$ . In both cases, by Lemma 32, Bob will win. (Note that in case Alice colours $f_{0}$ in a forthcoming move, this may be considered as skipping her turn in the situation of Lemma 32.)
•

If Alice colours $f_{1,1}$ (w.l.o.g. with colour 1), then Bob colours $e_{2}$ with colour 2. On the other hand, if Alice colours $e_{2}$ (w.l.o.g. with colour 2), then Bob colours $f_{1,1}$ with colour 1. In both cases, if Bob will be able to colour $f_{1,2}$ or $e_{0}$ with colour 3 in his next move, then he would win as there would be no feasible colour for $e_{1}$ any more. The only possibility for Alice to avoid both threats simultaneously is to colour $e_{1}$ with colour 3. But then Bob colours $f_{0}$ with colour 1, so that there is no feasible colour for $e_{0}$ any more.

In any case, Bob wins. ∎

Figure 12: The precoloured configuration

F_{3}^{1}

The next lemma is an auxiliary result that will be used to simplify some strategies in the forthcoming Lemma 38.

Lemma 37.

Bob has a winning strategy with 4 colours in the $[X,A]$ -edge colouring game on the precoloured graph $F_{3}^{1}$ (depicted in Figure 12) if it is Alice’s turn.

Proof.

Assume the colour set is $\{1,2,3,4\}$ . By symmetry, Alice has six possible types of moves: she can miss her turn, colour $f_{1,1}$ with colour 1 or with colour 3, she can colour $e_{2}$ with colour 3, or she can colour $f_{0}$ with colour 2 or with colour 3.

•

If Alice misses her turn or colours $f_{1,1}$ (with colour 1 or colour 3), then Bob colours $f_{0}$ with colour 3. After that only colour 4 is feasible for $e_{1}$ and $e_{2}$ , which can be used only for one the these edges.
•

If Alice colours $e_{2}$ or $f_{0}$ with colour 3, Bob colours $f_{1,1}$ with colour 4. Then there is no feasible colour for $e_{1}$ .
•

If Alice colours $f_{0}$ with colour 2, Bob colours $f_{1,1}$ with colour 3. If Bob will be able to colour $f_{1,2}$ or $e_{2}$ with colour 4 in his next move, he will win, since there would be no feasible colour for $e_{1}$ in both cases. In order to avoid both threats simultaneously, Alice has only one possibility: she must colour $e_{1}$ with colour 4. But then Bob colours $f_{2,1}$ with colour 3, so that there is no feasible colour for $e_{2}$ any more.

Thus, in any case, Bob will win. ∎

Figure 13: The trigraph

F_{3}

Lemma 38.

The trigraph $F_{3}$ is not line $[A,A]$ -nice.

Proof.

We describe a winning strategy for Bob on $F_{3}$ with colour set $\{1,2,3,4\}$ . We use the edge labels from Figure 13. Due to symmetry, Alice has three possibilities for her first move: She can colour $e_{0}$ or $f_{0,1}$ with colour 1 or miss her turn.

If Alice colours $e_{0}$ with colour 1, then Bob colours $f_{0,1}$ with colour 2. And, vice-versa, if Alice colours $f_{0,1}$ with colour 1, then Bob colours $e_{0}$ with colour 2. In both cases (by considering the coloured edge $e_{0}$ broken in two parts) we get the precoloured configuration $F_{3}^{1}$ from Figure 12. By Lemma 37, Bob wins.

If Alice misses her turn, then Bob colours $f_{0,1}$ with colour 1. Now, by symmetry, Alice has seven possibilities for her second move: she may miss her turn, colour $e_{0}$ with colour 1 or with colour 2, colour $f_{0,2}$ with colour 2, colour $e_{1}$ with colour 2, or colour $f_{1,1}$ with colour 2 or with colour 1. We make a case distinction according to Alice’s second move.

•

If Alice misses her turn, then Bob colours $e_{0}$ with colour 2. Again, we have a situation as in configuration $F_{3}^{1}$ , and, by Lemma 37, Bob wins.
•

If Alice colours $e_{0}$ with colour 1, then this colour is forbidden for every uncoloured edge. The uncoloured edges form a 3-caterpillar $F_{1}$ and the game is reduced to the $[B,A]$ -edge colouring game with three colours (2,3,4) on $F_{1}$ . Therefore, Bob wins by Lemma 33.
•

If Alice colours $e_{0}$ with colour 2, Bob colours $f_{0,2}$ with colour 3. And, vice-versa, if Alice colours $f_{0,2}$ with colour 2, Bob colours $e_{0}$ with colour 3. In both cases the only feasible colour remaining for $e_{1}$ and $e_{2}$ is colour 4, which cannot be assigned to both edges.
•

If Alice colours $e_{1}$ with colour 2, then Bob colours $f_{2,1}$ with colour 3. If Bob will be able to colour $f_{0,2}$ or $f_{2,2}$ with colour 4 in his next move, he will win as $e_{2}$ has no feasible colour. The only possible move of Alice to avoid both threats is to colour $e_{2}$ with colour 4. But then Bob colours $f_{1,1}$ with colour 1 and there is no feasible colour for $e_{0}$ any more.
•

If Alice colours $f_{1,1}$ with colour 2, then Bob colours $f_{1,2}$ with colour 3. If Bob will be able to colour $e_{0}$ or $f_{0,2}$ with colour 4 in his next move, he will win as $e_{1}$ has no feasible colour. The only possible move of Alice to avoid both threats is to colour $e_{1}$ with colour 4. But then Bob colours $f_{2,1}$ with colour 1 and there is no feasible colour for $e_{0}$ any more.
•

If Alice colours $f_{1,1}$ with colour 1, then Bob colours $e_{1}$ with colour 2. If Bob will be able to colour $f_{2,1}$ or $f_{2,2}$ with colour 3 in his next move, he will win as the only feasible colour for the edges $e_{0}$ and $e_{2}$ will be colour 4, which can not be used for both edges. The only possible moves of Alice to avoid both threats are to colour $e_{0}$ or $e_{2}$ with colour 3. By symmetry, we may assume that Alice colours $e_{0}$ with colour 3. But then Bob colours $f_{2,1}$ with colour 4 and there is no feasible colour for $e_{2}$ any more.

Thus, in any case, Bob wins. ∎

Figure 14: The 3-caterpillar

F_{1}

Lemma 39.

The graph $F_{1}\cup F_{1}$ is not line $[A,A]$ -nice.

Proof.

We describe a winning strategy for Bob with 3 colours in the $[A,A]$ -edge colouring game played on a graph $F_{1}\cup F_{1}$ consisting of two components that are 3-caterpillars. No matter what Alice does in her first move, Bob is able to choose a component where every edge is uncoloured. Bob colours the edge $e_{0}$ (see Figure 14) in this component and then, by playing always in this component, he has a winning strategy by Lemma 32. ∎

5 The permitted types

5.1 Permitted for game $[B,B]$

We start with some definitions.

Definition 40 (vase of flowers).

Let $n\in{\mathbb{N}}$ . A vase of $n$ flowers is a graph consisting of a $C_{3}$ and $n$ vertices of degree 1 that are adjacent with the same vertex of the $C_{3}$ , i.e., the graph has the vertex set

\{w_{1},w_{2},w_{3},v_{1},v_{2},\ldots,v_{n}\}

and the edge set

\{w_{1}w_{2},w_{1}w_{3},w_{2}w_{3}\}\cup\{w_{1}v_{i}\mid 1\leq i\leq n\}.

A vase of flowers is a vase of $n$ flowers for some $n\in{\mathbb{N}}$ . A vase of 1 flower is often called a paw, and a vase of 2 flowers is sometimes called a cricket.

Definition 41 (double star).

Let $m,n\in{\mathbb{N}}$ . An $(m,n)$ -double star is a graph formed by an $m$ -star and an $n$ -star by connecting the centres of the stars by an additional edge, i.e., the graph has the vertex set

\{w_{1},w_{2},u_{1},u_{2},\ldots,u_{m},v_{1},v_{2},\ldots,v_{n}\}

an the edge set

\{w_{1}w_{2}\}\cup\{w_{1}u_{i}\mid 1\leq i\leq m\}\cup\{w_{2}v_{i}\mid 1\leq i\leq n\}.

A double star is an $(m,n)$ -double star for some $m,n\in{\mathbb{N}}$ . The $(0,0)$ -double star is the complete graph $K_{2}$ .

In order to prove the theorem, we start with some lemmata.

Lemma 42.

Graphs whose components are vases of flowers, double stars, or isolated vertices are line $[B,B]$ -perfect.

Proof.

Let $G$ be a graph whose components are vases of flowers, double stars, or isolated vertices. The line graph of a vase of $n$ flowers is an ear animal with $k=0$ , $a=b=1$ , and $c=n$ . The line graph of an $(m,n)$ -double star is an ear animal with $k=2$ , $a=b=c=0$ , $d_{1}=m$ , and $d_{2}=n$ . The line graph of an isolated vertex is the empty graph $K_{0}$ and can thus be ignored. Thus, the line graph $L(G)$ of $G$ is a graph each of whose components is an ear animal. Therefore, by Theorem 6, $L(G)$ is $[B,B]$ -perfect. By the definition of line game-perfectness this means that $G$ is line $[B,B]$ -perfect. ∎

5.2 Permitted for game $[B,-]$

We start with some definitions.

Definition 43 (candy).

Let $m,n_{1},n_{2}\in{\mathbb{N}}$ and $m\geq 1$ . An $(m,n_{1},n_{2})$ -candy is a graph consisting of a $K_{2,m}$ and $n_{1}$ vertices of degree 1 that are adjacent to a vertex $v_{1}$ of degree $m$ of the $K_{2,m}$ and $n_{2}$ vertices of degree 1 that are adjacent to the vertex $v_{2}$ at distance 2 from $v_{1}$ , i.e., the graph has the vertex set

\{v_{1},v_{2}\}\cup\{w_{i}\mid 1\leq i\leq m\}\cup\{x_{j}\mid 1\leq j\leq n_{1}\}\cup\{y_{j}\mid 1\leq j\leq n_{2}\}

and the edge set

\{v_{1}w_{i},w_{i}v_{2}\mid 1\leq i\leq m\}\cup\{x_{j}v_{1}\mid 1\leq j\leq n_{1}\}\cup\{v_{2}y_{j}\mid 1\leq j\leq n_{2}\}.

A candy is an $(m,n_{1},n_{2})$ -candy and an empty candy is a $(1,n_{1},n_{2})$ -candy for some $m,n_{1},n_{2}\in{\mathbb{N}}$ .

Definition 44 (shooting star).

Let $m,n\in{\mathbb{N}}$ . An $(m,n)$ -shooting star is a graph formed by a central vertex $v$ with $n$ adjacent vertices of degree 1 and a pending $P_{3}$ and another adjacent vertex $w$ that is adjacent to $m$ vertices of degree 1, i.e., the graph has the vertex set

\{v,w,a,b\}\cup\{x_{i}\mid 1\leq i\leq m\}\cup\{y_{j}\mid 1\leq j\leq n\}

and the edge set

\{wv,va,ab\}\cup\{wx_{i}\mid 1\leq i\leq m\}\cup\{vy_{j}\mid 1\leq j\leq n\}.

A shooting star is an $(m,n)$ -shooting star for some $m,n\in{\mathbb{N}}$ .

Definition 45 (double vase).

Let $n\in{\mathbb{N}}$ . A double vase of $n$ flowers is a graph formed by a central vertex $v$ with $n$ adjacent vertices of degree 1 and two pending triangles, i.e., the graph has the vertex set

\{v,x_{1},x_{2},y_{1},y_{2}\}\cup\{w_{j}\mid 1\leq j\leq n\}

and the edge set

\{vx_{1},x_{1}x_{2},x_{2}v,vy_{1},y_{1}y_{2},y_{2}v\}\cup\{vw_{j}\mid 1\leq j\leq n\}.

A double vase is a double vase of $n$ flowers for some $n\in{\mathbb{N}}$ ; if $n=0$ , it is a 2-windmill.

Definition 46 (amaryllis).

Let $m,n\in{\mathbb{N}}$ . An $(m,n)$ -amaryllis is a graph formed by a central vertex $v$ with $n$ adjacent vertices of degree 1 and a pending triangle and another adjacent vertex $w$ that is adjacent to $m$ vertices of degree 1, i.e., the graph has the vertex set

\{v,w,c_{1},c_{2}\}\cup\{x_{i}\mid 1\leq i\leq m\}\cup\{y_{j}\mid 1\leq j\leq n\}

and the edge set

\{wv,vc_{1},c_{1}c_{2},c_{2}v\}\cup\{wx_{i}\mid 1\leq i\leq m\}\cup\{vy_{j}\mid 1\leq j\leq n\}.

An amaryllis is an $(m,n)$ -amaryllis for some $m,n\in{\mathbb{N}}$ ; if $m=0$ , it is a vase of $n+1$ flowers.

We prove first that Alice wins the $[B,-]$ -colouring game with $\omega(L(G))$ colours on the configurations $G$ needed for Theorem 11. In the proofs we refer to the notation given above.

A component of a graph is nontrivial if it contains an edge.

Lemma 47.

Graphs whose single nontrivial component is a candy are line $[B,-]$ -nice.

Proof.

Let $G$ be a graph that consists of a $(m,n_{1},n_{2})$ -candy ( $m\geq 1$ ) and possibly some isolated vertices. Then the line graph $L(G)$ of $G$ is an expanded cocobi with $a=n_{1}$ , $d=n_{2}$ , $k=m$ , $b_{1},\ldots,b_{k}=1$ , and $c_{1},\ldots,c_{k}=1$ . Therefore, by Proposition 7, the line graph $L(G)$ is $[B,-]$ -perfect. Thus $G$ is line $[B,-]$ -perfect. ∎

We will use Lemma 47 not only for the proof of Theorem 11, but also for the proofs of Theorem 10 and Theorem 9. Note that the proof given above relies on the results by Lock (2016) and Andres and Lock (2019).

Lemma 48.

Graphs whose single nontrivial component is a shooting star are line $[B,-]$ -nice.

Proof.

Let $G$ be a graph that consists of a $(m,n)$ -shooting star and possibly some isolated vertices. Then the line graph $L(G)$ of $G$ is an expanded bull with $a=m$ , $b=d=1$ , and $c=n$ . Therefore, by Proposition 8, the line graph $L(G)$ is $[B,-]$ -perfect. Thus $G$ is line $[B,-]$ -perfect. ∎

Lemma 49.

Graphs whose single nontrivial component is a double vase are line $[B,-]$ -nice.

Proof.

Let $G$ be a graph that consists of a double vase of $n$ flowers and possibly some isolated vertices. Then the line graph $L(G)$ of $G$ is an expanded bull with $a=1$ , $b=d=2$ , and $c=n$ . Therefore, by Proposition 8, the line graph $L(G)$ is $[B,-]$ -perfect. Thus $G$ is line $[B,-]$ -perfect. ∎

Lemma 50.

Graphs whose single nontrivial component is an amaryllis are $[B,-]$ -nice.

Proof.

Let $G$ be a graph that consists of an $(m,n)$ -amaryllis and possibly some isolated vertices. Then the line graph $L(G)$ of $G$ is an expanded bull with $a=m$ , $b=1$ , $c=n$ , and $d=2$ . Therefore, by Proposition 8, the line graph $L(G)$ is $[B,-]$ -perfect. Thus $G$ is line $[B,-]$ -perfect. ∎

5.3 Permitted for game $[B,A]$

Definition 51 (star book).

Let $m,n_{1},n_{2}\in{\mathbb{N}}$ and $m\geq 1$ . An $(m,n_{1},n_{2})$ -star book is a graph consisting of a $K_{2,m}$ and $n_{1}$ vertices of degree 1 that are adjacent to a vertex $v_{1}$ of degree $m$ of the $K_{2,m}$ and $n_{2}$ vertices of degree 1 that are adjacent to the vertex $v_{2}$ at distance 2 from $v_{1}$ , furthermore there is an additional edge $v_{1}v_{2}$ , i.e., the graph has the vertex set

\{v_{1},v_{2}\}\cup\{w_{i}\mid 1\leq i\leq m\}\cup\{x_{j}\mid 1\leq j\leq n_{1}\}\cup\{y_{j}\mid 1\leq j\leq n_{2}\}

and the edge set

\{v_{1}v_{2}\}\cup\{v_{1}w_{i},w_{i}v_{2}\mid 1\leq i\leq m\}\cup\{x_{j}v_{1}\mid 1\leq j\leq n_{1}\}\cup\{v_{2}y_{j}\mid 1\leq j\leq n_{2}\}.

A star book is an $(m,n_{1},n_{2})$ -star book for some $m,n_{1},n_{2}\in{\mathbb{N}}$ . Furthermore, a star book with $m$ book sheets is an $(m,n_{1},n_{2})$ -star book for some $n_{1},n_{2}\in{\mathbb{N}}$ .

Thus, a star book is like a candy, but with an additional edge $v_{1}v_{2}$ .

Definition 52 (diamond of flowers).

Let $n\in{\mathbb{N}}$ . A diamond of $n$ flowers is constructed from a diamond by attaching $n$ leaves to a vertex $v$ of degree 2, i.e., the graph has the vertex set

\{v,u_{1},u_{2},w\}\cup\{x_{j}\mid 1\leq j\leq n\}

and the edge set

\{vu_{1},vu_{2},u_{1}u_{2},wu_{1},wu_{2}\}\cup\{vx_{j}\mid 1\leq j\leq n\}.

A diamond of flowers is a diamond of $n$ flowers for some $n\in{\mathbb{N}}$ .

Definition 53 (tetrahedron of flowers).

Let $n\in{\mathbb{N}}$ . A tetrahedron of $n$ flowers is constructed from a $K_{4}$ by attaching $n$ leaves to one of its vertices, i.e., the graph has the vertex set

\{v,u_{1},u_{2},u_{3}\}\cup\{x_{j}\mid 1\leq j\leq n\}

and the edge set

\{vu_{1},vu_{2},vu_{3},u_{1}u_{2},u_{1}u_{3},u_{2}u_{3}\}\cup\{vx_{j}\mid 1\leq j\leq n\}.

A tetrahedron of flowers is a tetrahedron of $n$ flowers for some $n\in{\mathbb{N}}$ .

Definition 54 (single galaxy).

Let $k,\ell\in{\mathbb{N}}$ . A $(k,\ell)$ -single galaxy consists of a central vertex $v$ and $k$ pending triangles and $\ell$ pending $P_{3}$ , i.e., the graph has the vertex set

\{v\}\cup\{c_{s},d_{s}\mid 1\leq s\leq k\}\cup\{x_{t},y_{t}\mid 1\leq t\leq\ell\}

and the edge set

\{vc_{s},vd_{s},c_{s}d_{s}\mid 1\leq s\leq k\}\cup\{vx_{t},x_{t}y_{t}\mid 1\leq t\leq\ell\}.

A single galaxy is a $(k,\ell)$ -single galaxy for some $k,\ell\in{\mathbb{N}}$ .

Note that a $(0,0)$ -single galaxy is an isolated vertex.

Definition 55 (double galaxy).

Let $k,\ell,m,n\in{\mathbb{N}}$ . A $(k,\ell,m,n)$ -double galaxy consists of a central vertex $v$ and $k$ pending triangles, $\ell$ pending $P_{3}$ , a pending $(m+1)$ -star, and $n$ pending $P_{2}$ , i.e., the graph has the vertex set

			$\displaystyle\{v,z\}\cup\{c_{s},d_{s}\mid 1\leq s\leq k\}\cup\{x_{t},y_{t}\mid 1\leq t\leq\ell\}$
		$\displaystyle\cup$	$\displaystyle\{u_{i}\mid 1\leq i\leq m\}\cup\{w_{j}\mid 1\leq j\leq n\}$

and the edge set

			$\displaystyle\{vz\}\cup\{vc_{s},vd_{s},c_{s}d_{s}\mid 1\leq s\leq k\}\cup\{vx_{t},x_{t}y_{t}\mid 1\leq t\leq\ell\}$
		$\displaystyle\cup$	$\displaystyle\{zu_{i}\mid 1\leq i\leq m\}\cup\{vw_{j}\mid 1\leq j\leq n\}$

A double galaxy is a $(k,\ell,m,n)$ -double galaxy for some $k,\ell,m,n\in{\mathbb{N}}$ .

Note that a $(0,0,m,n)$ -double galaxy is a double star.

Lemma 56.

A star book is line $[B,A]$ -nice.

Proof.

A triangle is line $[B,A]$ -nice, trivially. We describe a winning strategy for Alice in the $[B,A]$ -edge colouring game played on a star book $S$ that is not a triangle with

c=\max\{m+n_{1}+1,m+n_{2}+1\}

colours. We use the vertex labels from Definition 51.

Whenever Bob does not colour the universal edge $v_{1}v_{2}$ , then Alice follows her winning strategy for the candy $S-v_{1}v_{2}$ with $c-1$ colours, which exists by Lemma 47. If Bob colours $v_{1}v_{2}$ , then Alice misses her turn. After that she uses again her strategy for the candy $S-v_{1}v_{2}$ . This strategy is feasible since the colour of $v_{1}v_{2}$ cannot be used on any other edge, since $v_{1}v_{2}$ is adjacent to every other edge. ∎

We remark that the same strategy shows that a star book is line $[A,-]$ -nice. Namely, Alice should colour $v_{1}v_{2}$ in her first move in the edge colouring game $[A,-]$ . However, it is not line $[A,-]$ -perfect (except in the trivial case when it is a vase of flowers) since it contains a $P_{5}$ or a $C_{4}$ , which are forbidden configurations for the edge colouring game $[A,-]$ .

Lemma 57.

A diamond of flowers is line $[B,A]$ -nice.

Proof.

Let $D_{n}$ be a diamond of $n$ flowers with the vertex labels from Definition 52. We describe a winning strategy for Alice with $c:=\max\{3,n+2\}$ colours for the $[B,A]$ -edge colouring game played on $D_{n}$ . Consider Bob’s first move.

•

If Bob colours $u_{1}u_{2}$ , then, if $n\geq 1$ , Alice colours $e=vx_{1}$ with the same colour, and if $n=0$ , she misses her turn. And vice-versa, if Bob colours a star edge $e=vx_{j}$ , then Alice colours $u_{1}u_{2}$ with the same colour. In all cases this colour may not be used for any other edge. Therefore, after that, Alice may follow her winning strategy with $c-1$ colours for the $[B,-]$ -edge colouring game played on the candy $D_{n}-\{u_{1}u_{2},e\}$ , which exists by Lemma 47.
•

If Bob colours $vu_{i}$ for some $i\in\{1,2\}$ , then Alice colours $wu_{3-i}$ with the same colour, and vice-versa. In any case, this colour may not be used for any other edge. Thus, after that, Alice may follow her winning strategy for the $[B,-]$ -edge colouring game with $c-1$ colours played on the shooting star $D_{n}-\{vu_{i},wu_{3-i}\}$ , which exists by Lemma 48.

Thus, in any case, Alice wins. ∎

The next lemma is very similar to the preceeding one.

Lemma 58.

A tetrahedron of flowers is line $[B,A]$ -nice.

Proof.

Let $T_{n}$ be a tetrahedron of $n$ flowers with the vertex labels from Definition 53. We describe a winning strategy for Alice with $c:=n+3$ colours for the $[B,A]$ -edge colouring game played on $T_{n}$ . Consider again Bob’s first move.

•

If Bob colours $u_{1}u_{2}$ , then Alice colours $vu_{3}$ with the same colour and vice-versa. In all cases this colour may not be used for any other edge. Therefore, after that, Alice may follow her winning strategy with $c-1$ colours for the $[B,-]$ -edge colouring game played on the candy $T_{n}-\{u_{1}u_{2},vu_{3}\}$ , which exists by Lemma 47.
•

If Bob colours $vu_{i}$ for some $i\in\{1,2\}$ , then Alice colours $u_{3}u_{3-i}$ with the same colour, and vice-versa. In any case, this colour may not be used for any other edge. Thus, after that, Alice may follow her winning strategy for the $[B,-]$ -edge colouring game with $c-1$ colours played on the candy $T_{n}-\{vu_{i},u_{3}u_{3-i}\}$ , which exists by Lemma 47.
•

If Bob colours a star edge $vx_{i}$ for some $i\in{\mathbb{N}}$ with $1\leq i\leq n$ , then Alice colours $u_{1}u_{2}$ with the same colour. This colour may not be used for any other edge. Thus, after that, Alice may follow her winning strategy for the $[B,A]$ -edge colouring game with $c-1$ colours played on the star book $T_{n}-\{vx_{i},u_{1}u_{2}\}$ , which exists by Lemma 56.

Thus, in any case, Alice wins. ∎

A $P_{3}$ is pending at a vertex $v$ of a graph $G$ if the $P_{3}$ is an induced subgraph of $G$ , and $v$ is a vertex of degree 1 in the $P_{3}$ , and, if $v$ is deleted, the two other vertices of the $P_{3}$ are disconnected with the vertices of $G-v$ that are not in the $P_{3}$ . Analoguously, a triangle is pending at a vertex $v$ of a graph $G$ if the triangle is an induced subgraph of $G$ , and $v$ is one of the three vertices of the triangle, and, if $v$ is deleted, the two other vertices of the triangle are disconnected with the vertices of $G-v$ that are not in the triangle.

For a (single or double) galaxy with the notation of Definition 54 resp. Definition 55, we call a $P_{3}$ pending at $v$ resp. a triangle (pending at $v$ ) a pending object. The (one or two) edges of the pending object incident with $v$ are called star edges, the other edge of the pending object is called matching edge.

Lemma 59.

A single galaxy is line $[B,A]$ -nice.

Proof.

Let $G$ be a single galaxy with the notation from Definition 54.

If the number $k+\ell$ of pending objects of $G$ is at most 2, then $G$ is an isolated vertex, a $P_{3}$ , a triangle, a $P_{5}$ , an amaryllis, or a double vase, thus, in any case, line $[B,-]$ -nice, which implies by Observation 15 that $G$ is line $[B,A]$ -nice.

Otherwise, the maximum degree $\Delta(G)$ of $G$ is at least 3, and Alice has the following winning strategy with $\Delta(G)$ colours in the $[B,A]$ -edge colouring game played on $G$ . She may arbitrarily number the pending objects $O_{1},O_{2},\ldots,O_{k+\ell}$ and perform the following pairing strategy.

•

If Bob colours the matching edge of the pending object $O_{j}$ , then Alice colours a star edge of the pending object $O_{j+1\mod{k+\ell}}$ with the same colour, if possible. If it is not possible, she uses a new colour for such a star edge.
•

If Bob colours the first star edge of the pending object $O_{j}$ (a triangle or a $P_{3}$ ), then Alice colours the matching edge of the pending object $O_{j-1\mod{k+\ell}}$ with the same colour.
•

If Bob colours the second star edge of the pending object (a triangle) $O_{j}$ , then Alice misses her turn.

Note that by this strategy, colouring a star edge with the same colour in the first case is only not possible if the colour has been already used for a star edge and a matching edge. Note further that after Alice’s moves, a star edge is either adjacent to an uncoloured matching edge or to a matching edge coloured in a colour of another star edge. Furthermore, by the pairing strategy, whenever Bob colours a matching edge with a new colour, then there is a nonadjacent uncoloured star edge left that can be coloured with the same colour. Thus every unsafe edge (the star edges) can be coloured feasibly.

∎

Lemma 60.

A double galaxy is line $[B,A]$ -nice.

Proof.

Let $G$ be a double galaxy with the notation from Definition 55.

If the number $k+\ell$ of pending objects of $G$ is at most 1, then $G$ is a double star, a shooting star or an amaryllis, thus, in any case, line $[B,-]$ -nice, which implies by Observation 15 that $G$ is line $[B,A]$ -nice.

Otherwise, the degree of $v$ is at least 3, and Alice uses an extension of the strategy for a single galaxy. Note that the maximum degree of $G$ is

\Delta(G)=\max\{m+1,2k+\ell+n+1\}.

We describe a winning strategy for Alice with $\Delta(G)$ colours in the $[B,A]$ -edge colouring game played on $G$ .

The only unsafe edges are the star edges of pending objects and the edge $vz$ . Alice may arbitrarily number the pending objects $O_{1},O_{2},\ldots,O_{k+\ell}$ and performs basically the same pairing strategy as in the proof of Lemma 59 with only small extensions, as described in the following.

•

If Bob colours the matching edge of the pending object $O_{j}$ , then, if this was the first such move and the edge $vz$ is still uncoloured, Alice colours $vz$ with the same colour (if possible, or a new colour otherwise); otherwise, Alice colours a star edge of the pending object $O_{j+1\mod{k+\ell}}$ with the same colour, if possible. If it is not possible, she uses a new colour for such a star edge.
•

If Bob colours the first star edge of the pending object $O_{j}$ and there is still a pending object with only uncoloured star edges, then Alice colours the matching edge of the pending object $O_{j-1\mod{k+\ell}}$ with the same colour. If the matching edge is already coloured, then Alice misses her turn.
•

If Bob colours the first star edge of the pending object $O_{j}$ and there is no pending object with only uncoloured star edges left, then Alice colours $vz$ with a new colour (if $vz$ is still uncoloured) or misses her turn (if $vz$ is already coloured).
•

If Bob colours the edge $vz$ , an edge $vx_{j}$ or the second star edge of the pending object (a triangle) $O_{j}$ , then Alice misses her turn.
•

If Bob colours an edge $zu_{i}$ , then Alice colours $vz$ (if $vz$ is still uncoloured) or misses her turn (otherwise).

This strategy has the same properties as the strategy for the single galaxy in the proof of Lemma 59, and, in addition, it guarantees that the edge $vz$ is coloured before it is in danger to be infeasible for any colour. ∎

5.4 Permitted for game $[A,A]$

Definition 61 (full tree).

Let $n,m_{1},m_{2}\in{\mathbb{N}}$ . An $(n,m_{1},m_{2})$ -full tree is based on a path $P_{3}$ , where there are $m_{1}$ (respectively, $n$ , $m_{2}$ ) leaves attached its three vertices, i.e., the graph has the vertex set

\{w_{1},v,w_{2}\}\cup\{x_{i}\mid 1\leq i\leq m_{1}\}\cup\{y_{j}\mid 1\leq j\leq n\}\cup\{z_{i}\mid 1\leq i\leq m_{2}\}

and the edge set

\{w_{1}v,vw_{2}\}\cup\{w_{1}x_{i}\mid 1\leq i\leq m_{1}\}\cup\{vy_{j}\mid 1\leq j\leq n\}\cup\{w_{2}z_{i}\mid 1\leq i\leq m_{2}\}.

A full tree is an $(n,m_{1},m_{2})$ -full tree for some $n,m_{1},m_{2}\in{\mathbb{N}}$ .

Note that an $(n,m_{1},1)$ -full tree is a shooting star; a $(0,m_{1},m_{2})$ -full tree is an empty candy; an $(n,m_{1},0)$ -full tree is a double star; and an $(n,0,0)$ -full tree is a star. These trivial configurations are excluded in the next definition.

Definition 62 (full tree of type $E_{1}$ ).

A full tree of type $E_{1}$ is a full tree that is neither a shooting star nor a candy nor a double star.

By Definition 62, a full tree of type $E_{1}$ does not belong to the permitted configurations for game $[B,A]$ .

Definition 63 (satellite).

Let $m_{1},m_{2}\in{\mathbb{N}}$ . An $(m_{1},m_{2})$ -satellite is based on a triangle $K_{3}$ , where there are $m_{1}$ (respectively, $m_{2}$ ) leaves attached to two of its three vertices and exactly one leaf is attached to its third vertex, i.e., the graph has the vertex set

\{w_{0},w_{1},w_{2},y\}\cup\{z_{1,i}\mid 1\leq i\leq m_{1}\}\cup\{z_{2,i}\mid 1\leq i\leq m_{2}\}

and the edge set

\{w_{0}w_{1},w_{0}w_{2},w_{1}w_{2},w_{0}y\}\cup\{w_{1}z_{1,i}\mid 1\leq i\leq m_{1}\}\cup\{w_{2}z_{2,i}\mid 1\leq i\leq m_{2}\}.

A satellite is an $(m_{1},m_{2})$ -satellite for some $m_{1},m_{2}\in{\mathbb{N}}$ .

Note that an $(m_{1},0)$ -satellite is a special star book (with one book sheet). Such a trivial configuration is excluded in the next definition.

Definition 64 (satellite of type $E_{2}$ ).

A satellite of type $E_{2}$ is a satellite that is not a star book.

By Definition 64, a satellite of type $E_{2}$ does not belong to the permitted configurations for game $[B,A]$ .

Lemma 65.

A full tree is line $[A,A]$ -nice.

Proof.

Let $G$ be a full tree with the vertex labels from Definition 61. Note that the only possibly unsafe edges are $vw_{1}$ and $vw_{2}$ . We describe a winning strategy for Alice with $\Delta(G)$ colours in the $[A,A]$ -edge colouring game played on $G$ .

If there is at most one unsafe edge, then Alice colours this edge (if any) in her first move and wins trivially. In the following, we assume that there are two unsafe edges.

If $G$ is the path $P_{5}$ , which is a trivial shooting star, then Alice misses her first turn and has a trivial winning strategy for the $[B,-]$ -edge colouring game by Lemma 48.

Otherwise, $\Delta(G)\geq 3$ , and so the number of colours in the game is at least 3. Therefore, Alice may ensure that the two unsafe edges $vw_{1}$ and $vw_{2}$ are coloured after her first two moves, which is possible with three colours since Bob has only one move in between.

Thus, in any case, Alice wins. ∎

Lemma 66.

A satellite is line $[A,A]$ -nice.

Proof.

Let $G$ be a satellite with the vertex labels from Definition 63. Note that the only possibly unsafe edges are the triangle edges $w_{0}w_{1}$ , $w_{0}w_{2}$ and $w_{1}w_{2}$ . We describe a winning strategy for Alice with $c=\Delta(G)$ colours in the $[A,A]$ -edge colouring game played on $G$ .

Alice misses her first turn and then reacts as follows on Bob’s first move.

•

If Bob colours $w_{1}w_{2}$ , then Alice colours $w_{0}y$ with the same colour, and vice-versa. Now this colour may not be used any more. Note that the graph $G-\{w_{1}w_{2},w_{0}y\}$ is an empty candy and we have

$\Delta(G-\{w_{1}w_{2},w_{0}y\})=\Delta(G)-1=c-1.$

Therefore, if Alice follows her winning strategy for the $[B,-]$ -edge colouring game with $c-1$ colours played on the empty candy $G-\{w_{1}w_{2},w_{0}y\}$ , which exists by Lemma 47, then Alice will win.

•

Let $s\in\{1,2\}$ . If Bob colours $w_{0}w_{s}$ , then, if $m_{3-s}\geq 1$ , Alice colours the star edge $e:=w_{3-s}z_{3-s,1}$ with the same colour, and if $m_{3-s}=0$ , Alice misses her turn. And vice-versa, if Bob colours a star edge $e:=w_{3-s}z_{3-s,i}$ for some $i\in{\mathbb{N}}$ with $1\leq i\leq m_{3-s}$ , then Alice colours $w_{0}w_{s}$ with the same colour. Now this colour may not be used any more. Note that the graph

G^{\prime}:=\left\{\begin{array}[]{ll}G-\{w_{0}w_{s},e\}&\text{if}\ m_{3-s}\geq 1\\ G-\{w_{0}w_{s}\}&\text{if}\ m_{3-s}=0\end{array}\right.

is a shooting star and we have

\Delta(G^{\prime})=\Delta(G)-1=c-1.

Therefore, if Alice follows her winning strategy for the $[B,-]$ -edge colouring game with $c-1$ colours played on the shooting star $G^{\prime}$ , which exists by Lemma 48, then Alice will win.

Thus, in any case, Alice has a winning strategy. ∎

We remark that, since, in her strategy, Alice misses her first turn, the proof of Lemma 66, indeed, shows that a satellite is line $[B,A]$ -nice. However, in general, a satellite is not line $[B,A]$ -perfect, since it may contain a 3-caterpillar $F_{1}$ as an edge-induced subgraph (which can be seen by deleting the edge $w_{1}w_{2}$ ).

6 Proof of the structural characterisations

6.1 Proof of Theorem 9

A basic concept in the proof of Theorem 9 is the concept of a block of a graph. Recall that a graph $G$ is 2-connected if it has at least 3 vertices and, for any vertex $v$ , if $v$ is deleted, the remaining graph $G-v$ is still connected. A vertex $v$ of a graph $G$ is an articulation point of $G$ if deleting $v$ increases the number of components, i.e., $G-v$ has strictly more components than $G$ . A block of a graph $G$ is a maximal subgraph of $G$ that is connected and contains no articulation points. Thus, a block is either a maximal 2-connected subgraph of $G$ or a $K_{2}$ . The edges of different blocks do not overlap, but several blocks may share the same articulation point.

of Theorem 9.

We prove the equivalence by a ring closure.

(1) $\Longrightarrow$ (2)

We have to prove that $P_{6},C_{5},F_{2},F_{3}$ and $F_{1}\cup F_{1}$ are not line $[A,A]$ -perfect. It is sufficient to prove that they are not line $[A,A]$ -nice. This was proved in Lemma 34 for path $P_{6}$ , in Lemma 36 for the mini lobster $F_{2}$ , and in Lemma 38 for the trigraph $F_{3}$ . The $C_{5}$ is not line perfect, thus it is not line $[A,A]$ -perfect (see Lemma 35). $F_{1}$ is not line $[B,A]$ -nice by Lemma 33, so $F_{1}\cup F_{1}$ is not line $[A,A]$ -nice (see Lemma 39).

(2) $\Longrightarrow$ (3)

Let $G$ be a graph that contains no $P_{6}$ , $C_{5},F_{2},F_{3},F_{1}\cup F_{1}$ as edge-induced subgraphs and let $H$ be a component of $G$ .

Since $H$ does not contain $C_{5}$ or $P_{6}$ , the component $H$ is line perfect by Theorem 2. Thus, by Theorem 3, every block of $H$ is either bipartite or a $K_{4}$ or a triangular book $K_{1,1,m}$ for some $m\geq 1$ . Since $H$ contains no $P_{6}$ and no $C_{5}$ , the only possible cycles are triangles and 4-cycles.

We first observe that, among the blocks that $H$ contains, there is at most one block which is one of the following configurations: $K_{1,1,m}$ with $m\geq 2$ (a nontrivial triangular book), a bipartite block containing at least one 4-cycle, or $K_{4}$ . Assume to the contrary that $H$ contains two such (not necessarily different) configurations. Then there are 3 edges from each of the two configurations which, together with the edges on a shortest path connecting the two configurations, form an edge-induced $P_{k}$ with $k\geq 7$ , which contains a $P_{6}$ , contradicting (2).

We observe further that if $H$ contains a block that is a triangle (i.e., a trivial triangular book $K_{1,1,1}$ ), then $H$ cannot contain any of the configurations $K_{1,1,m}$ with $m\geq 2$ , $K_{4}$ , or a bipartite block containing at least one 4-cycle. Assume to the contrary that $H$ contains one of them. Then there are 3 edges from such a configuration and 2 edges from the triangle which, together with the edges on a shortest path connecting the configuration with the triangle, form an edge-induced $P_{k}$ with $k\geq 6$ , which contains a $P_{6}$ , contradicting (2).

Case 1:

$H$ contains a $K_{4}$ .

Then there is a vertex $v$ of the $K_{4}$ , so that every edge of $H$ that is not part of the $K_{4}$ is adjacent to $v$ , since, otherwise, if outside of the $K_{4}$ there is an edge that is not adjacent to $v$ and an edge that is adjacent to $v$ , by using these two edges and 3 edges of the $K_{4}$ there is a path or a cycle of lenght at least 5, thus $H$ contains an edge-induced $P_{6}$ or $C_{5}$ , which contradicts (2). Thus $H$ is a tetrahedron of flowers.
Case 2:

$H$ contains a nontrivial triangular book $K_{1,1,m}$ with $m\geq 2$ .

Let $v_{1},v_{2}$ be the two vertices of degree $m+1$ and $w_{1},\ldots,w_{m}$ the vertices of degree 2 of the $K_{1,1,m}$ . Let $e$ be an edge that does not belong to the $K_{1,1,m}$ .

(a)

(b)

(c)

(d)

(e)

Figure 19: Creating forbidden configurations in Case 2.

If $e$ connects two vertices $w_{i}$ and $w_{j}$ with $i\neq j$ , then, in case $m=2$ , we have a $K_{4}$ and are thus in Case 1, which was already discussed above, or, in case $m\geq 3$ , the graph contains an edge-induced $C_{5}$ (see Figure 19 (a)), which is forbidden by (2).

Now consider the case that $e$ is incident with some vertex $w_{i}$ and another vertex $x$ that is not part of the $K_{1,1,m}$ . If $m\geq 3$ , then $e$ together with 4 edges of the $K_{1,1,m}$ form a $P_{6}$ (see Figure 19 (b)), which is forbidden by (2). If $m=2$ , then there is neither an additional edge incident with $v_{1}$ or $v_{2}$ other than the edges of the $K_{1,1,m}$ nor an edge different from $e$ incident with $x$ since, otherwise, $H$ contains an edge-induced $P_{6}$ (see Figures 19 (c) and (d)), which is forbidden by (2). Thus, in this case, $H$ is a diamond of flowers.

If $e$ is incident with $v_{1}$ or $v_{2}$ , then there is no edge adjacent to $e$ that is not part of the $K_{1,1,m}$ since, otherwise, $H$ contains a $P_{6}$ (see Figure 19 (e)), which is forbidden by (2). Thus, in this case, $H$ is a star book.
Case 3:

$H$ is bipartite and contains a block with a $C_{4}$ .

First note that the union of the 4-cycles in the block must form a $K_{2,m}$ with $m\geq 2$ . This is because it is the only possibility to combine several 4-cycles in a block without creating cycles $C_{2k+6}$ with $k\in{\mathbb{N}}$ , which are forbidden since its subgraph, the $P_{6}$ , is forbidden by (2).

Note that in the contradictions of Case 2 in Figure 19 the edge between $v_{1}$ and $v_{2}$ was not used, which means they are still valid even if $v_{1}v_{2}$ is absent, which is the case $K_{2,m}$ here. Only for $m=2$ where there appeared a $K_{4}$ , there would appear here a diamond (which is not bipartite). Thus, by the same proof as in Case 2, $H$ is a candy.
Case 4:

$H$ contains a block that is a triangle.

Consider one fixed triangle with vertices $v_{1},v_{2},v_{3}$ . Note that no $P_{4}$ may be pending at $v_{i}$ since, otherwise, the three edges of the $P_{4}$ and two of the edges of the triangle would form an edge-induced $P_{6}$ , which is forbidden by (2). Similarly, no $P_{3}$ resp. no other triangle may be pending at $v_{i}$ when $P_{2}$ is pending at $v_{j}$ with $j\neq i$ .

In the following, we disinguish between the cases that the number $a$ of vertices $v_{1},v_{2},v_{3}$ that have at least one pending $P_{2}$ is 2, 3 or at most 1.
1. Subcase 4.1:
  
  $a=2$ .
  
  The case that the block containing $v_{1},v_{2},v_{3}$ is a $K_{4}$ or a diamond was already discussed in Case 1 or Case 2, respectively. Thus we are left with the case that the block containing $v_{1},v_{2},v_{3}$ is a triangle. Then the component $H$ is a star book with exactly one triangle (and two of $v_{1},v_{2},v_{3}$ have at least one pending $P_{2}$ ).
2. Subcase 4.2:
  
  $a=3$ .
  
  Suppose now at least one $P_{2}$ is pending at every $v_{i}$ . Since the trigraph $F_{3}$ , in which every $v_{i}$ has two pending $P_{2}$ s, is forbidden, at least one of $v_{1},v_{2},v_{3}$ has at most one pending $P_{2}$ , which means that $H$ is a satellite.
3. Subcase 4.3:
  
  $a\leq 1$ .
  
  Suppose exactly one of $v_{1},v_{2},v_{3}$ has at least one pending $P_{3}$ . Note that $H$ may contain more than one block which is a triangle. As discussed above, all these triangle blocks share exactly one vertex and we denote this by $v$ . At most one pending star with at least 2 star edges may be pending at $v$ since, otherwise, if there are two of them, two of the star edges of each pending star and the edges of the pending stars that are incident with $v$ together with two of the edges of a triangle would form an edge-induced mini lobster $F_{2}$ , which is forbidden by (2). Thus, $H$ is a double galaxy or a single galaxy.
Case 5:

$H$ is a tree.

As the $P_{6}$ is forbidden, $H$ has diameter at most 4. If $H$ has diameter at most 3, then $H$ is an isolated vertex (which is a single galaxy) or a double star (which is a double galaxy). If $H$ has diameter 4, $H$ can be depicted by configuration $E$ in Figure 20.

Figure 20: A generic tree $E$ of diameter 4

Since the mini lobster $F_{2}$ is $[A,A]$ -forbidden we conclude that, if $m\geq 3$ in configuration $E$ , at most two of the stars pending at the central vertex have more than one leaf. If there are exactly two such stars, then the other stars are simply pending $P_{2}$ s, again since the mini lobster $F_{2}$ is forbidden, thus $H$ is a full tree; otherwise, i.e., when there is at most one such star, $H$ is a double galaxy (or a single galaxy) with no triangles.

Thus, in all cases we get a permitted configuration. Furthermore, since $F_{1}\cup F_{1}$ is forbidden, at most one of the components may be a full tree of type $E_{1}$ or a satellite of type $E_{2}$ (as both of the latter configurations contain a 3-caterpillar $F_{1}$ by definiton). Therefore, (3) holds.

(3) $\Longrightarrow$ (1)

The permitted configurations for each component are line $[A,A]$ -nice: we have proved this for the candy in Lemma 47, for the star book in Lemma 56, for the single galaxy in Lemma 59, for the double galaxy in Lemma 60, for the diamond of flowers in Lemma 57, for the tetrahedron of flowers in Lemma 58, for the full tree $E_{1}$ in Lemma 65, and for the satellite in Lemma 66. With the exception of a full tree of type $E_{1}$ and a satellite of type $E_{2}$ , the permitted configurations are even line $[B,A]$ -nice.

Let $G$ be a graph whose components are of the permitted types and where at most one component is a special component, namely a full tree of type $E_{1}$ or a satellite of type $E_{2}$ . Then, in her first move, Alice plays according to her strategy for the special component (if there is a special component) or misses her turn (if there is no special component). After that she reacts always in the component where Bob has played in his previous move according to her strategy for the $[B,A]$ -edge colouring game (respectively, $[A,A]$ -edge colouring game for the special component) or she misses her turn (if the component where Bob has played in his previous move is completely coloured). By the lemmas mentioned above, Alice will win. Thus $G$ is $[A,A]$ -nice.

In Lemma 67 we will show that the permitted types are hereditary. Thus the permitted types are line $[A,A]$ -perfect. From this we conclude that $G$ is line $[A,A]$ -perfect, which proves (1).

∎

Lemma 67.

The permitted types for game $[A,A]$ are hereditary.

Proof.

See Table 1 and its caption. ∎

Structure	Structure after deleting an edge
candy	candy
	two stars (which are galaxies)
star book	star book
	candy
	double star (which is a double galaxy)
diamond of flowers	diamond of flowers
	double galaxy
	star book
	candy
tetrahedron of flowers	tetrahedron of flowers
	diamond of flowers
	star book
single galaxy	double galaxy
	single galaxy & $P_{2}$ (which is a double galaxy)
	single galaxy
double galaxy	double galaxy
	double galaxy & star (which is a galaxy)
	single galaxy & star (which is a galaxy)
satellite	star book
	double galaxy
	full tree $E_{1}$
	satellite
full tree $E_{1}$	full tree
	double star & star (which are galaxies)

Table 1: The permitted types for the edge-game

[A,A]

are hereditary. Note that, in particular, by deleting an edge, there will remain at most one satellite or full tree. Furthermore, in some cases additionally there will be isolated vertices, which we do not mention explicitly.

In order to illustrate the proof we depict four characteristic situations for the candy when one edge is deleted in Figure 21.

6.2 Proof of Theorem 10

of Theorem 10.

We prove the equivalence by a ring closure.

(1) $\Longrightarrow$ (2): We have to prove that a $P_{6}$ , a $C_{5}$ and a 3-caterpillar $F_{1}$ are not line $[B,A]$ -perfect. Since, by Lemma 34 and Lemma 35, $P_{6}$ and $C_{5}$ are not line $[A,A]$ -perfect, by Observation 19 they are not line $[B,A]$ -perfect. Thus, it is sufficient to prove that $F_{1}$ is not line $[B,A]$ -nice. This was proved in Lemma 33.
(2) $\Longrightarrow$ (3): Let $G$ be a graph that contains no $P_{6}$ , $C_{5}$ , or 3-caterpillar $F_{1}$ as an edge-induced subgraph. Thus, in particular, the graph $G$ contains no $P_{6}$ , $C_{5}$ , mini lobster $F_{2}$ , trigraph $F_{3}$ , and no $F_{1}\cup F_{1}$ .

By Theorem 9, every component of $G$ is a candy, a star book, a diamond of flowers, a tetrahedron of flowers, a single galaxy, a double galaxy, a full tree, or a satellite. Since a full tree of type $E_{1}$ and a satellite of type $E_{2}$ contain a 3-caterpillar no component of $G$ is a full tree of type $E_{1}$ or a satellite of type $E_{2}$ . Thus (3) holds.
(3) $\Longrightarrow$ (1): The permitted configurations are line $[B,A]$ -nice: we proved this for the candy in Lemma 47, for the star book in Lemma 56, for the single galaxy in Lemma 59, for the double galaxy in Lemma 60, for the diamond of flowers in Lemma 57, and for the tetrahedron of flowers in Lemma 58.

Let $G$ be a graph whose components are of one of the permitted types for game $[B,A]$ . Then Alice always reacts in the component where Bob has played according to her strategy for the $[B,A]$ -edge colouring game (or she misses her turn if this component is completely coloured). By the mentioned lemmata, Alice will win. Thus $G$ is line $[B,A]$ -nice.

Furthermore, the permitted configurations are hereditary, which can be seen from the first six entries in Table 1. From this we conclude that $G$ is line $[B,A]$ -perfect, which proves (1).

∎

6.3 Proof of Theorem 11

of Theorem 11.

We prove the equivalence by a ring closure.

(1) $\Longrightarrow$ (2)

This implication is part of Proposition 31.

(2) $\Longrightarrow$ (3)

Let $G$ be a graph that fulfils (2), i.e., it contains no $P_{5}\cup P_{2}$ , $C_{4}\cup P_{2}$ , $P_{6}$ , $C_{5}$ , bull, diamond, or 3-caterpillar as an edge-induced subgraph.

By (2), the graph $G$ , in particular, contains no $P_{6}$ , $C_{5}$ , 3-caterpillar. Thus, by Theorem 10, each component of $G$ is a diamond of flowers, a tetrahedron of flowers, a candy, a star book, a single galaxy, or a double galaxy. Let $H$ be a component of $G$ .

The component $H$ may neither be a diamond of flowers nor a tetrahedron of flowers, since those two configurations contain a diamond as a subgraph, which is forbidden by (2).

Consider the case that $H$ is a star book. It may not contain more than one book sheet, since otherwise it would contain a diamond, which is forbidden by (2). If $H$ has exactly one book sheet, it may not have star edges on both sides, since otherwise it would contain a bull, which is forbidden by (2). Thus, in this case, the component $H$ is a vase of flowers. If $H$ has no book sheet, then $H$ is a double star.

Now consider the case that $H$ is a single galaxy or a double galaxy. In both cases, the component $H$ has a vertex $v$ with $k_{0}$ pending $P_{2}$ s, $k_{1}$ pending $P_{3}$ s, $k_{2}$ pending triangles, and $k_{3}$ pending stars, where $k_{0},k_{1},k_{2}\geq 0$ and $k_{3}\in\{0,1\}$ . First note that

k_{1}+k_{2}+k_{3}\leq 2,

(2)

since otherwise, if $k_{1}+k_{2}+k_{3}\geq 3$ , two of the pending objects would contain a $P_{5}$ and the third would contain a $P_{2}$ that is not adjacent with the $P_{5}$ , thus $H$ would contain an edge-induced $P_{5}\cup P_{2}$ , which is forbidden by (2). So we may assume that (2) holds. We distinguish some cases.

•

If $k_{1}=2$ and $k_{2}=k_{3}=0$ , then $H$ is a shooting star.
•

If $k_{1}=1$ and $k_{2}=k_{3}=0$ , then $H$ is a double star.
•

If $k_{1}=k_{2}=1$ and $k_{3}=0$ , then $H$ is an amaryllis.
•

If $k_{1}=k_{3}=1$ and $k_{2}=0$ , then $H$ is a shooting star.
•

If $k_{2}\leq 2$ and $k_{1}=k_{3}=0$ , then $H$ is a double vase, a vase of flowers, or a star (which is either a double star or an isolated vertex).
•

If $k_{2}=k_{3}=1$ and $k_{1}=0$ , then $H$ is an amaryllis.
•

If $k_{3}=1$ and $k_{1}=k_{2}=0$ , then $H$ is a double star.

Finally, we have to prove that if one of the components of $G$ is a candy, a shooting star, a double vase, or an amaryllis, but neither a double star nor a vase of flowers, then $G$ has only one nontrivial component. We observe that

•

a candy that is not a double star contains a $P_{5}$ or a $C_{4}$ ,
•

a shooting star that is not a double star contains a $P_{5}$ ,
•

a double vase contains a $P_{5}$ , and
•

an amaryllis that is not a vase of flowers contains a $P_{5}$ .

Thus, if there is such a component in the graph, then there may not be another component that contains an edge, since otherwise $G$ would contain a $P_{5}\cup P_{2}$ or a $C_{4}\cup P_{2}$ , which are forbidden by (2). Therefore, (3) holds.

(3) $\Longrightarrow$ (1)

Let $G$ be a graph fulfilling (3). Then, by Lemmata 42, 47, 48, 49, and 50, the graph $G$ is line $[B,-]$ -perfect, i.e., (1) holds.

∎

6.4 Proof of Theorem 12

of Theorem 12.

We prove the equivalence by a ring closure.

(1) $\Longrightarrow$ (2): This follows from ${\cal LP}[B,B]\subseteq{\cal LP}[A,B]$ (Observation 19).
(2) $\Longrightarrow$ (3): This follows from ${\cal LP}[A,B]\subseteq{\cal LP}[A,-]$ (Observation 19).
(3) $\Longrightarrow$ (4): This implication is part of Proposition 30.
(4) $\Longrightarrow$ (5): Let $G$ be a graph that contains neither $P_{5}$ nor $C_{4}$ as an edge-induced subgraph. Thus, in particular $G$ contains no $P_{5}\cup P_{2}$ , $C_{4}\cup P_{2}$ , $P_{6}$ , $C_{5}$ , bull, diamond, 3-caterpillar (since these configurations either contain a $P_{5}$ or, in the case of $C_{4}\cup P_{2}$ , a $C_{4}$ ). Thus $G$ is line $[B,-]$ -perfect. Therefore, by Theorem 11 every component of $G$ is a double star, a vase of flowers, an isolated vertex, a candy, a shooting star, a double vase, or an amaryllis. Let $H$ be a component of $G$ .

If $H$ is a candy, then it must be an empty candy, since otherwise it would contain a $C_{4}$ , which is forbidden by (4). Furthermore, it may not have star edges at both sides, since otherwise it would contain a $P_{5}$ , which is forbidden by (4). Thus $H$ is a double star.

If $H$ is a shooting star, then it must have diameter 3, since otherwise it would contain a $P_{5}$ , which is forbidden by (4). Thus $H$ is a double star.

Note that $H$ may not be a double vase as the two triangles contain an edge-induced $P_{5}$ , which is forbidden by (4).

Furthermore, if $H$ is an amaryllis, then the pending star must be empty, since otherwise two edges of the pending star and two edges of the triangle would form a $P_{5}$ , which is forbidden by (4). Thus $H$ is a vase of flowers.

We conclude that (5) holds.
(5) $\Longrightarrow$ (1): We have to prove that graphs each component of which is a double star, vase of flowers or isolated vertex is line $[B,B]$ -perfect. This was shown in Lemma 42, which proves the last implication of the theorem.

∎

7 Final remarks

In this paper, we completely characterize line game-perfect graphs for all six possible games.

7.1 Similar characterisations for vertex colouring games

Similar characterisations for game-perfect graphs (where vertex games are considered instead of edge games) are only known for the games $[B,B]$ , $[A,B]$ , $[A,-]$ and $[B,-]$ . Thus the following question might be interesting for further research.

Problem 68.

Characterise game-perfect graphs for the games $[B,A]$ and $[A,A]$ (by forbidden induced subgraphs and/or explicit structural descriptions).

Note that we have no idea how to extend our methods to the more general case of Problem 68. This might be very difficult as there are infinitely many minimal forbidden configurations, namely (among others) all odd antiholes (Andres, 2009, Thm 23).

There is a historic analog for this discrepancy: the characterisation of line-perfect graphs by forbidden subgraphs was found by Trotter (1977) in 1977, but the more general result, the characterisation of perfect graphs by forbidden induced subgraphs (the famous Strong Perfect Graph Theorem) was proved by Chudnovsky et al. (2006) nearly 30 years later and published in 2006.

We remark that an analog for the explicit characterisation of line perfect graphs by Maffray (1992) has not yet been found (more than 30 years later) for perfect graphs.

7.2 A variant of line game-perfectness

One might also consider a variant of line game-perfectness: A graph $G$ is edge $[X,Y]$ -perfect if, for any edge-induced subgraph $H$ of $G$ ,

\chi_{[X,Y]}^{\prime}(H)=\Delta(H).

By Corollary 24, the only difference between line $[X,Y]$ -perfect graphs and edge $[X,Y]$ -perfect graphs is that in edge $[X,Y]$ -perfect graphs we have an additional forbidden configuration, namely the triangle $K_{3}$ . Thus, edge $[X,Y]$ -perfect graphs can be obtained from our explicit structural descriptions of line $[X,Y]$ -perfect graphs by deleting all graphs that contain a triangle, which leaves fairly trivial classes of graphs. Therefore our notion of line $[X,Y]$ -perfect graphs might be the better concept to describe game-perfectness for edge colouring games.

7.3 Games with a bounded number of skipping turns

In our games, skipping a turn was either forbidden or allowed for an unlimited number of turns. Now, we consider the question what happens if we allow only a bounded number of skipping turns.

Let $X,Y\in\{A,B\}$ , and $k,s\in{\mathbb{N}}$ , and $G$ be a graph. In the edge colouring game $[X,Y]_{s}$ played with $k$ colours on the graph $G$ the players alternately move with player $x$ beginning. Player $Y$ may skip a turn (including the first one) up to $s$ times. A move that is not skipped consists in colouring an uncoloured edge $e$ of $G$ with a colour from the set $\{1,2,\ldots,k\}$ that is different from the colours of the edges adjacent to $e$ . This game defines a game chromatic index $\chi_{[X,Y]_{s}}^{\prime}(G)$ of the graph $G$ . The graph $G$ is line $[X,Y]_{s}$ -perfect if, for any edge-induced subgraph $H$ of $G$ ,

\omega(L(H))=\chi_{[X,Y]_{s}}^{\prime}(H).

The class of all line $[X,Y]_{s}$ -perfect graphs is denoted by ${\cal LP}[X,Y]_{s}$ . By definition,

{\cal LP}[X,Y]_{0}={\cal LP}[X,-].

We observe the following.

Observation 69.

Let $X\in\{A,B\}$ . Then we have:

(i)

${\cal LP}[X,B]\subseteq\ldots\subseteq{\cal LP}[X,B]_{3}\subseteq{\cal LP}[X,B]_{2}\subseteq{\cal LP}[X,B]_{1}\subseteq{\cal LP}[X,-]$
(ii)

${\cal LP}[X,-]\subseteq{\cal LP}[X,A]_{1}\subseteq{\cal LP}[X,A]_{2}\subseteq{\cal LP}[X,A]_{3}\subseteq\ldots\subseteq{\cal LP}[X,A]$

Proof.

This holds since the possibility to skip one time more is no disadvantage for the player who is allowed to skip. ∎

Observation 70.

Let $s\in{\mathbb{N}}$ . Then we have:

(i)

${\cal LP}[B,B]_{s+1}\subseteq{\cal LP}[A,B]_{s}$
(i)

${\cal LP}[B,A]_{s}\subseteq{\cal LP}[A,A]_{s+1}$

Proof.

Ad (i): If Bob has a winning strategy for the game $[A,B]_{s}$ on a graph $G$ , then, by skipping his first turn, he can use the same strategy in order to win the game $[B,B]_{s+1}$ played on $G$ .

Ad (ii): If Alice has a winning strategy for the game $[B,A]_{s}$ on a graph $G$ , then, by skipping her first turn, she can use the same strategy in order to win the game $[A,A]_{s+1}$ played on $G$ . ∎

Using the two observations above, we obtain the following corollary of Theorem 12.

Corollary 71.

Let $s\in{\mathbb{N}}$ with $s\geq 1$ . Then

{\cal LP}[X,B]_{s}={\cal LP}[B,B].

Proof.

For any $s\in{\mathbb{N}}$ with $s\geq 1$ , by Theorem 12, Observation 19, Observation 69 (i), and Observation 70 (i), we have

	$\displaystyle{\cal LP}[B,B]\stackrel{{\scriptstyle\text{Obs}~{}\ref{obs:compareclasses}}}{{\subseteq}}{\cal LP}[A,B]$	$\displaystyle\stackrel{{\scriptstyle\text{Obs}~{}\ref{obs:skipone}~{}(i)}}{{\subseteq}}$	$\displaystyle{\cal LP}[A,B]_{s}$
		$\displaystyle\stackrel{{\scriptstyle\text{Obs}~{}\ref{obs:skipone}~{}(i)}}{{\subseteq}}$	$\displaystyle{\cal LP}[A,-]\stackrel{{\scriptstyle\text{Thm}~{}\ref{thm:lineBB}}}{{=}}{\cal LP}[B,B]$

and

	$\displaystyle{\cal LP}[B,B]\stackrel{{\scriptstyle\text{Obs}~{}\ref{obs:skipone}~{}(i)}}{{\subseteq}}{\cal LP}[B,B]_{s}$	$\displaystyle\stackrel{{\scriptstyle\text{Obs}~{}\ref{obs:skiptwo}~{}(i)}}{{\subseteq}}$	$\displaystyle{\cal LP}[A,B]_{s-1}$
		$\displaystyle\stackrel{{\scriptstyle\text{Obs}~{}\ref{obs:skipone}~{}(i)}}{{\subseteq}}$	$\displaystyle{\cal LP}[A,-]\stackrel{{\scriptstyle\text{Thm}~{}\ref{thm:lineBB}}}{{=}}{\cal LP}[B,B].$

Thus, the equality ${\cal LP}[X,B]_{s}={\cal LP}[B,B]$ is true when $X=A$ or $X=B$ . ∎

According to Corollary 71, our new games give no new classes in case the skipping is allowed to Bob. The situation changes if the skipping is allowed to Alice. Here the characterisation of the respective classes of line game-perfect graphs seems to be very intricate. One reason is that in our strategies for Alice sometimes Alice has to miss a turn in order to avoid beginning to colour in a new, uncoloured component, which makes the discussion of disconnected graphs very difficult. But even for connected graphs our strategies require that Alice skips several times. This is the case for single or double galaxies, where our strategies require that Alice skips if Bob plays on the second star edge of a pending triangle. Note that a (single or double) galaxy may have arbitrarily many pending triangles; therefore it might seem to be straightforward that some of the classes ${\cal LP}[X,A]_{s}$ are different from the classes ${\cal LP}[X,-]$ and ${\cal LP}[X,A]$ . However, it is not clear whether the strategies given in this paper cannot be improved in some way using fewer skipping moves.

Problem 72.

For any $s\in{\mathbb{N}}\setminus\{0\}$ and $X\in\{A,B\}$ , characterise the class ${\cal LP}[X,A]_{s}$ , i.e., characterise line game-perfect graphs for the game $[X,A]_{s}$ (by forbidden edge-induced subgraphs and/or explicit structural descriptions).

The edge-colouring games $[X,Y]_{s}$ defined in this section might be considered more generally, thus, we might define vertex colouring games $[X,Y]_{s}$ in the same way. Then we might ask the following question.

Problem 73.

For any $s\in{\mathbb{N}}\setminus\{0\}$ and $X,Y\in\{A,B\}$ , characterise game-perfect graphs for the game $[X,Y]_{s}$ (by forbidden induced subgraphs and/or explicit structural descriptions).

We expect that the answer to this question will be even more intricate than the answer to Problem 72.

Acknowledgements.

The authors thank the two anonymous reviewers for many useful suggestions that helped to improve the presentation of the paper. Furthermore, in particular, we acknowledge that the idea of the games discussed in Section 7.3 originates from one of the reviewers.

References

Andres (2006) S. D. Andres. The game chromatic index of forests of maximum degree $\Delta\geq 5$ . Discrete Applied Mathematics, 154:1317–1323, 2006.
Andres (2007) S. D. Andres. Digraph coloring games and game-perfectness. Verlag Dr. Hut, München, 2007. Ph.D. thesis, Universität zu Köln.
Andres (2009) S. D. Andres. Game-perfect graphs. Mathematical Methods of Operations Research, 69:235–250, 2009.
Andres (2012) S. D. Andres. On characterizing game-perfect graphs by forbidden induced subgraphs. Contributions to Discrete Mathematics, 7:21–34, 2012.
Andres and Lock (2019) S. D. Andres and E. Lock. Characterising and recognising game-perfect graphs. Discrete Mathematics & Theoretical Computer Science, 21(Paper No. 6):39pp., 2019.
Andres et al. (2011) S. D. Andres, W. Hochstättler, and C. Schallück. The game chromatic index of wheels. Discrete Applied Mathematics, 159:1660–1665, 2011.
Bartnicki and Grytczuk (2008) T. Bartnicki and J. Grytczuk. A note on the game chromatic index of graphs. Graphs and Combinatorics, 24:67–70, 2008.
Beineke (1970) L. W. Beineke. Characterizations of derived graphs. Journal of Combinatorial Theory, 9:129–135, 1970.
Beveridge et al. (2008) A. Beveridge, T. Bohman, A. Frieze, and O. Pikhurko. Game chromatic index of graphs with given restrictions on degrees. Theoretical Computer Science, 407:242–249, 2008.
Bodlaender (1991) H. L. Bodlaender. On the complexity of some coloring games. International Journal of Foundations of Computer Science, 2:133–147, 1991.
Boudon et al. (2017) O. Boudon, J. Przybyło, M. Senhaji, E. Sidorowicz, E. Sopena, and M. Woźniak. The neighbour-sum-distinguishing edge-colouring game. Discrete Mathematics, 340:1564–1572, 2017.
Cai and Zhu (2001) L. Cai and X. Zhu. Game chromatic index of $k$ -degenerate graphs. Journal of Graph Theory, 36:144–155, 2001.
Chan and Nong (2014) W. H. Chan and G. Nong. The game chromatic index of some trees of maximum degree 4. Discrete Applied Mathematics, 170:1–6, 2014.
Charpentier et al. (2018) C. Charpentier, B. Effantin, and G. Paris. On the game coloring index of $f^{+}$ -decomposable graphs. Discrete Applied Mathematics, 236:73–83, 2018.
Chudnovsky et al. (2006) M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas. The strong perfect graph theorem. Annals of Mathematics (2), 164:51–229, 2006.
Dunn (2007) C. Dunn. The relaxed game chromatic index of $k$ -degenerate graphs. Discrete Mathematics, 307:1767–1775, 2007.
Dunn et al. (2015) C. Dunn, D. Morawski, and J. F. Nordstrom. The relaxed edge-coloring game and k-degenerate graphs. Order, 32:347–361, 2015.
Fong and Chan (2019a) W. L. Fong and W. H. Chan. The edge coloring game on trees with the number of colors greater than the game chromatic index. Journal of Combinatorial Optimization, 38:456–480, 2019a.
Fong and Chan (2019b) W. L. Fong and W. H. Chan. The game chromatic index of some trees with maximum degree 4 with at most three degree-four vertices in a row. arXiv, 2019b. arXiv:1904.01496.
Fong et al. (2018) W. L. Fong, W. H. Chan, and G. Nong. The game chromatic index of some trees with maximum degree four and adjacent degree-four vertices. Journal of Combinatorial Optimization, 36:1–12, 2018.
Gardner (1981) M. Gardner. Mathematical games. Scientific American, 244:23–26, April 1981.
Keusch (2018) R. Keusch. A new upper bound on the game chromatic index of graphs. Electronic Journal of Combinatorics, 25(Paper No. 2.33):18pp., 2018.
Lam et al. (1999) P. C. B. Lam, W. C. Shiu, and B. Xu. Edge game-coloring of graphs. Graph Theory Notes New York, 37:17–19, 1999.
Lock (2016) E. Lock. The structure of $g_{B}$ -perfect graphs. FernUniversität in Hagen, 2016. Bachelor thesis.
Maffray (1992) F. Maffray. Kernels in perfect line-graphs. Journal of Combinatorial Theory B, 55:1–8, 1992.
Trotter (1977) L. E. Trotter. Line perfect graphs. Mathematical Programming, 12:255–259, 1977.
Whitney (1932) H. Whitney. Congruent graphs and the connectivity of graphs. American Journal of Mathematics, 54:150–168, 1932.


candy	$\longrightarrow$	candy (+isolated vertex)

candy	$\longrightarrow$	candy

candy	$\longrightarrow$	(empty) candy

(empty) candy	$\longrightarrow$	two stars

Line game-perfect graphs

Abstract

keywords:

1 Introduction

Theorem 1 (Trotter (1977)).

Theorem 2 (Trotter (1977)).

Theorem 3 (Maffray (1992)).

1.1 Vertex colouring games

1.2 Game-perfect graphs

Theorem 4 (Andres (2012)).

Theorem 5 (Lock (2016); Andres and Lock (2019)).

Theorem 6 (Andres (2012)).

Proposition 7 (Lock (2016); Andres and Lock (2019)).

Proposition 8 (Lock (2016); Andres and Lock (2019)).

1.3 The edge colouring game

1.4 Combining the setting: line game-perfect graphs

1.5 Main results

Theorem 9.

Theorem 10.

Theorem 11.

Theorem 12.

1.6 Idea of the proof

1.7 Structure of this paper

2 Preliminaries

2.1 Notation

Definition 13.

2.2 Basic observations

Observation 14 (Andres (2009)).

Observation 15 (Andres (2006)).

2.3 Basic definitions and observations

Observation 16.

Observation 17 (Trotter (1977)).

Observation 18.

Observation 19.

Corollary 20.

Definition 21.

Observation 22.

2.4 Characterisations of line graphs

Theorem 23 (Whitney (1932)).

Corollary 24.

of Corollary 24.

Observation 25.

Definition 26.

Theorem 27 (Beineke (1970)).

3 A plan for characterising line game-perfect graphs

Theorem 28.

Proof.

General strategy to characterise gg-game line perfect graphs.

4 The forbidden subgraphs

4.1 Forbidden subgraphs for game [A,−][A,-]

Lemma 29.

Proposition 30.

Proof.

4.2 Forbidden subgraphs for game [B,−][B,-]

Proposition 31.

Proof.

4.3 Forbidden subgraphs for game [B,A][B,A]

Lemma 32.

Proof.

Lemma 33.

Proof.

4.4 Forbidden subgraphs for game [A,A][A,A]

Lemma 34.

Proof.

Lemma 35.

Proof.

Lemma 36.

Proof.

Lemma 37.

Proof.

Lemma 38.

Proof.

Lemma 39.

Proof.

5 The permitted types

5.1 Permitted for game [B,B][B,B]

Definition 40 (vase of flowers).

Definition 41 (double star).

Lemma 42.

Proof.

General strategy to characterise $g$ -game line perfect graphs.

4.1 Forbidden subgraphs for game $[A,-]$

4.2 Forbidden subgraphs for game $[B,-]$

4.3 Forbidden subgraphs for game $[B,A]$

4.4 Forbidden subgraphs for game $[A,A]$

5.1 Permitted for game $[B,B]$

5.2 Permitted for game $[B,-]$

5.3 Permitted for game $[B,A]$

5.4 Permitted for game $[A,A]$

Definition 62 (full tree of type $E_{1}$ ).

Definition 64 (satellite of type $E_{2}$ ).