# Line game-perfect graphs

Stephan Dominique Andres
University of Greifswald
Institute of Mathematics and Computer Science
Walther-Rathenau-Str. 47, 17487 Greifswald, Germany
<EMAIL_ADDRESS>
Wai Lam Fong
The University of Hong Kong
Department of Mathematics
Hong Kong SAR, China
<EMAIL_ADDRESS>
###### 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 in 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.

Key words: line graph, line perfect graph, edge colouring game, game-perfect
graph, graph colouring game, perfect graph, forbidden subgraph
characterisation

MSC 2020: 05C15, 05C17, 05C57, 05C76, 91A43

##  1 Introduction

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 [25]. 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 [25], 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 vertex-induced subgraphs of $L(G)$.

It is known that line perfect graphs are perfect:

######  Theorem 1 (Trotter (1977) [25]).

Line perfect graphs are perfect.

Trotter [25] gave a characterisation of line perfect graphs by a set of
forbidden edge-induced subgraphs:

######  Theorem 2 (Trotter (1977) [25]).

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

Maffray [24] gave a complete characterisation of the structure of line perfect
graphs:

######  Theorem 3 (Maffray (1992) [24]).

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 [20]. Later it was reinvented by Bodlaender [10] 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 [2, 3]. 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:

######  Theorem 4 (Andres (2012) [4]).

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

$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

######  Theorem 5 (Lock (2016) [23]; Andres and Lock (2019) [6]).

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

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

Furthermore, Andres [4] 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$.

######  Theorem 6 (Andres (2012) [4]).

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).

Andres and Lock [6, 23] 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 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.

Figure 3: An expanded cocobi Figure 4: An expanded bull

######  Proposition 7 (Lock (2016) [23]; Andres and Lock (2019) [6]).

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

######  Proposition 8 (Lock (2016) [23]; Andres and Lock (2019) [6]).

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. [22] and Cai and Zhu
[12]. Determining the maximum game chromatic index of some classes of graphs
has been the subject of several papers [1, 5, 7, 12, 13, 14, 17, 18, 19, 22]
as well as the game chromatic index of random graphs [9, 21] as well as
different types of edge-colouring based games [11, 15, 16]

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$: a $P_{6}$, $C_{5}$, a mini lobster $F_{2}$, a 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$: a $P_{6}$, $C_{5}$, or a 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$: a $P_{5}\cup P_{2}$, $C_{4}\cup P_{2}$, $P_{6}$, $C_{5}$, a
bull, a diamond, or a 3-caterpillar $F_{1}$.

  * (3)

Either every component of $G$ is a double star, a vase of flowers, or an
isolated vertex, or $G$ contains at most one nontrivial component and this
component is a double star, a vase of flowers, a candy, a shooting star, a
double vase, an amaryllis, or an isolated vertex (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$: a $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).

$P_{6}$

$C_{5}$

mini lobster $F_{2}$

trigraph $F_{3}$

$F_{1}\cup F_{1}$

Figure 5: Forbidden subgraphs for line $[A,A]$-perfect graphs

$P_{6}$

$C_{5}$

3-caterpillar $F_{1}$

Figure 6: Forbidden subgraphs for line $[B,A]$-perfect graphs

$P_{5}\cup P_{2}$

$C_{4}\cup P_{2}$

$P_{6}$

$C_{5}$

bull

diamond

3-caterpillar $F_{1}$

Figure 7: Forbidden subgraphs for line $[B,-]$-perfect graphs

$P_{5}$

$C_{4}$

Figure 8: Forbidden subgraphs for line game-perfect graphs for the games
$[B,B]$, $[A,B]$, and $[A,-]$

###  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 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 ([3]).

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 ([1]).

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) [25]).

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) [26]).

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}\Delta(G)&\text{if}\ \Delta(G)\geq
3\\\ 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.$

###### Proof 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 [8] gave a characterisation of line graphs by forbidden induced
subgraphs, which will be used in our proofs.

######  Theorem 27 (Beineke (1970) [8]).

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 Idea of 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 those forbidden induced subgraphs that do not
contain any graph from $N_{1},\ldots,N_{9}$ as an induced subgraph.

  * •

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$ do 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. 1.

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

  2. 2.

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

  3. 3.

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

  4. 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 two basic lemmata are implied by Theorem 23.

######  Lemma 29.

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

######  Lemma 30.

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

From the lemmata above we conclude the following.

######  Proposition 31.

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, $G$ is line $[A,-]$-perfect if and only if
no graph in $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, by Lemma 30, 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,-]$

The following basic lemmata are implied by Theorem 23.

######  Lemma 32.

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

######  Lemma 33.

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

######  Lemma 34.

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

######  Lemma 35.

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

######  Lemma 36.

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

######  Lemma 37.

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

######  Lemma 38.

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

From the lemmata above we conclude the following.

######  Proposition 39.

A graph is line $[B,-]$-perfect graph 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 $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 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}\\}.$

By the lemmata above (Lemma 32 – Lemma 38), 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 41, Lemma 44, and Lemma 47.

