On kernels in strongly game-perfect digraphs and a characterisation of weakly game-perfect digraphs

Abstract

We prove that the game-perfect digraphs defined by Andres (2012) with regard to a digraph version of the maker-breaker graph colouring game introduced by Bodlaender (1991) always have a kernel. Furthermore, we introduce weakly game-perfect digraphs related to another digraph version of Bodlaender’s graph colouring game, which was defined by Yang and Zhu (2010), and characterise the classes of weakly game-perfect digraphs by means of the classes of undirected game-perfect graphs.

Keywords:

• Game-perfect digraph
• Game-perfect graph
• Game chromatic number
• Kernel
• Perfect digraph

1 Introduction

In this paper we consider two generalisations of game-perfectness of undirected graphs to digraphs. Before defining these notions we recall the way perfectness of undirected graphs is generalised to digraphs.

1.1 Perfect graphs

An undirected graph $G$ is perfect if, for any induced subgraph $H$ of $G$, the chromatic number $\chi \left(H\right)$ equals the clique number $\omega \left(H\right)$. The notion of perfectness was introduced by Berge [1]. Perfect graphs are of major importance in computer science, since some problems like the $k$-colouring problem for $k\ge 3$ which are NP-hard in general can be solved efficiently on perfect graphs [2]. By the Strong Perfect Graph Theorem [3], a graph is perfect if and only if it does neither have odd holes, which are odd cycles of length $\ge 5$, nor odd antiholes, which are complements of odd holes, as induced subgraphs.

The characterisation of perfect graphs given by the Strong Perfect Graph Theorem is a characterisation by a set of forbidden induced subgraphs. Every hereditary class of graphs (or digraphs) has a characterisation by forbidden induced sub(di)graphs. Made by definition, the class of perfect graphs is hereditary. In a similar way, the classes of digraphs that we will consider in this paper allow characterisations by forbidden induced sub(di)graphs. We aim to discover some of these characterisations.

1.2 Perfect digraphs

The notion of perfectness and the Strong Perfect Graph Theorem have been generalised to digraphs in the following way.

Key of the generalisation is the dichromatic number $\chi \left(D\right)$ of a digraph $D$, which is the smallest number of colours in a (not necessarily proper) colouring of the vertices of $D$, such that $D$ does not contain any monochromatic directed cycle. The concept of dichromatic number was first introduced by Neumann-Lara [4] and later reinvented by several authors under different names. For example Bokal et al. [5] call it chromatic number of a digraph.

The justification to use the same parameter $\chi$ for the dichromatic number of digraphs as well as for the chromatic number of undirected graphs is given by the observation that any colouring of a symmetric digraph must be proper, thus is a colouring of its underlying undirected graph. The size of a largest symmetric clique of a digraph $D$ is the clique number $\omega \left(D\right)$ of $D$. A digraph is perfect if, for any induced subdigraph, dichromatic number and clique number coincide. Andres and Hochstättler [6] generalised the Strong Perfect Graph Theorem to digraphs (see Theorem 1 in Section 3).

When one considers digraph classes, the kernel existence problem is a widely-used measure of the complexity of a given class of digraphs [7–9]. Recall that a kernel of a digraph $D=(V,A)$ is an independent and absorbing set $K$, i.e. for every two vertices $v,w\in K$ we have $(v,w)\notin A$ and for every vertex $u\in V\setminus K$ there is a vertex $v\in K$ such that $(v,u)\in A$. It is NP-complete to decide whether a digraph has a kernel, moreover it is even NP-complete to decide whether a perfect digraph has a kernel [6]. However, using Lovász’ (Weak) Perfect Graph Theorem [10] and a major result of Boros and Gurvich [11], Andres and Hochstättler [6] proved that the complement of any perfect digraph has a kernel.

1.3 Game-perfect graphs

The study of special classes of perfect graphs, such as split graphs, bipartite graphs and their complements, comparability graphs, etc., has received considerable attention [12]. Recently studied small classes of perfect graphs are the classes of game-perfect graphs. These are defined via a competitive version of the chromatic number, the so-called game chromatic number, introduced by Bodlaender [13]. This is based on the following graph colouring game, played by two players, Alice and Bob , with a finite undirected graph $G$ and a colour set $C$. At the beginning, every vertex is uncoloured. The players alternately choose an uncoloured vertex $v$ of $G$ and colour it with a colour $c$ from $C$ such that

(F)	the colour $c$ is different from the colours of every neighbour of $v$.