Figure 10: The precoloured configuration $F_{1}^{1}$

######  Lemma 40.

Bob has a winning strategy with 3 colours in the $[X,A]$-edge colouring game
on the precoloured graph $F_{1}^{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 41.

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 40. ∎

###  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 42.

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 43.

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 44.

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_{1,1}$, $e_{2}$, $e_{0}$, or $f_{0}$
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 40, 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 40.)

  * •

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 46.

######  Lemma 45.

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 1, 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 46.

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 45, 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 45, 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 41.

  * •

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 3 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 47.

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 40. ∎

##  5 The permitted types

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

We start with some definitions.

######  Definition 48 (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 49 (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 centers 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}$.

vase of 5 flowers

$(4,3)$-double star

Figure 15: A vase of flowers and a double star

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

######  Lemma 50.

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 51 (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 52 (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 53 (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 54 (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.

$(4,2,3)$-candy

double vase of 5 flowers

$(5,3)$-shooting star

$(5,3)$-amaryllis

Figure 16: A candy, a shooting star, a double vase, and an amaryllis.

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 55.

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 55 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 Andres and Lock [6, 23].

######  Lemma 56.

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 57.

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 58.

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 59 (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 60 (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 61 (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 62 (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 63 (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.

$(4,2,3)$-candy

$(4,2,3)$-star book

diamond of 5 flowers

tetrahedron of 5 flowers

$(2,3)$-single galaxy

$(2,3,4,5)$-double galaxy

Figure 17: A candy, a star book, a diamond of flowers, a tetrahedron of
flowers, a single galaxy and a double galaxy.

######  Lemma 64.

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 59.

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 55. 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 $[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 65.

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
60. 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 55.

  * •

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 56.

Thus, in any case, Alice wins. ∎

The next lemma is very similar to the preceeding one.

######  Lemma 66.

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 61. 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 55.

  * •

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
candy $T_{n}-\\{vu_{i},wu_{3-i}\\}$, which exists by Lemma 55.

  * •

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 64.

Thus, in any case, Alice wins. ∎

For a (single or double) galaxy with the notation of Definition 62 resp.
Definition 63, we call a $P_{3}$ pending at $v$ resp. a triangle (pending at
$v$) a _pending object_. The edges incident with $v$ are called _star edges_ ,
the other edge of a pending object is called _matching edge_.

######  Lemma 67.

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

###### Proof.

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

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 performs 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 edge or to an 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 68.

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

###### Proof.

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

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 67 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 67, 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 69 (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}$) leafs
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 70 (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.

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

######  Definition 71 (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}$) leafs
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 72 (satellite of type $E_{2}$).

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

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

$(3,4,5)$-full tree

$(4,5)$-satellite

Figure 18: A full tree and a satellite

######  Lemma 73.

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

###### Proof.

Let $G$ be a full tree with the vertex labels from Definition 69. 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 56.

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 inbetween.

Thus, in any case, Alice wins. ∎

######  Lemma 74.

A satellite (graph of type $E_{2}$) is line $[A,A]$-nice.

###### Proof.

Let $G$ be a satellite with the vertex labels from Definition 71. 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 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 55, 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
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 56, 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 74, 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

###### Proof 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 42 for path $P_{6}$, in Lemma 44 for
the mini lobster $F_{2}$, and in Lemma 46 for the trigraph $F_{3}$. The
$C_{5}$ is not line perfect, thus it is not line $[A,A]$-perfect (see Lemma
43). $F_{1}$ is not line $[B,A]$-nice by Lemma 41, so $F_{1}\cup F_{1}$ is not
line $[A,A]$-nice (see Lemma 47).

(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}$, 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 $H$ can only contain one of the configurations
$K_{1,1,m}$ with $m\geq 2$ (a _nontrivial_ triangular book), a block
containing at least one 4-cycle, and $K_{4}$. Assume to the contrary, $H$
contains two of them. 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 block containing at
least one 4-cycle. Assume to the contrary, $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$, 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}$.

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).

(a)

(b)

(c)

(d)

(e)

Figure 19: Creating forbidden configurations in Case 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 used never, 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 the cases whether 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.

  * •

Subcase 4.1: $a=2$.

The component $H$ is a star book with exactly one triangle if exactly two of
$v_{1},v_{2},v_{3}$ have at least one pending $P_{2}$, given that the block
containing $v_{1},v_{2},v_{3}$ is a triangle but neither the diamond (which
was discussed in Case 2) nor $K_{4}$ (which was discussed in Case 1).

  * •

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.

  * •

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 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 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 are line $[A,A]$-nice: we have proved this for
the candy in Lemma 55, for the star book in Lemma 64, for the single galaxy in
Lemma 67, for the double galaxy in Lemma 68, for the diamond of flowers in
Lemma 65, for the tetrahedron of flowers in Lemma 66, for the full tree
$E_{1}$ in Lemma 73, and for the satellite in Lemma 74. 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 lemmata mentioned above, Alice will win. Thus $G$ is
$[A,A]$-nice.

In Table 1 it is shown 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).

∎

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 least one
satellite or full tree.

###  6.2 Proof of Theorem 10

###### Proof 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 42 and Lemma 43, $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 41.

(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
graph $E_{1}$, or a satellite. Since a full graph of type $E_{1}$ and a
satellite of type $E_{2}$ contain a 3-caterpillar no component of $G$ is a
full graph 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 have proved this for
the candy in Lemma 55, for the star book in Lemma 64, for the single galaxy in
Lemma 67, for the double galaxy in Lemma 68, for the diamond of flowers in
Lemma 65, and for the tetrahedron of flowers in Lemma 66.

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

###### Proof of Theorem 11.

We prove the equivalence by a ring closure.

(1)$\Longrightarrow$(2)

This implication is part of Proposition 39.

(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 50, 55, 56, 57, and 58,
the graph $G$ is line $[B,-]$-perfect, i.e., (1) holds.

∎

###  6.4 Proof of Theorem 12

###### Proof 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 31.

(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
50, 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. 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 reseach.

######  Problem 75.

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

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.

## References

  * [1] S. D. Andres, The game chromatic index of forests of maximum degree $\Delta\geq 5$. Discrete Appl. Math. 154 (2006) 1317–1323.
  * [2] S. D. Andres, Digraph coloring games and game-perfectness. Ph.D. thesis, Universität zu Köln. Verlag Dr. Hut, München, 2007.
  * [3] S. D. Andres, Game-perfect graphs. Math. Methods Oper. Res. 69 (2009) 235–250.
  * [4] S. D. Andres, On characterizing game-perfect graphs by forbidden induced subgraphs. Contributions to Discrete Math. 7 (2012) 21–34.
  * [5] S. D. Andres, W. Hochstättler, and C. Schallück, The game chromatic index of wheels. Discrete Applied Math. 159 (2011) 1660–1665.
  * [6] S. D. Andres and E. Lock, Characterising and recognising game-perfect graphs. Discrete Math. Theor. Comput. Sci. 21:1 (2019) #6, 39pp.
  * [7] T. Bartnicki and J. Grytczuk, A note on the game chromatic index of graphs. Graphs Comb. 24 (2008) 67–70.
  * [8] L. W. Beineke, Characterizations of derived graphs. J. Combin. Theory 9 (1970) 129–135.
  * [9] A. Beveridge, T. Bohman, A. Frieze, and O. Pikhurko, Game chromatic index of graphs with given restrictions on degrees. Theoret. Comput. Sci. 407 (2008) 242–249.
  * [10] H. L. Bodlaender, On the complexity of some coloring games. Int. J. Found. Comput. Sci. 2 (1991) 133–147.
  * [11] O. Boudon, J. Przybyło, M. Senhaji, E. Sidorowicz, É. Sopena, and M. Woźniak, The neighbour-sum-distinguishing edge-colouring game. Discrete Math. 340 (2017) 1564–1572.
  * [12] L. Cai and X. Zhu, Game chromatic index of $k$-degenerate graphs. J. Graph Theory 36 (2001) 144–155.
  * [13] W. H. Chan and G. Nong, The game chromatic index of some trees of maximum degree 4. Discrete Applied Math. 170 (2014) 1–6.
  * [14] C. Charpentier, B. Effantin, and G. Paris, On the game coloring index of $F^{+}$-decomposable graphs. Discrete Appl. Math. 236 (2018) 73–83.
  * [15] C. Dunn, The relaxed game chromatic index of $k$-degenerate graphs. Discrete Math. 307 (2007) 1767–1775.
  * [16] C. Dunn, D. Morawski, and J. F. Nordstrom, The relaxed edge-coloring game and k-degenerate graphs. Order 32 (2015) 347–361.
  * [17] W. L. Fong and W. H. Chan, The edge coloring game on trees with the number of colors greater than the game chromatic index. J. Combin. Opt. 38 (2019) 456–480.
  * [18] 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:1904.01496 (2019) 36pp.
  * [19] 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. J. Comb. Optim. 36 (2018) 1–12.
  * [20] M. Gardner, Mathematical games. Scientific American 244 (April, 1981) 23–26.
  * [21] R. Keusch, A new upper bound on the game chromatic index of graphs. Electron. J. Combin. 25 (2018) Paper 2.33, 18pp.
  * [22] P. C. B. Lam, W. C. Shiu, and B. Xu, Edge game-coloring of graphs. Graph Theory Notes N.Y. 37 (1999) 17–19.
  * [23] E. Lock, The structure of $g_{B}$-perfect graphs. Bachelor’s thesis, FernUniversität in Hagen, 2016.
  * [24] F. Maffray, Kernels in perfect line-graphs. J. Combin. Theory, Series B, 55 (1992) 1–8.
  * [25] L. E. Trotter, Line perfect graphs. Math. Programm. 12 (1977) 255–259.
  * [26] H. Whitney, Congruent graphs and the connectivity of graphs. Am. J. Math. 54 (1932) 150–168.