The game ends as soon as no such move is possible any more. Alice wins if every vertex is coloured. Otherwise Bob wins. Thus Bob wins if during the game an uncoloured vertex is surrounded by vertices of all colours.

Different variants of the game were considered concerning which player moves first or whether skipping is allowed for a player. For any variant $g$ of the game, the game chromatic number ${\chi }_g\left(G\right)$ of the graph $G$ is the smallest size of a colour set $C$ such that Alice has a winning strategy for the game played on $G$ with $\left|C\right|$ colours. This parameter is well-defined, since Alice always has a winning strategy with $1+\Delta \left(G\right)$ colours, where $\Delta \left(G\right)$ denotes the maximum degree of $G$. A graph $G$ is game-perfect with regard to the game variant $g$, or, $g$-perfect for short, if, for every induced subgraph $H$ of $G$, we have ${\chi }_g\left(H\right)=\omega \left(H\right)$.

A structural characterisation of game-perfect graphs by forbidden induced subgraphs has been given for some variants of this game by Andres [14], Lock [15], and Andres and Lock [16].

1.4 Game-perfect digraphs

Two ways of generalising the game-chromatic number from undirected graphs to digraphs have been proposed. We first consider a notion of game-perfectness related to the weak game chromatic number ${\chi }_{wg}\left(D\right)$ of a digraph $D$, which is very much inspired by Neumann-Lara’s notion of the dichromatic number. The weak game chromatic number and its underlying game were introduced by Yang and Zhu [17]. The rules of this so-called weak digraph colouring game $wg$ (or, weak game, for short) are the same as for the graph colouring game except that the graph $G$ is replaced by a digraph $D$ and the feasibility condition ($F$) is replaced by the condition

(Fw)	no monochromatic directed cycles are created.

The second way to generalise the game-chromatic number is inspired by the importance of neighbourhoods in the graph colouring game and was studied already by Andres [18,19], Yang and Zhu [17], and Chan et al. [20]. In the strong digraph colouring game $sg$ (or, strong game, for short), the feasibility condition ($F_w$) is replaced by

(Fs)	the colour $c$ is different from the colours of every in-neighbour of $v$.

As in the weak game, Alice wins if every vertex is coloured at the end. Then the colour classes are acyclic. But in the strong game Bob wins already if an uncoloured vertex is surrounded by in-neighbours of all colours, even if this partial colouring could be extended to a colouring where all colour classes are acyclic.

As for the game $g$ in the undirected case, we may specify the player $X\in \{A,B\}$ who starts and the player $Y\in \{A,B,-\}$ who has the right to skip, where “$A$” resp. “$B$” denote Alice resp. Bob and “$-$” denotes “none of the players”. This defines six different weak games of the form $wg=w[X,Y]$ resp. six different strong games $sg=s[X,Y]$ for digraphs with regard to the associated games $g=[X,Y]$ for undirected graphs (see Section 2).

Then for each of these variants we may define the weak resp. strong game chromatic number as the smallest number of colours such that Alice has a winning strategy for this variant of the weak resp. strong digraph colouring game. We define a digraph to be weakly resp. strongly game-perfect if, for any induced subdigraph, weak resp. strong game chromatic number and clique number coincide. In [19], strongly game-perfect digraphs were introduced and the classes of strongly game-perfect biorientations of paths and cycles were characterised.

1.5 Our contribution

This paper initiates the study of weakly game-perfect digraphs and has two main results.

First, we reduce the characterisation of weakly game-perfect digraphs to the characterisation of game-perfect graphs. Together with the characterisations from [14] and [15,16], this gives us complete characterisations of weakly game-perfect digraphs for the games $w[B,B]$, $w[A,B]$, $w[A,-]$ and $w[B,-]$ by forbidden induced subdigraphs.

Second, we show that every strongly game-perfect digraph with regard to the game $s[A,-]$ has a kernel.

The paper is structured as follows. In Section 2 we introduce the notation. In Section 3 we summarise some previous results needed for our proofs. Section 4 contains the characterisation of weakly game-perfect digraphs. Kernels in strongly game-perfect digraphs are studied in Section 5. Implications of our work and open problems are described in the final Section 6.

2 Notation

For all terminology on digraphs we refer to Bang-Jensen and Gutin [21]. All digraphs we consider are without loops and without multiple arcs, however pairs $(v,w)$ and $(w,v)$ of antiparallel arcs are allowed. By $D^C$ we denote the complement of a digraph $D$, i.e. the arc set of $D^C$ consists of all arcs $(v,w)$ with $v\ne w$, such that $(w,v)$ is not an arc of $D$. Undirected graphs are considered as symmetric digraphs, i.e. those digraphs where for any arc $(v,w)$ there also exists the arc $(w,v)$. A pair $\{(v,w),(w,v)\}$ with $v\ne w$ is called an edge. An arc $(v,w)$ such that $(w,v)$ is not an arc is called single arc. For a digraph $D=(V,A)$, the symmetric digraph $S\left(D\right)≔(V,A^{\prime })$, where $A^{\prime }$ is the union of all edges of $D$ (i.e. the set of all arcs $(v,w)\in A$ such that also $(w,v)\in A$), is called symmetric part of $D$.

A symmetric clique is a symmetric digraph where for every ordered pair $(v,w)$ of distinct vertices the arc $(v,w)$ exists. The clique number $\omega \left(D\right)$ of a digraph $D$ is the size of the largest symmetric clique in $D$. In line with the undirected case, a digraph $D$ is perfect if, for any induced subdigraph $H$ of $D$, we have the equality $\chi \left(H\right)=\omega \left(H\right)$. A filled odd hole resp. a filled odd antihole is a digraph $H$ such that its symmetric part $S\left(H\right)$ is an odd hole resp. an odd antihole. More generally, for any graph $G$, a filled$G$ is a digraph $D$ with $S\left(D\right)=G$. See Figs. 1 and 2 for examples. In all depictions, edges $\{(v,w),(w,v)\}$ are depicted as fat lines, single arcs $(v,w)$ as arrows.

Fig. 1 The 15 filled $P_4$s.

Fig. 2 The 3 filled $C_4$s.

By $K_n$, $P_n$, and $C_n$ we denote symmetric cliques, paths and cycles with $n$ vertices, respectively. ${\overrightarrow{P}}_n$ and ${\overrightarrow{C}}_n$ denote directed paths and directed cycles with $n$ vertices, respectively. The disjoint union $G_1\cup G_2$ of two graphs $G_1$ and $G_2$ is the graph consisting of an isomorphic copy $G_1^{\prime }$ of $G_1$ and an isomorphic copy $G_2^{\prime }$ of $G_2$ with disjoint vertex sets and no edges between $G_1^{\prime }$ and $G_2^{\prime }$. The join $G_1\vee G_2$ of $G_1$ and $G_2$ is built from $G_1\cup G_2$ by connecting every vertex of $G_1^{\prime }$ with every vertex of $G_2^{\prime }$ by an edge. The disjoint union $$\underset{n}{\underbrace{G\cup \cdots \cup G}}$$of $n$ disjoint copies of the same graph $G$ is denoted as $nG$.

We consider six variants of each of the digraph colouring games, denoted by the symbols $wg$ and $sg$ for the weak and the strong game, respectively, where $g≔[X,Y]$, with $X\in \{A,B\}$ and $Y\in \{A,B,-\}$. $X$ denotes the player who has the first move. $Y$ denotes a player that has the right to miss one or several turns at any time of the game, including the first move; $Y=$“$-$” means that none of the players has this right. We also use the abbreviations $g_A≔[A,-]$ and $g_B≔[B,-]$.

The weak (resp. strong) game chromatic number ${\chi }_{wg}\left(D\right)$ (resp. ${\chi }_{sg}\left(D\right)$) of a digraph $D$ with regard to the game $wg$ (resp. $sg$) is the smallest size $\left|C\right|$ of a colour set $C$ such that Alice has a winning strategy for the weak (resp. strong) digraph colouring game $wg$ (resp. $sg$) played on $D$ with colour set $C$.

We define a digraph $D$ to be weakly game-perfect with regard to the game $wg$ (or, weakly $g$-perfect, or $wg$-perfect for short) if, for any induced subdigraph $H$ of $D$, ${\chi }_{wg}\left(H\right)=\omega \left(H\right)$. The digraph $D$ is strongly game-perfect with regard to the game $sg$ (or, strongly $g$-perfect, or $sg$-perfect for short) if, for any induced subdigraph $H$ of $D$, ${\chi }_{sg}\left(H\right)=\omega \left(H\right)$. Note that for undirected graphs, considered as symmetric digraphs, the games $wg$ and $sg$ are equal, therefore the notions of weak and strong game chromatic number and thus the notions of weakly and strongly game-perfect coincide. For the games $wg$ and $sg$, when played on an undirected graph, we use simply the symbol $g$. The game $g_A$ is the original maker-breaker graph colouring game introduced by Bodlaender [13].

3 Observations and previous results

In this section we list some facts that we will use in our proofs.

3.1 Perfect digraphs

Theorem 1

Andres and Hochstättler [6, Cor. 5] A digraph is perfect if and only if it does neither have filled odd holes nor filled odd antiholes nor directed cycles of length $\ge 3$ as induced subdigraphs.

Theorem 2

Andres and Hochstättler [6, Cor. 13] For any perfect digraph $D$, the complement $D^C$ has a kernel.

Theorem 1 is the generalisation of the Strong Perfect Graph Theorem to digraphs. As already mentioned in the introduction, Theorem 2 is related to the Weak Perfect Graph Theorem.

3.2 Colouring games

We have the following obvious relations of colouring parameters.

Observation 3

For any digraph $D$ and any $X\in \{A,B\}$,$Y\in \{A,B,-\}$,

(a)	$\omega \left(D\right)\le \chi \left(D\right)\le {\chi }_{w[X,Y]}\left(D\right)$,
(b)	$\omega \left(D\right)\le \chi \left(D\right)\le {\chi }_{s[X,Y]}\left(D\right)$.

Observation 4

For any digraph $D$,

(a)	${\chi }_{w[B,B]}\left(D\right)\ge {\chi }_{w[A,B]}\left(D\right)\ge {\chi }_{w[A,-]}\left(D\right)\ge {\chi }_{w[A,A]}\left(D\right)$,
(b)	${\chi }_{w[B,B]}\left(D\right)\ge {\chi }_{w[B,-]}\left(D\right)\ge {\chi }_{w[B,A]}\left(D\right)\ge {\chi }_{w[A,A]}\left(D\right)$,
(c)	${\chi }_{s[B,B]}\left(D\right)\ge {\chi }_{s[A,B]}\left(D\right)\ge {\chi }_{s[A,-]}\left(D\right)\ge {\chi }_{s[A,A]}\left(D\right)$,
(d)	${\chi }_{s[B,B]}\left(D\right)\ge {\chi }_{s[B,-]}\left(D\right)\ge {\chi }_{s[B,A]}\left(D\right)\ge {\chi }_{s[A,A]}\left(D\right)$.

By Observation 4, some of the classes of weakly resp. strongly game-perfect digraphs are related in an obvious way, as depicted in Fig. 3. By Observation 3, weakly resp. strongly game-perfect digraphs are, in particular, perfect.

Fig. 3 Inclusions of the classes of game-perfectness: $GP[X,Y]$ might be the class of either game-perfect graphs or weakly game-perfect digraphs or strongly game-perfect digraphs with regard to game variant $[X,Y]$.

3.3 Characterisations of game-perfect graphs

A structural characterisation of game-perfect graphs by a set of 4, 7, 7, and 15 forbidden induced subgraphs has been given for the games $[B,B]$, $[A,B]$ and $[A,-]$ in [14] and for the game $[B,-]$ in [15,16], respectively. A characterisation for the richest classes, the $[B,A]$-perfect and $[A,A]$-perfect graphs, is still an open problem.

We summarise the characterisations of game-perfect graphs by forbidden induced subgraphs.

Theorem 5

Andres [14, Thm. 3] A graph $G$ is$[B,B]$-perfect if and only if it contains no induced $P_4$,$C_4$,$K_2\vee 3K_1$,$K_1\vee 2P_3$.

Theorem 6

Andres [14, Thm. 7]

(a)	A graph $G$ is $g_A$-perfect if and only if it is $[A,B]$-perfect.
(b)	A graph $G$ is $g_A$-perfect if and only if it contains no induced $P_4$, $C_4$, $K_3\vee 3K_1$, $K_2\vee 2P_3$, $2(K_2\vee 3K_1)$, $2(K_1\vee 2P_3)$, $(K_2\vee 3K_1)\cup (K_1\vee 2P_3)$.

Theorem 7

Lock [15, Thm. 14], Andres and Lock [16, Thm. 4] A graph $G$ is$g_B$-perfect if and only if it contains no induced $P_5$,$C_5$,$K_2\vee 3K_1$,$K_1\vee 2P_3$,$P_4\cup K_1$,$C_4\cup K_1$,$P_4\vee K_1$,$C_4\vee K_1$, chair,$F_{10},\dots ,F_{15}$ (seeFig. 4).

Fig. 4 Some additional forbidden induced subgraphs in $[B,-]$-perfect graphs.

4 Weakly game-perfect digraphs

As we shall see in Theorem 9, the characterisation of weakly game-perfect digraphs with regard to a game $wg$ can be easily reduced to the characterisation of game-perfect (undirected) graphs with regard to the associated game $g$.

The proof of Theorem 9 uses basically the same idea as the main theorem for characterising perfect digraphs by means of perfect graphs in [6]. We start with an obvious observation.

Observation 8

In a digraph $D$ that contains no directed cycle ${\overrightarrow{C}}_n$ with $n\ge 3$ as an induced subdigraph, every directed cycle has an edge as a chord.

Theorem 9

For a weak game $wg$ and the associated undirected game $g$, a digraph $D$ is $wg$-perfect if and only if the following two conditions hold.

(i)	The symmetric part $S\left(D\right)$ is a $g$-perfect graph.
(ii)	$D$ contains no directed cycle ${\overrightarrow{C}}_n$ with $n\ge 3$ as an induced subdigraph.

Proof

First, we show that (i) and (ii) are necessary conditions for $wg$-perfectness. Assume that (ii) does not hold, i.e. let $D$ contain an induced directed cycle of length at least 3. Then $D$ is not perfect, thus it is not $wg$-perfect. By contraposition, (ii) is necessary for $wg$-perfectness.

Now, in order to prove that (i) is necessary, we may assume that (ii) holds, i.e. $D$ does not contain any directed cycles of length at least 3. Assume that (i) does not hold, i.e. let $S\left(D\right)$ be a non-$g$-perfect graph. This means that there exists an induced subdigraph $H$ of $D$ such that Bob has a winning strategy for the game $g$ played on $S\left(H\right)$ with $\omega \left(S\left(H\right)\right)$ colours. He uses the same strategy for the game $wg$ played on the digraph $H$ with $\omega \left(H\right)=\omega \left(S\left(H\right)\right)$ colours. The single arcs do not restrict him in doing so, since whenever he would be forced by his strategy to close a monochromatic directed cycle, then by Observation 8 this cycle would either be a monochromatic edge or have a monochromatic edge as a chord, neither of which is possible in his strategy for the game $g$ on $S\left(H\right)$. Therefore every move of Bob is feasible in the game $wg$ until he creates a win for him or forces Alice to do so, which will happen, since his strategy is a winning strategy on $S\left(H\right)$. Therefore $D$ is not $wg$-perfect. By contraposition, (i) is necessary for $wg$-perfectness.

Second, we show that (i) and (ii) imply that $D$ is $wg$-perfect. Let $S\left(D\right)$ be a $g$-perfect graph and $D$ not contain any induced directed cycle of length $\ge 3$. Let $H$ be an induced subdigraph of $D$. Then $S\left(H\right)$ is an induced subgraph of $S\left(D\right)$. Thus, Alice has a winning strategy for the game $g$ played on $S\left(H\right)$ with $\omega \left(S\left(H\right)\right)$ colours. She uses the same strategy for the game $wg$ played on $H$ with $\omega \left(H\right)=\omega \left(S\left(H\right)\right)$ colours. Assume Alice is forced by her strategy to close a monochromatic directed cycle. Then by Observation 8 this cycle would either be a monochromatic edge or have a monochromatic edge as a chord, neither of which is possible in her strategy for the game $g$ on $S\left(H\right)$. Therefore every move of Alice is feasible in the game $wg$ until she creates a win for her, i.e. every vertex of $H$ is coloured, which will happen, since her strategy is a winning strategy on $S\left(H\right)$. Since $H$ was arbitrarily chosen, $D$ is $wg$-perfect. □

By the characterisations mentioned in Section 3 and Theorem 9 we obtain explicit characterisations for the four classes of weakly $[B,B]$-, $[A,B]$-, $g_A$- and $g_B$-perfect digraphs.

Corollary 10

A digraph $D$ is weakly$[B,B]$-perfect if and only if it contains no induced ${\overrightarrow{C}}_n$ ($n\ge 3$), filled$P_4$ (see Fig. 1), filled $C_4$ (seeFig. 2), filled $K_2\vee 3K_1$, filled $K_1\vee 2P_3$.

Corollary 11

(a)	A digraph $D$ is weakly $g_A$-perfect if and only if it is weakly $[A,B]$-perfect.
(b)	A digraph $D$ is weakly $g_A$-perfect if and only if it contains no induced ${\overrightarrow{C}}_n$ ($n\ge 3$), filled $P_4$ (see Fig. 1), filled $C_4$ (see Fig. 2), filled $K_3\vee 3K_1$, filled $K_2\vee 2P_3$, filled $2(K_2\vee 3K_1)$, filled $2(K_1\vee 2P_3)$, filled $(K_2\vee 3K_1)\cup (K_1\vee 2P_3)$.

Corollary 12

A digraph $D$ is weakly$g_B$-perfect if and only if it contains no induced ${\overrightarrow{C}}_n$ ($n\ge 3$) and no induced filled $G$, where $G$ is one of the graphs $P_5$,$C_5$,$K_2\vee 3K_1$,$K_1\vee 2P_3$,$P_4\cup K_1$,$C_4\cup K_1$,$P_4\vee K_1$,$C_4\vee K_1$, chair,$F_{10},\dots ,F_{15}$ (seeFig. 4).

Proof of Corollaries 10–12

By Theorem 9, $D$ is weakly game-perfect if and only if $S\left(D\right)$ is a game-perfect graph and $D$ contains no induced ${\overrightarrow{C}}_n$ with $n\ge 3$. Thus the corollaries follow from the equivalence $$S\left(D\right)\text{is game-perfect}\stackrel{\text{Theorems 5–7}}{⟺}S\left(D\right)\text{contains no induced subgraph from the list}{G}_1,\dots ,G_k⟺D\text{contains no induced subdigraph from filled}{G}_1,\dots ,\mathrm{filled}{G}_k,$$ where the list $G_1,\dots ,G_k$ is the list of forbidden subgraphs given in Theorem 5 (in the case of Corollary 10), Theorem 6 (in the case of Corollary 11), and Theorem 7 (in the case of Corollary 12), respectively. □

We remark that game-perfect graphs for the four variants of the game considered above can be described by finitely many forbidden induced subgraphs, whereas perfect graphs, perfect digraphs and weakly game-perfect digraphs require infinitely many forbidden configurations.

5 Existence of kernels in strongly game-perfect digraphs

The existence of kernels in strongly game-perfect digraphs depends on the non-existence of a single configuration, ${\overrightarrow{C}}_4^C$, the complement of a directed 4-cycle. The key for our analysis is the following.

Theorem 13

Let $D$ be a strongly$[A,A]$-perfect digraph that does not contain an induced ${\overrightarrow{C}}_4^C$. Then $D$ is the complement of a perfect digraph.

In order to prove Theorem 13 and our second main result, its Corollary 18, we will start with three simple lemmas. Let $H_3≔K_3-(b,a)$ the digraph that is constructed from the symmetric clique $K_3$ on the vertices $a,b,d$ by deleting the arc $(b,a)$ (see Fig. 5 (a)).

Fig. 5 The digraphs in Lemma 14–16.

Lemma 14

The digraph $H_3$ is not $s[A,A]$-perfect.

Proof

We will prove that Bob has a winning strategy for the game $s[A,A]$ played on $H_3$ with $\omega \left(H_3\right)=2$ colours. We make a case distinction according to Alice’s first move. Note that the only feasible 2-colouring of $H_3$ is to colour $a,b$ in the same colour and $d$ with the other colour. If Alice colours $a$ or $b$, Bob can easily avoid this situation by colouring the other one of these two vertices with the other colour, thus he wins in this case. If Alice skips or colours $d$, Bob colours $a$ and wins, since now $b$ must be coloured differently from $a$ by the rules of the strong game. □

Lemma 15

The digraph ${\overrightarrow{P}}_4^C$ is not $s[A,A]$-perfect.

Proof

This is implied by Lemma 14, since $H_3$ is an induced subdigraph of ${\overrightarrow{P}}_4^C$ (see Fig. 5 (b)). □

Lemma 16

The digraph ${\overrightarrow{C}}_4^C$ is not $s{g}_A$-perfect.

Proof

We will prove that Bob has a winning strategy for the game $s[A,-]$ played on ${\overrightarrow{C}}_4^C$ with $\omega \left({\overrightarrow{C}}_4^C\right)=2$ colours. Let the vertices be labelled as in Fig. 5 (c). By symmetry, Alice w.l.o.g. colours $a$ in her first move. Then Bob colours $d$ with the other colour. Since $b$ is surrounded by in-neighbours in all colours, Bob wins. □

Proof of Theorem 13

$D$ is a perfect digraph, since every strongly game-perfect digraph is perfect by Observation 3. By Theorem 1, $D$ has neither an induced filled odd hole nor an induced filled odd antihole nor an induced complement of a directed 3-cycle (since a directed 3-cycle is self-complementary). By precondition, $D$ has no induced complement of a directed 4-cycle. By Lemma 15, $D$ has no complement of a directed $n$-cycle, $n\ge 5$. (Indeed, any four consecutive vertices in a directed cycle ${\overrightarrow{C}}_n$ of length $n\ge 5$ would induce the complement of a directed path ${\overrightarrow{P}}_4$ in the complement ${\overrightarrow{C}}_n^C$ of ${\overrightarrow{C}}_n$ (see Fig. 6), which, by Lemma 15, is not $s[A,A]$-perfect.) Therefore $D^C$ is a digraph without induced filled odd hole and without induced filled odd antihole and without induced directed cycles of length $\ge 3$. From Theorem 1 follows that $D^C$ is perfect. □

Fig. 6 For $n\ge 5$, ${\overrightarrow{C}}_n^C$ contains an induced ${\overrightarrow{P}}_4^C$.

Corollary 17

of Theorem 13 Let $D$ be a strongly$[A,A]$-perfect digraph that does not contain an induced ${\overrightarrow{C}}_4^C$. Then $D$ has a kernel.

Proof

Let $D$ be a strongly game-perfect digraph (with regard to the game $s[A,A]$) that does not contain a ${\overrightarrow{C}}_4^C$. By Theorem 13, $D^C$ is perfect. Therefore, by Theorem 2, $D$ has a kernel. □

Corollary 18

Let $D$ be a strongly $g_A$-perfect digraph. Then $D$ has a kernel.

Proof

By Observation 4, $D$ is $s[A,A]$-perfect. By Lemma 16, $D$ contains no induced ${\overrightarrow{C}}_4^C$. Therefore, by Corollary 17, $D$ has a kernel. □

We remark that in the class of $s[A,A]$-perfect digraphs that contain an induced ${\overrightarrow{C}}_4^C$ there exist members that do not have a kernel, e.g. the ${\overrightarrow{C}}_4^C$, and members that have a kernel, as shown in Example 19.

Example 19

The digraph $D_0$ from Fig. 7 (b), which we call ${\overrightarrow{C}}_4^C$ with roof, is $s[A,A]$-perfect and has a kernel.

Fig. 7 Two $s[A,A]$-perfect digraphs: (a) The ${\overrightarrow{C}}_4^C$; (b) $D_0$: the ${\overrightarrow{C}}_4^C$ with roof.

Proof

The digraph $D_0$ has a kernel: e.g. a kernel consists of the two circled vertices in Fig. 7 (b). We have to prove that $D_0$ is $s[A,A]$-perfect, i.e. Alice has a winning strategy for any subdigraph $H$ of $D_0$ when the game $s[A,A]$ is played on $H$ with $\omega \left(H\right)$ colours. For the subdigraphs with 0, 1, 2 or 3 vertices such a strategy is trivial. Therefore we are left to consider $D_0$ and its (up to isomorphism) three subdigraphs of order 4, namely ${\overrightarrow{C}}_4^C$ and the digraphs $D_1$ and $D_2$ from Fig. 8.

Alice’s strategy with 3 colours on $D_0$ is the following. We call the vertex that is not in the ${\overrightarrow{C}}_4^C$ roof vertex, its two neighbours base vertices, and the other two vertices diagonal vertices. In her first move, Alice colours the roof vertex with colour 1. If Bob colours a base vertex with colour 2, then Alice colours the other base vertex with colour 3. If Bob colours a diagonal vertex with colour 2, then Alice proceeds in the same way, i.e. she colours the other diagonal vertex with colour 3. Then, in any case one of the remaining vertices can be coloured at least in colour 3 but not in colour 2, the other at least in colour 2 but not in colour 3, thus there is no move of Bob to avoid the digraph getting completely coloured in the remainder of the game. If, otherwise, Bob, in his first move, colours a diagonal vertex $v$ with colour 1, then Alice colours the base vertex that is the in-neighbour of $v$ with colour 2. Also in this case the last two vertices are forced to be coloured feasibly.

Alice’s strategy with 2 colours on ${\overrightarrow{C}}_4^C$ is the following. She misses her first turn. Then she replies on Bob’s move as in the preceeding strategy: If Bob colours a vertex with colour 1, she colours the vertex connected to it by an edge with colour 2. This will lead into a winning situation for her by the same arguments as in the case of $D_0$.

Alice’s strategy with 3 colours on $D_1$ is the following. She misses her first turn and then follows a copycat strategy: if Bob colours a central vertex, she colours the other central vertex; if Bob colours another vertex with colour $c$, she colours its non-neighbour with $c$. This obviously will make her win.

Alice’s strategy with 2 colours on $D_2$ is the following. In her first move she colours the vertex pointed at in Fig. 8 with colour 1. If Bob colours its edge-neighbour with colour 2, Alice may colour the central vertex with colour 1 to make Bob complete the colouring. If Bob colours a vertex of the uncoloured edge, Alice colours the other vertex of the uncoloured edge with the other colour. Since the last vertex has no in-neighbour in this edge, it may be coloured in colour 2 anyway. Therefore, Alice wins in any case. □

Fig. 8 Two subdigraphs of order 4 of the ${\overrightarrow{C}}_4^C$ with roof.

6 Final remarks

Andres [19] proved that every strongly game-perfect digraph has diameter at most 8. Therefore it is easy to see that the classes of weakly game-perfect digraphs are much richer than the classes of strongly game-perfect digraphs. Indeed, for any game variant $g$ and its corresponding weak variant $wg$, every orientation of a forest of diameter greater than 8 is weakly game-perfect, but not strongly game-perfect.

We might ask for a characterisation of strongly game-perfect digraphs. For the games, where Bob begins, this can be easily reduced to the case of undirected graphs, since in these cases the oriented path ${\overrightarrow{P}}_2$ is not game-perfect (cf. Fig. 9 (a)), implying that single arcs are forbidden, thus in these cases we have the following.

Fig. 9 (a) ${\overrightarrow{P}}_2$ is not $[B,Y]$-perfect for every $Y\in \{A,B,-\}$ (b) $2{\overrightarrow{P}}_2$ is not game-perfect for any game.

Observation 20

Andres [19, Prop. 2] Let $g\in \{g_B,[B,A],[B,B]\}$. Then every $sg$-perfect digraph is an undirected graph.

The characterisations of game-perfect graphs for the game $[B,B]$ by a set of 4 forbidden induced subgraphs in Theorem 5 resp. for the game $g_B$ by a set of 15 forbidden induced subgraphs in Theorem 7 are thus an answer for the characterisation of $s[B,B]$- resp. $s{g}_B$-perfect digraphs, too.

Problem 21

Characterise the class of $[B,A]$-perfect graphs by a set of forbidden induced subgraphs.

Problem 22

Characterise the classes of $s[A,A]$-, $s{g}_A$- resp. $s[A,B]$-perfect digraphs by sets of forbidden induced subdigraphs, respectively.

A partial result characterising the strongly game-perfect biorientations of forests has been recently obtained by Andres, Charpentier and Fong [22].

Observation 20 implies immediately also the following.

Corollary 23

Let $g\in \{g_B,[B,A],[B,B]\}$. Then every strongly $g$-perfect digraph has a kernel.

By Observation 4, we get from Corollary 18 the following.

Corollary 24

Every strongly $[A,B]$-perfect digraph has a kernel.

Problem 25

Characterise which of the strongly $[A,A]$-perfect digraphs with a ${\overrightarrow{C}}_4^C$ has a kernel.

As already mentioned, it is NP-complete to decide whether a perfect digraph has a kernel (cf. [6]). In contrast to that we conjecture that the solution to Problem 25 is easy. Conjecture 26 is supported by the observation that, since $2{\overrightarrow{P}}_2$ is forbidden in any strongly game-perfect digraph (cf. Fig. 9 (b)), on the one hand only one of the components of a game-perfect digraph is not an undirected graph, and undirected graphs always have a kernel, on the other hand the structure of the non-symmetric component is forced to be quite simple and, thus, might be characterised by finitely many efficient rules.

Conjecture 26

There is a polynomial time algorithm to decide whether a strongly game-perfect digraph has a kernel.

One might also ask which weakly game-perfect digraphs admit a kernel.

Problem 27

Characterise the subclass of digraphs admitting a kernel among the weakly game-perfect digraphs (for the different variants of the game). Or at least, determine the complexity of deciding whether a weakly game-perfect digraph has a kernel.