$P_{11}$-Coloring of Oriented Graphs

Abstract

We show that, every oriented graph with maximum average degree less than 28/9 admits a homomorphism into the Paley tournament with 11 vertices.

1 Introduction

This paper is concerned with oriented graphs, that is digraphs without loops or opposite arcs. If G is an oriented graph, then we write $G=(V, A)$, where $V=V(G)$ and $A=A(G)$ are respectively the vertex set and arc set of G. For an unoriented graph G, $E=E(G)$ will denote the edge set of G. For an (oriented) graph G, |G| and ||G|| will denote respectively |V(G)| and |E(G)| (|A(G)|). A k-path in an oriented graph is a path with k edges. We will refer to a 2-path $v_0 v_1 v_2$ as directed if there are arcs from $v_0$ to $v_1$ and $v_1$ to $v_2$ or from $v_2$ to $v_1$ and $v_1$ to $v_0$, non-directed otherwise. All graphs will be finite in this paper.

A homomorphism from $G_1=(V_1, A_1)$ to $G_2 = (V_2, A_2)$ is a function $\phi : V_1 \rightarrow V_2$ such that, if $(u,v) \in A_1$, then $(\phi (u),\phi (v)) \in A_2$. A homomorphism from G to H is also referred to as an H-coloring of G, and the vertices of H as colors. If such a homomorphism exists we say that G is H-colorable, this terminology being suggested by the fact that, for an unoriented graph, a proper vertex coloring with n colors is equivalent to a homomorphism to the complete graph $K_n$. An oriented graph is H-critical if it has no H-coloring, but every proper subgraph of it has. We say that a configuration is H-reducible if no H-critical graph can contain it.

The average degree, $\mathrm{ad}(G)$, of a graph G is defined by $\mathrm{ad}(G)=2||G||/|G|$. From this we define the maximum average degree, $\mathrm{mad}(G)$, of G as the maximum of $\mathrm{ad}(H)$ taken over all subgraphs H of G.

Much work has has been done showing that the members of a certain class of oriented graphs (e.g. planar graphs, graphs with bounded maximum average degree, bounded treewidth, etc.) are all H-colorable for a certain graph H. Borodin et al. [1] have proved (among several similar results) that every oriented graph G with $\mathrm{mad}(G)<$3 is $P_{11}$-colorable, where $P_{11}$ is the Paley tournament on 11 vertices (see below). Our main theorem is a strengthening of this result.

Theorem 1

Every oriented graph G with $\mathrm{mad}(G)<28/9$ is $P_{11}$-colorable. This bound is sharp.

Fig. 1

A forbidden graph

A forbidden graph is an oriented graph with the same underlying unoriented graph as the graph shown in Fig. 1, oriented such that the 2-paths $a_1 v a_2$ and each $v_i x_i v_{i+1}$ (subscripts modulo 3) are all directed in either direction, and all the arcs between the vertex sets $\{a_1,a_2\}$ and $\{v_1,v_2,v_3\}$ are in the same direction. Figure 1 shows one such orientation, and there are three more (up to isomorphism). These can be obtained from the graph in the figure by reversing all the arcs between $\{a_1,a_2\}$ and $\{v_1,v_2,v_3\}$ and/or reversing one of the directed paths linking two $v_i$s. We will show that the forbidden graphs are not $P_{11}$-colorable (Corollary 16 below); since they have maximum average degree 28 / 9, this gives the sharpness in Theorem 1. If we exclude the forbidden graphs, we get the following stronger result.

Theorem 2

Every oriented graph G with $\mathrm{mad}(G)<22/7$ is $P_{11}$-colorable if and only if it contains no forbidden subgraph.

The key lemma used in the proof is the following.

Lemma 3

Every cycle of vertices of degree at most 3 is $P_{11}$-reducible.

This lemma also has an immediate application. For this purpose we first state it in a slightly more explicit version, in which the cycle is assumed to be induced.

Lemma 4

If G is an oriented graph, C is an induced cycle of vertices of degree at most 3 in G and there is a $P_{11}$-coloring of $G-C$, then this can be extended to a $P_{11}$-coloring of G.

Every graph which contains a cycle of vertices of degree at most 3 must contain an induced such cycle (choose one of minimum length), so that Lemma 4 immediately gives Lemma 3.

We now apply Lemma 4 to grid coloring. Fertin et al. [2] have shown that every grid is $P_{11}$-colorable. Since every cylindrical grid (the Cartesian product of a path and a cycle) contains an induced cycle C of vertices of degree at most 3, for which $G-C$ is either a cylindrical grid or empty, induction using Lemma 4 gives the following generalization.

Theorem 5

Every cylindrical grid is $P_{11}$-colorable.

We conclude the section with some more notation. Given two vertices v, w in an oriented graph, we set [v, w] to be 1, $-1$ or 0 according as there is an arc from v to w, from w to v, or neither. If G is an oriented graph, and $V_0 \subseteq V(G)$, $G[V_0]$ will represent the induced oriented graph with vertex set $V_0$. We then set $G-V_0=G[V(G) {\setminus } V_0]$. The degree of a vertex v in G is denoted by $d_G(v)$, with the subscript omitted if the graph G is clear from context. A k-vertex (resp. $^{\le }k$-vertex, x$^{\ge }k$-vertex) is a vertex of degree k (resp. $\le k$, $\ge k$). A k-neighbor (resp. $^{\le }k$-neighbor, $^{\ge }k$-neighbor) of a vertex v is a neighbor of v which is a k-vertex (resp. $^{\le }k$-vertex, $^{\ge }k$-vertex). If $v \in V(G)$ then $N^1(v)$ and $N^{-1}(v)$ will represent respectively the sets of out-neighbors and in-neighbors of v, also written as out(v) and in(v) respectively. We refer to these sets collectively as oriented neighborhoods of v. If $S \subset V(G)$ and $a=\pm 1$, then $N^a(S):=\cup _{v \in S} N^a(v)$.

2 The Target Graph: $P_{11}$

If q is prime, $q \equiv 3$ mod 4, then the Paley Tournament $P_q$ is defined to be the tournament with $V(P_q)=\mathbb {Z}_q$ and

$$\begin{aligned} A(P_q)=\{(a,b)\;| \; b-a \text{ is } \text{ a } \text{ non-zero } \text{ quadratic } \text{ residue } \text{ mod } q\} \end{aligned}$$

(the condition $q \equiv 3$ mod 4 guarantees that exactly one of a and $-a$ is a quadratic residue for $a \not \equiv 0$ mod q, so $P_q$ is indeed a tournament). The automorphism group, $\mathrm{Aut}(P_q)$ of $P_q$ comprises the maps $n \rightarrow an+b$, where $a, b \in \mathbb {Z}_q$ and a is a non-zero quadratic residue; in particular, $P_q$ is arc-transitive.

We derive some preliminary results about $P_{11}$. All the computations we do are feasible by hand, but in order to reduce tedious analyses of cases, we have always used a computer for routine calculations whenever this saves work, with minimum explanation of details.

The automorphism group of $P_{11}$ induces a natural action on the (unordered) k-subsets of $V(P_{11})$, namely

$$\begin{aligned} \phi (\{v_1,v_2, \ldots v_k\})= \{\phi (v_1),\phi (v_2), \ldots \phi (v_k)\} \end{aligned}$$

(1)

As nearly every property of vertex sets which we consider is invariant under this action, it will be useful, for small k, to count the orbits, and to find a representative for each one. We know that the action is transitive for $k \le 2$. For $k=3,4$ we have

Lemma 6

Modulo automorphism there are three 3-element subsets and six 4-element subsets of $\mathbb {Z}_{11}$. The classes of 3-sets have representatives

$$\begin{aligned} \{0,1,2\},\quad \{0,1,4\},\quad \{0,1,5\}. \end{aligned}$$

(2)

The first of these induces a circuit, and the other two induce transitive triangles. The classes of 4-sets have representatives

$$\begin{aligned} \{0,1,2,3\},\quad \{0,1,2,4\},\quad \{0,1,2,5\},\quad \{0,1,2,6\},\quad \{0,1,2,8\},\quad \{0,1,3,4\}. \end{aligned}$$

(3)

Lemma 7

Each set of at least 8 vertices in $V(P_{11})$ contains an oriented neighborhood.

Proof

It suffices to show this for the complements of the sets listed in (2), and these sets all include out(5). $\square$

Lemma 8

If S is a set of vertices in $V(P_{11})$, and $a=\pm 1$, then

Sketch of Proof

Transitivity and arc-transitivity of $P_{11}$ reduce the cases $|S|=1$ and $|S|=2$ to $S=\{0\}$ and $S=\{0,1\}$ respectively. Lemma 6 can be used for the cases $|S|=3$ and $|S|=4$ (note that in the latter case we need only check the set $S=\{0,1,3,4\}$, since $\{ 0,1,2 \}$ induces a circuit). $\square$

The following, which is also easily verified using Lemma 6, slightly generalizes the case $|S|=4$ above.

Lemma 9

If $S \subseteq \mathbb {Z}_{11}$, $|S|=4$ and $a=\pm 1$ , then $|N^a(A)| \ge 10$ for at least two of the 3-element subsets A of S.

The (arc-)transitivity of $P_{11}$ makes the next two results easy to verify using Table 1. We may assume $v=0$ in Lemma 10 and $(v,w)=(0,1)$ in Lemma 12.

Lemma 10

If $a =\pm 1$, $v \in \mathbb {Z}_{11}$ and S is a 4-element subset of $N^a(v)$, then $N^a(S)=\mathbb {Z}_{11}{\setminus }\{v\}$, and $N^{-a}(S)=\mathbb {Z}_{11}$.

Corollary 11

If $a =\pm 1$ and $v \in \mathbb {Z}_{11}$, then $N^a(N^a(v))=\mathbb {Z}_{11}{\setminus } \{v\}$, and $N^{-a}(N^a(v))=\mathbb {Z}_{11}$.

Lemma 12

If $v,w \in V(P_{11})$, and $w \in out(v)$ then, $|out(v) \cap out(w)|=|in(v) \cap in(w)|=|out(v) \cap in(w)|=2$, and $|in(v) \cap out(w)|=3$.

Corollary 13

The intersection of two oriented neighborhoods in $P_{11}$ is either empty, or contains at least two members.

Table 1 Oriented neighborhoods in $P_{11}$

Lemma 12 shows in particular that oriented neighborhoods of different vertices always have a non-empty intersection. We extend this observation slightly.

Lemma 14

If $v \in V(P_{11})$, $S \subseteq V(P_{11})$, $|S| =1, 2$, $a,b=\pm 1$, and either $a=b$ or $v \notin S$ then, $|N^a(S) \cap N^b(v)| \ge |S|+1$.

Proof

Lemma 12 deals with $|S|=1$; $|S|=2$ is an easy calculation (we may assume that $S=\{0,1\}$). $\square$

Lemma 15

If $u,v,v' \in V(P_{11})$ and $a=\pm 1$, then $N^a(u) \cap N^a(v)=N^a(u) \cap N^a(v')$ only if $v=v'$.

Proof

Another straightforward computation. We may assume $u=0$. $\square$

Corollary 16

The forbidden graphs are not $P_{11}$-colorable.

Proof

With reference to Fig. 1, $a_1$ and $a_2$ must take different colors, since they are joined by a directed 2-path. Moreover the same set of colors is available at each of $v_1$, $v_2$ and $v_3$, and by Lemma 12, this set has two elements. But since any two of the vertices $v_1$, $v_2$ and $v_3$ are joined by a directed 2-path, they must take distinct colors, which is impossible. $\square$

Lemma 17

Let $x,y \in V(P_{11})$, $a,b,c \in \{-1,1\}$, then either

• 1.
  $$\begin{aligned} N^b(t)\cap N^c(y)\hbox { induces a circuit} \end{aligned}$$

  (4)

  for are at least two values of $t \in N^a(x)$ or

• 2.
  $$\begin{aligned} |N^b(S)\cap N^c(y)| \ge |S|+1 \end{aligned}$$

  (5)

  for all $S \subseteq N^a(x)$ with $|S|=1,2$, and with at most two exceptions for $|S|=3$.

Proof

We first show that it suffices to prove the lemma for the case $a=1$. From the definition of Paley graphs (in particular from the fact that $-1$ is not a quadratic residue modulo 11), we have $N^a(-S)=-N^{-a}(S)$ (where $-S=\{-v\;|\;v \in S\}$). Thus, if $S \subseteq N^{-a}(x)$, then $-S \subseteq N^a(-x)$, and

$$\begin{aligned} N^{b}(S) \cap N^c(y)=-[N^{-b}(-S) \cap N^{-c}(-y)]. \end{aligned}$$

Since the cardinality of a set S, and the property of inducing a circuit are both preserved in passing from S to $-S$, the lemma holds for both values of a if it holds for either one. We may thus assume that $a=1$.

By arc transitivity we may further assume that $x=0$. and that $y \in \{0,1,2\}$ (since this set contains x and one representative from each of $N^+(x)$ and $N^-(x)$).

By Lemma 14, (6) holds for $|S| =1, 2$ if either $y \notin N^a(x)$ (that is $y \ne 1$ with our normalization) or $b=c$. When $|S|=3$, Lemma 8 shows that (6) holds if either $b=-a$ (in which case $S \subseteq N^{-b}(x)$) or $x \notin N^c(y)$ (in which case, either $b=-a$ or x is absent from both $N^b(S)$ and $N^c(y)$).

In view of our normalizing assumptions, $x=0$, $a=1$, $y \in \{0,1,2\}$, these conditions ensure that (6) holds for $1 \le |S| \le 3$ except in the following cases: $(b,c,y)=(-1,1,1), (1,-1,1)$ or (1, 1, 2). In the first case (5) holds by direct calculation, since $in(3) \cap out(1)=\{2,5,10\}$ and $in(9) \cap out(1)=\{4,5,6\}$ both induce circuits. In the second case the same is true of $out(4) \cap in(1)=\{7,8,9\}$ and $out(5) \cap in(1)=\{3,8,9\}$. In the last case again $y \notin N^a(x)$, so (6) holds for $|S| =1, 2$. Direct calculation shows that it also holds for $|S|=3$ except when $S=\{1,3,4\}$ or $S=\{3,5,9\}$. $\square$

3 Colorings

Let G and H be oriented graphs, and let L be a function which assigns to each $v \in V(G)$ a subset of V(H). We say that G is L-choosable if there is a homomorphism $\phi : G \rightarrow H$ such that $\phi (v) \in L(v)$ for all $v \in V(G)$. We refer to such a homomorphism as a list coloring for the list assignment L, or more briefly as an L-coloring. The target graph H is not referred to explicitly in our notation; in this paper it is always $P_{11}$.

Lemma 18

A cycle C is L-choosable, if each L(v) is an oriented neighborhood of a vertex in $\mathbb {Z}_{11}$.

Remark

In the above, the hypothesis on L(v) cannot be relaxed to $|L(v)| \ge 5$. For example, if C is a transitive triangle $v_1 v_2 v_3$, with source $v_1$ and sink $v_3$, and with list assignment $L(v_1)=\{1,3,4,5,6\}$, $L(v_2)=\{0,1,3,5,6\}$, $L(v_3)=\{0,1,2,3,5\}$, one can readily verify that C is not L-choosable. Lemma 18 immediately gives

Proof of Lemma 4

Suppose that G contains an induced cycle C of $^{\le }3$-vertices. Color $G-C$ and apply Lemma 18.

Proof of Lemma 18

We first suppose that $|C| \ge 4$. Let $C=v_1, v_2, \ldots v_n$ and $L(v_i)=N^{a_i}(x_i)$. For $1 \le i \le n$, we define $P_i$ to be the path $v_1 v_2, \ldots v_i$, and for $k \in L(v_1)$, let

$$\begin{aligned} c_i(k)=\{\phi (v_i)\;|\;\phi \; \text{ is } \text{ an } L\text{-coloring } \text{ of } P_i \text{ such } \text{ that } \phi (v_1)=k\}, \end{aligned}$$

(6)

then $c_1(k)=\{k\}$, and

$$\begin{aligned} c_{i+1}(k)=N^{e_{i}}(c_i(k)) \cap N^{a_{i+1}}(x_{i+1})\; \mathrm{where}\;\; e_i=[v_i,v_{i+1}]. \end{aligned}$$

(7)

We say that i is good if $|c_i(k)| \ge 4$ for at least 2 values of k.

We will show that every $i \ge 4$ is good. If the first case of Lemma 17 holds for some i, with $x=x_i$, $y=x_{i+1}$, $a=a_i$, $b=e_i$ and $c=a_{i+1}$, then by reindexing we may suppose that $i=1$. It follows that $c_2(k)$ induces a circuit for at least 2 values of $k \in L(v_1)$. Then by induction using (8) and Lemma 8, all $i \ge 3$ are good.

Otherwise for all i, the second case of Lemma 17 holds with $x=x_i$, $y=x_{i+1}$, $a=a_i$, $b=e_i$ and $c=a_{i+1}$, and we can apply (6) repeatedly to get in turn that $|c_2(k)| \ge 2$ and $|c_3(k)| \ge 3$ for all $k \in L(v_1)$, and that $|c_4(k)| \ge 4$ for at least three of these values. In particular $i=4$ is good, and as before this remains true for all $i \ge 4$.

Since n is good, there are $k_1, k_2 \in L(v_1)$ such that $|c_n(k_1)|, |c_n(k_2)| \ge 4$. By Lemma 10 it follows that $N^{e_n}(c_n(k_1))=N^{e_n}(c_n(k_2))$ contains either $k_1$ or $k_2$, hence there is an L-coloring of C, which takes this color at $v_1$. Only the case $k=3$ remains, and the argument above can be adapted to cover this. Here there are only finitely many cases to consider, and we can prove the following slightly stronger result using a computer. $\square$

Lemma 19

The following are L-choosable:

• 1. A triangle $v_1 v_2 v_3$, where $|L(v_1)| \ge 4$, and each other L(v) is an oriented neighborhood of a vertex in $Z_{11}$.

• 2. A 4-cycle $v_1 v_2 v_3 v_4$, where $L(v_1) =\mathbb {Z}_{11}$, $|L(v)| \ge 4$ for each other $v_i$, and $L(v_2) \ne L(v_4)$.

Clearly the condition $L(v_2) \ne L(v_4)$ is redundant if either of these sets contains more than four vertices, a fact we use in the following application.

Corollary 20

If G comprises a 6-cycle $u_0 u_1 u_2 u_3 u_4 u_5$, together with an edge between $u_0$ and $u_3$, and $L(u_i)$ are subsets of $V(\mathbb {Z}_{11})$ such that $|L(u_0)| \ge 5$, $L(u_1),L(u_5)=\mathbb {Z}_{11}$, $|L(u_2)|,|L(u_4)|\ge 4$ and $|L(u_3)|\ge 10$, then any orientation of G is L-colorable.

Proof

Let $c \in L(u_2)$. By Corollary 11, there is an L-coloring of the oriented G for which $u_2$ takes the color c, if there is an $L'$-coloring of the cycle $G[u_0,u_3, u_4,u_5]$, where $L'(u_3)=L(u_3) \cap N^{[u_2,u_3]}(c)$, $L'(u_0)=L(u_0) {\setminus } \{c\}$, and $L'(u_i)=L(u_i)$ for $i=4,5$. By Lemma 19 (2), such a coloring exists if $L'(u_0) \ne L'(u_4)$ or if $|L'(u_0)| \ge 5$. At least one of these conditions is met if we can choose $c \notin L(u_0)$ or $c \in L(u_4)$. We are thus done unless $L(u_2) \cap L(u_4) = \emptyset$, $L(u_2) \subseteq L(u_0)$ and (interchanging the roles of $u_2$ and $u_4$) $L(u_4) \subseteq L(u_0)$, but these three together conditions force $|L(u_0)| \ge 8$, so we are done in this case too. $\square$

Lemma 21

A path $v_1 \ldots v_n$ is L-choosable, if $|L(v_1)|, |L(v_n)| \ge 3$, and if $|L(v)| \ge 5$ for each interior vertex of P.

Proof

A straightforward induction on |P|, using Lemma 8. $\square$

The following result resembles Lemma 18, and the proof is similar but easier.

Lemma 22

A cycle $C=v_1 v_2, \ldots v_n$ is L-choosable, if $|L(v_1)|, |L(v_3)| \ge 4$, $L(v_2)=\mathbb {Z}_{11}$, $|L(v_k)| \ge 5$ for all $k \ge 4$, and if $n \ge 4$, $L(v_n)$ is either an oriented neighborhood or contains at least 6 vertices.

Proof

If $n=3$, then we can L-color $v_1$ and $v_3$ using Lemma 8, and this coloring then extends to C by Lemma 12. Now suppose that $n \ge 4$. As in the proof of Lemma 18, for $1 \le i \le n$, we define $P_i$ to be the path $v_1,v_2, \ldots v_i$, and we define $c_i(k)$ by (7). Thus $c_1(k)=\{k\}$, and

$$\begin{aligned} c_{i+1}(k)=N^{e_{i}}(c_i(k)) \cap L(v_{i+1}) \quad \mathrm{where}\quad e_i=[v_i,v_{i+1}]. \end{aligned}$$

(8)

Thus $c_2(k)=N^{e_{1}}(k)$, whence by Corollary 11, $c_3(k) \supseteq L(v_3) {\setminus } \{k\}$, for each $k \in L(v_1)$. By Lemma 9, $|c_i(k)| \ge 4$ for $i=4$ for at least two values of $k \in L(v_1)$, whence by induction using Lemma 8, this is true when $4 \le i \le n$. If $|L(v_n)| \ge 6$, then there are $k_1$ and $k_2$, such that $|c_n(k_1)|, |c_n(k_2)| \ge 5$. Since therefore $c_n(k_1) \cap c_n(k_2)\ge 4$, Lemma 8 gives that $N^{e_n}(c_n(k_1)) \cap N^{e_n}(c_n(k_2))$ omits at most one vertex, and so contains either $k_1$ or $k_2$. If $L(v_n)$ is an oriented neighborhood, then the same conclusion holds, using Lemma 10 as in the proof of Lemma 18. Again as in the proof of Lemma 18, we conclude that there is an L-coloring of C, which takes the color $k_1$ or $k_2$ at $v_1$. $\square$

4 Reducible Configurations

Definition

A weak vertex is a 4-vertex with two 2-neighbors.

Definition

A bad configuration is a 6-cycle $C=v_1x_1v_2x_2v_3x_3$, where the vertices $v_i$ and $x_i$ are of degree 4 and 2 respectively, together with a 4-vertex y, adjacent to each of the $v_i$, and (not necessarily distinct) vertices $z_1, z_2, z_3$ with $z_i$ adjacent to $v_i$, oriented so that that each of the 2-paths $v_i x_i v_{i+1}$ (counting subscripts modulo 3) is directed, and the arcs between $\{y,z_1,z_2,z_3\}$ and $\{v_1,v_2,v_3\}$ are all in the same direction (Fig. 2). Note that a bad configuration with $z_1=z_2=z_3$ is part of a forbidden subgraph (Fig. 1) if there is a directed 2-path between y and $z_1$.

Fig. 2

Bad configurations

Lemma 23

The following configurations are $P_{11}$-reducible

$$\begin{aligned}&\text{ A } ^{\le }1- \text{ vertex. } \end{aligned}$$

(9)

$$\begin{aligned}&\text{ Two } \text{ adjacent } \text{2-vertices. } \end{aligned}$$

(10)

$$\begin{aligned}&\text{ A } \text{3-vertex } \text{ with } \text{ a } \text{2-neighbor. } \end{aligned}$$

(11)

$$\begin{aligned}&\text{ A } \text{ non-directed } \text{2-path } \text{ with } \text{ interior } \text{ vertex } \text{ of } \text{ degree } \text{2. } \end{aligned}$$

(12)

$$\begin{aligned}&\text{ Two } \text{ vertices } \text{ linked } \text{ by } \text{ two } \text{ or } \text{ more } \text{ paths } \text{ with } \nonumber \\&\text{ interior } \text{ vertices } \text{ of } \text{ degree } \text{2. } \end{aligned}$$

(13)

$$\begin{aligned}&\text{ A } \text{3-vertex } \text{ with } \text{ three } ^{\le }3\hbox {-}\hbox {neighbors.} \end{aligned}$$

(14)

$$\begin{aligned}&\text{ A } \text{ weak } \text{ vertex } \text{ with } \text{ two } \text{3-neighbors. } \end{aligned}$$

(15)

$$\begin{aligned}&\text{ Two } \text{ adjacent } \text{ weak } \text{ vertices. } \end{aligned}$$

(16)

$$\begin{aligned}&\text{ A } \text{ path } \text{ of } \text{3-vertices } \text{ with } \text{ two } \text{ weak } \text{ neighbors. } \end{aligned}$$

(17)

$$\begin{aligned}&\text{ A } \text{ triangle } v_1 v_2 v_3 \hbox { such that } v_1 \hbox { is a 4-vertex with a 2-neighbor,} \nonumber \\&\text{ and } \text{ each } \text{ of } v_2 \hbox { and } v_3 \hbox { is a weak vertex or a 3-vertex.} \end{aligned}$$

(18)

$$\begin{aligned}&\text{ A } \text{4-vertex } \text{ with } \text{ three } \text{ or } \text{ more } \text{2-neighbors. } \end{aligned}$$

(19)

$$\begin{aligned}&\text{ A } \text{4-vertex } v \hbox { with neighbors } w, v_1, v_2 \hbox { and } v_3 \hbox { such that } d(w)=2, \nonumber \\&\text{ each } \text{ of } v_1, v_2 \hbox { and } v_3 \hbox { is a weak vertex or a}~^{\le }3\hbox {-}\hbox {vertex, and} \nonumber \\&\text{ these } \text{ three } \text{ vertices } \text{ are } \text{ not } \text{ the } \text{ vertices } v_1, v_2 \hbox { and } v_3 \hbox { of a bad} \nonumber \\&\text{ configuration } \text{(Fig. } \text{2). } \end{aligned}$$

(20)

$$\begin{aligned}&\text{ A } \text{5-vertex } \text{ with } \text{ four } \text{ or } \text{ more } \text{2-neighbors. } \end{aligned}$$

(21)

$$\begin{aligned}&\text{ A } \text{5-vertex } \text{ with } \text{ three } \text{2-neighbors } \text{ and } \text{ two } \text{ weak } \text{ or } \text{3-neighbors. } \end{aligned}$$

(22)

$$\begin{aligned}&\text{ A } \text{6-vertex } \text{ with } \text{ six } \text{2-neighbors. } \end{aligned}$$

(23)

$$\begin{aligned}&\text{ A } \text{6-vertex } \text{ with } \text{ five } \text{2-neighbors } \text{ and } \text{ a } \text{ weak } \text{ or } \text{3-neighbor. } \end{aligned}$$

(24)

$$\begin{aligned}&\text{ A } \text{7-vertex } \text{ with } \text{ seven } \text{2-neighbors. } \end{aligned}$$

(25)

Sketch Proof

The proofs of reducibility follow a similar pattern for all cases. We suppose that G contains one of the listed configurations, and that every proper subgraph of G is $P_{11}$-colorable. We delete the vertices in the configuration (and possibly some others), $P_{11}$-color the remaining graph, and then extend this coloring back to G, using the list-coloring results of the previous section. We do a few cases in detail and sketch the rest.

(10) Trivial

(11) Similar to (and easier than) proof of (12) below

(12) Let u be a 3-vertex in G, with 2-neighbor v. Let w be the other neighbor of v. By assumption there is a $P_{11}$-coloring of $G-\{v\}$. In this graph $d(u)=2$, so by Corollary 13, we can change the color of u if necessary, so that it differs from the color of w. We can now extend this coloring back to G, using Lemma 12.

(13) Delete the interior vertex. Color inductively. Extend using Lemma 14

(14) Let u and v be joined by two or more paths whose interior vertices are of degree 2. If any of these paths has length 3 or more or is a non-directed 2-path, then we have reducibility by (11) and (13) respectively, so we assume all the paths are directed 2-paths or arcs. Since at most one path is an arc, there must be a path of length 2. Delete its middle vertex. Color inductively. Since u and v are still joined by an arc or a directed 2-path, they take different colors. Extend using Lemma 12.

(15) Let v be a 3-vertex with three $^{\le }3$-neighbors $w_1$, $w_2$ and $w_3$. We may assume these each of these vertices has degree 3, and that no two of them are adjacent, otherwise (10), (12) or Lemma 3 applies. Delete v, and inductively color $G-\{v\}$. Since $w_i$ has degree 2 in $G-\{v\}$, Corollary 13 shows that we can choose independently one of at least two colors for each of these vertices. Lemma 8 then shows that for each i there at least 8 colors at v which are compatible with one or other of the possible colors at $w_i$. In other words (as we will phrase it from now on), each $w_i$ deletes up to three colors at v; this leaves at least two colors available at v to extend the coloring of $G-\{v\}$ back to G.

(16) Let v be a weak vertex with two 3-neighbors $w_1$ and $w_2$, and hence two 2-neighbors $x_1$ and $x_2$. We may assume that neither $w_1$ nor $w_2$ is adjacent to $x_1$ or $x_2$, since (12) covers these cases. If $w_1$ and $w_2$ are not adjacent to each other, then delete v and color $G-\{ v\}$ inductively. By Corollary 13 there are at least two colors available at each $w_i$, and at least five at each $x_i$ (since each $x_i$ has degree 1 in $G-\{ v\}$). By Lemma 8, these together eliminate at most $3 + 3 + 1 + 1 = 8$ of the 11 colors available at v.

If $w_1$ and $w_2$ are adjacent, then inductively color $G-\{ v, w_1, w_2\}$. There are 5 color choices available at each $x_i$, and hence, using Lemma 8, at least 10 at v. The set of colors available at each $w_i$ is an oriented neighborhood in $\mathbb {Z}_{11}$. The coloring can thus be extended back to G using Lemmas 7 and 18.

(17) If the weak vertices u and v have a common 2-neighbor, then (14) applies, so we assume that u and v have distinct 2-neighbors. Let the neighbors of u be v, $u_1$, $u_2$ and $u_3$, where $d(u_1)=d(u_2)=2$. Inductively color $G-\{u, v\}$. There are 5 choices of color available at each of $u_1$ and $u_2$. Thus, by Lemma 8, $u_1$ and $u_2$ each delete at most one color at u, while $u_3$ deletes 6. Thus we are left with at least 3 possible colors at u, and symmetrically at v also. (It is possible that $u_3$ is also a neighbor of v; the argument still works in this case.) We can now extend the coloring back to G using Lemma 21.

(18) Let P be a path of 3-vertices with weak neighbors $v_1$ and $v_2$. In view of (17), (16) and (14), we may assume that $v_1$ and $v_2$ are not adjacent to each other, that neither is adjacent to more than one vertex of P, and that they have at most one common 2-neighbor. By shortening the path P if necessary, we may also assume that the neighbors of $v_1$ and $v_2$ in P are the two (not necessarily distinct) end vertices of P.

Suppose first that $v_1$ and $v_2$ have a common 2-neighbor x. We inductively color $G {\setminus } (V(P) \cup \{v_1,v_2,x\})$. If the neighbors of $v_1$ in $G {\setminus } (V(P) \cup \{x\})$ are y and z, with the latter a 2-vertex, then these vertices delete at most 6 colors and one color respectively from $v_1$. This leaves at least 4 colors at $v_1$, and symmetrically 4 colors at $v_2$. All 11 colors are available for x. Each vertex in P has a unique neighbor not in $V(P) \cup \{v_1,v_2\}$, so the set of colors available is an oriented neighborhood in $Z_{11}$ The coloring can thus be extended back to G using Lemma 22.

If $v_1$ and $v_2$ have no common 2-neighbor, then we inductively color $G {\setminus } (V(P) \cup \{v_1,v_2\})$. We have at least three colors available at each of $v_1$ and $v_2$, and 5 at each vertex of P. We then extend the coloring back to G using Lemma 21.

(19) Let $T=v_1 v_2 v_3$, $v_1$ is a 4-vertex with a 2-neighbor, and $v_2$ and $v_3$ are weak or 3-vertices. If any two vertices of T have a common 2-neighbor, apply (14). Otherwise delete V(T) and color inductively. This leaves at least 4 colors available at $v_1$ and the vertices of an oriented neighborhood at each of $v_2$ and $v_3$ (if $v_i$ is weak, then we have available a set of at least 9 colors, which by Lemma 7 contains an oriented neighborhood.) Extend the coloring using Lemma 19 (1).

(20) Delete the 4-vertex. Inductively color. Extend.

(21) By (10), (16), (17) and (20), we may assume that w is the only $^{\le }2$-neighbor of v. We may assume that none of the vertices $v_1$, $v_2$ and $v_3$ is adjacent to w, and that no two of them are adjacent to each other or have more than one common 2-neighbor, as these cases are covered by (14), (19) and (14) respectively.

Any two of the vertices $v_1$, $v_2$ and $v_3$ may have one common 2-neighbor, and we subdivide the proof according to how many of them there are.

Case 1: No common 2-neighbors Inductively color the graph obtained from G by deleting v and its neighbors. At least two colors are available at each $v_i$ (at least two if $v_i$ is a 3-vertex, at least 11-1-1-$6=3$ if $v_i$ is weak); thus these vertices in turn each delete at most three colors from v; w deletes at most one more. Thus at least one color remains for v.

Case 2: One common 2-neighbor Suppose that $v_1$ and $v_2$ have a common 2-neighbor x. Using (12), we may assume that $v_1$ and $v_2$ are both weak. After inductive coloring of $G-\{v,w,v_1,v_2,v_3,x \}$, there are at least 2 colors available at $v_3$ and at least 6 at w, so these vertices in turn together delete at most 4 colors from v. There are thus at least 7 colors available at v. There at least 4 colors available at $v_1$ and $v_2$, and 11 at x. The coloring of G can then be completed by Lemma 22.

Case 3: Two common 2-neighbors We may assume that $v_1$ and $v_2$ have a common 2-neighbor $x_1$, and that $v_2$ and $v_3$ have a common 2-neighbor $x_2$. Using (12), we may assume that $v_1$, $v_2$ and $v_3$ are all weak. Inductively color $G-\{v, w, v_1,v_2,v_3,x_1,x_2 \}$. As usual w deletes at most one color from v, so we have 10 colors available at v, at least 5 at $v_2$, at least 4 at each of $v_1$ and $v_3$, and all 11 at each of $x_1$ and $x_2$. The coloring of G can then be completed using Corollary 20.

Case 3: Three common 2-neighbors Again, using (12), we may assume that $v_1$, $v_2$ and $v_3$ are all weak. These vertices now alternate with 2-vertices in a 6-cycle $C=v_1x_1v_2x_2v_3x_3$. Let $z_i$ be the neighbor of $v_i$ not in $V(C) \cup \{v\}$. We may assume that each of the 2-paths in C from $v_i$ to $v_j$ is directed, otherwise we have reducibility by (13). Since $d(v)=4$, and by the assumption that v and C do not form a bad configuration, there is some $z_i$ such that the path $v v_i z_i$ is directed. Suppose that $v v_1 z_1$ is directed. Now inductively we have a coloring c of $G-V(C)$. There are at least 10 choices of color at v, so we recolor v if necessary, so that $[c(z_1), c(v)]=[v_1,z_1]$ (which eliminates 6 choices of color) and $c(v) \notin \{c(z_2), c(z_3)\}$ (which eliminates 2 more). We now extend c, first to the vertices $v_i$, then to the $x_i$. By Lemma 12, at least three colors are available at $v_1$, and at least two at each of $v_2$ and $v_3$. We can thus give $v_1$, $v_2$ and $v_3$ distinct colors. By Lemma 14, we can now color $x_1$, $x_2$ and $x_3$.

The remaining configurations are straightforward. We gives details only for (23); the others are similar and easier.

(23) Let v be 5-vertex with three 2-neighbors and two weak or 3-neighbors, $v_1$ and $v_2$. Using (14), we may assume that $v_1$ and $v_2$ are adjacent to none of the 2-neighbors of v, and have at most one common 2-neighbor. If $v_1$ and $v_2$ are neither adjacent nor have a common 2-neighbor, then the argument is similar to case 1 of the proof of (21). If $v_1$ and $v_2$ have a common 2-neighbor x, then by (14) they are not adjacent. Now we inductively color $G-\{v,v_1,v_2, x\}$, and apply Lemma 22. Finally suppose that $v_1$ and $v_2$ are adjacent. By (17), we may assume they are 3-vertices. Now inductively color $G-\{v,v_1,v_2\}$. There are at least 8 colors available at v, and the sets of colors available at $v_1$ and $v_2$ are oriented neighborhoods. Now apply Lemma 19 (1). $\square$

5 Bad Configurations

To deal with bad configurations we use a slightly weaker notion of reducibility. Instead of considering graphs with a given property minimal under the subgraph relation, we use minimal order such graphs.

Lemma 24

If H is a subgraph of a forbidden graph with $|H| \ge 3$, then $||H|| \le 2|H|-4$.

Proof

By Turan’s theorem, triangle-free graphs of order 3,4,5, and 6, have at most 2,4,6 and 9 edges respectively, the upper bound in the last case being uniquely attained by the complete bipartite graph $K_{3,3}$. Since forbidden graphs are triangle-free, and clearly have no $K_{3,3}$ subgraph, this gives the lemma for $|H| \le 6$. The remaining cases are easy. $\square$

Lemma 25

Let $\rho \le 16/5$. If $\mathrm{mad}(G)<\rho$, G is non-$P_{11}$-colorable, and contains no forbidden subgraph, and G is minimal order with these three properties, then G contains no bad configuration.

Proof

If $\rho \le 2$, then $\mathrm{mad}(G)<\rho$ implies that G is a forest, which is trivially $P_{11}$-colorable, so that the lemma holds vacuously in this case. We thus assume that $\rho > 2$.

Suppose for a contradiction that G is a minimal order non-$P_{11}$-colorable oriented graph G with $\mathrm{mad}(G)<\rho$ and no forbidden subgraph, but that G contains a bad configuration. We name the vertices of the bad configuration as in the definition at the start of Sect. 4 (and Fig. 2): that is $C=v_1x_1v_2x_2v_3x_3$ is a cycle, where the vertices $v_i$ and $x_i$ are of degree 4 and 2 respectively, and y is a 4-vertex adjacent to $v_1$, $v_2$ and $v_3$. Let e denote the fourth neighbor of y. Recall that $z_1$, $z_2$, and $z_3$ are (not necessarily distinct) vertices adjacent to $v_1$, $v_2$ and $v_3$ respectively. Let $W=V(C)\cup \{y\}$.

Case 1 $z_1=z_2=z_3$ Let z denote the common vertex $z_i$; y is not joined to z by either an arc (in which case $G[W \cup \{z\}]$ would be a subgraph of G with average degree $13/4>16/5 \ge \rho$) or a directed 2-path (in which case G would contain a forbidden subgraph). Thus $e \ne z$, and if e is adjacent to z, then we have $[z,e]=[y,e]$. Let $G'$ be defined to be $G-W$, with an arc added between z and e, oriented so that $[z,e]=[y,e]$, if no such arc is already present in G. We will show that $G'$ contains no forbidden subgraph, and that $\mathrm{mad}(G')<\rho$.

Suppose that M is a subgraph of $G'$, which is either forbidden or has average degree $\ge \rho$. Since G contains no such subgraph, this implies that $G'$ contains a new arc between z and e, and M includes this arc. Now let H be the subgraph of G induced by W and the vertices of M. We have $||H|| \ge ||M||+12$ (H contains all the arcs of M except one, together with 13 new arcs: 9 in W, 3 between the $v_i$ and z and one between y and e), and $|H|=|M|+7$. Thus, since H is a subgraph of G,

$$\begin{aligned} \rho > \mathrm{ad}(H) \ge 2 \left( \frac{||M||+12}{|M|+7} \right) \end{aligned}$$

Since $2(12/7) >16/5 \ge \rho$, this gives a contradiction when $\mathrm{ad}(M)\ge \rho$. If M is forbidden, then $||M||=14$ and $|M|=9$, which again gives a contradiction. We conclude as required that $G'$ contains no forbidden subgraph, and that $\mathrm{mad}(G') < \rho$.

Since $|G'|<|G|$, $G'$ has a $P_{11}$-coloring by the minimality assumption. The restriction of this coloring to $G-W$, then extends readily back to G. Since e is the only vertex in $G'$ adjacent to y, and $[y,e]=[z,e]$, we can first give y the same color as z, so that there are 5 colors available at $v_1$, $v_2$ and $v_3$. We can make any choice of distinct colors at these vertices, and then use Lemma 12 to extend the coloring to G. Thus G is $P_{11}$-colorable, and we have a contradiction.

Case 2: Exactly two of the $z_i$ are the same We may suppose $z_1=z_2 \ne z_3$. Define $G'$ by adjoining to $G-W$ a new directed 2-path between $z_1$ and $z_3$, with the midpoint a new vertex x. Let M be a subgraph of $G'$, which is either forbidden or has average degree $\ge \rho$, and in the latter case suppose that $\mathrm{ad}(M)$ is maximized. In either case M must have minimum degree at least two, in the latter case because if M had an isolated or pendant vertex, we could increase $\mathrm{ad}(M)$ by deleting it (using here the assumption that $\rho > 2$).

As in the previous case, M is not a subgraph of G, so must include the new vertex x, and by the minimum degree condition, both its neighbors $z_1$ and $z_3$ as well. Now let H be the subgraph of G induced by W and the vertices of M. We have $||H|| \ge ||M||+10$ (H contains all but two of the arcs of M, together with 9 arcs from W, 3 between the $v_i$ and the $z_i$ and possibly an arc between y and e), and $|H|=|M|+6$ ($V(H)=W \cup V(M) {\setminus } \{x\}$). Thus

$$\begin{aligned} \rho > \mathrm{ad}(H) \ge 2 \left( \frac{||M||+10}{|M|+6} \right) \end{aligned}$$

If $\mathrm{mad}(M)\ge \rho$ or M is forbidden, this gives a contradiction, as in the previous case.

As in the previous case there is a $P_{11}$-coloring of $G'$, and in this case $z_1$ and $z_3$ take different colors. The restriction of this coloring to $G-W$, then extends readily back to G. Since y has at most one neighbor in $G'$, at least five colors are available for y of which we choose one arbitrarily. Then there is a set of at least two colors available at each of $v_1$, $v_2$ and $v_3$, and by Lemma 15, these are not all the same; so one can choose distinct colors at these vertices. Thus G is $P_{11}$-colorable, and we have a contradiction.

Case 3 $z_1$, $z_2$ and $z_3$ are distinct For $i=1,2,3$, define $G_i$ by adjoining to $G-W$ a new directed 2-path between the vertices of $\{z_1,z_2,z_3 \} {\setminus } \{z_i\}$, with the midpoint a new vertex $x_i$. Suppose that $H_i$ is a subgraph of $G_i$ which contains $x_i$, and both its neighbors. Given such graphs $H_i$ and $H_j$, we define an induced subgraph of G, $H_{ij}$ by

$$\begin{aligned} H_{ij}=G[V(H_i) \cup V(H_j) \cup W {\setminus } \{x_i, x_j\}] \end{aligned}$$

(26)

We have

$$\begin{aligned} ||H_{ij}|| \ge ||H_i \cup H_j||+8 \ge ||H_i||+||H_j||-||H_i \cap H_j||+8 \end{aligned}$$

[$A(H_{ij})$ includes all the arcs of $H_i \cup H_j$ except for the up to 4 arcs incident at $x_i$ and $x_j$. Since $z_1$, $z_2$ and $z_3$ are all vertices of H, A(H) also contains the 3 arcs between $v_i$ and $z_i$, as well as 9 arcs from W, and possibly the arc between y and e.]

$$\begin{aligned} |H_{ij}|=|H_i \cup H_j|+5=|H_i|+|H_j|-|H_i \cap H_j|+5 \end{aligned}$$

Thus

$$\begin{aligned} \mathrm{ad}(H_{ij}) \ge 2 \left( \frac{||H_i||+||H_j||-||H_i \cap H_j||+8}{|H_i|+|H_j|-|H_i \cap H_j|+5}\right) \end{aligned}$$

(27)

Claim: $\mathrm{mad}(G_i) \ge \rho$ for at most one i, and $G_i$ contains a forbidden subgraph for at most one i

To prove the claim suppose that–say–$G_1$ and $G_2$ both contain a forbidden subgraph, or both have maximum average degree $\ge \rho$; then each $G_i$ has a subgraph $H_i$ such that either $H_1$ and $H_2$ are both forbidden or $\mathrm{ad}(H_1)$ and $\mathrm{ad}(H_2)$ are both at least $\rho$. In the latter case we choose $H_i$ to maximize $\mathrm{ad}(H_i)$.

Arguing as in the previous case, each $H_i$ must contain the vertex $x_i$ and both its neighbors. Define $H_{12}$ as in (27). Since $H_1 \cap H_2$ is a subgraph of G, $\mathrm{ad}(H_1 \cap H_2)< \rho$. Now, if $\mathrm{ad}(H_1), \mathrm{ad}(H_2) \ge \rho$, (28) gives $\mathrm{ad}(H_{12}) \ge \rho$, a contradiction, since $H_{12}$ is a subgraph of G.

If $H_1$ and $H_2$ are both forbidden, then since $||H_i||=14$ and $|H_i|=9$, (28) now gives

$$\begin{aligned} \mathrm{mad}(H_{12}) \ge 2 \left( \frac{36-||H_1 \cap H_2||}{23-|H_1 \cap H_2|}\right) \end{aligned}$$

We have $x_1 \in V(H_1) {\setminus } V(H_2)$, $x_2 \in V(H_2) {\setminus } V(H_1)$ and $z_3 \in V(H_1) \cap V(H_2)$. Thus $1 \le |H_1 \cap H_2| \le 7$, and a simple calculation using Lemma 24 then shows that $\mathrm{mad}(H_{12}) \ge 13/4 >16/5 > \rho$, again a contradiction. This proves the claim.

The claim shows that, for some i, $\mathrm{mad}(G_i) < \rho$ and $G_i$ has no forbidden subgraph. Thus again, $G_i$ is $P_{11}$-colorable. This restricts to a coloring of $G-W$ for which two of the $z_i$ take different colors. We extend the coloring to G as in the previous case, and get a contradiction. $\square$

Proof of Theorem 2

Suppose for a contradiction that there is an oriented graph G, with $\mathrm{mad}(G)< 22/7$, which contains no forbidden subgraph, and is not $P_{11}$-colorable, and that G is chosen to be minimum order with these properties.

Clearly G is $P_{11}$-critical (since the property of containing no forbidden subgraph and the maximum average degree bound are both inherited by subgraphs), so that by Lemmas 3 and 23, G contains no cycle of $^{\le }3$-vertices and none of the reducible configurations (10)–(26). By Lemma 25 (with $\rho =22/7$), G also contains no bad configuration.

Define a charge on each vertex v of G by $c(v)=7d(v)-22$, and move the charge according to the following rules

• 1. Each vertex sends a charge of 4 to each of its 2-neighbors.

• 2. Each $^{\ge }3$-vertex sends a charge of 1 to each of its weak neighbors.

• 3. Each non-weak $^{\ge }4$-vertex sends a charge of 1 to each of its 3-neighbors.

Let $c^*(v)$ denote the new charge on vertex v. By (10), there are no $^{\le }1$-vertices in G. By (11), $c^*(v)=0$ when $d(v)=2$. By Lemma 3 and (15) the 3-vertices of G induce a forest whose components are paths. The total initial charge on the vertices of a such a path P of n 3-vertices is $-n$. By (12) and (18), all of the $n+2$ neighbors of the vertices in P are are $^{\ge }4$-vertices, of which at most one is weak. Thus the sum of $c^*(v)$ over the vertices of P is at least $-n+(n+1)-1=0$. Now suppose that $d(v)=4$, then $c(v)=6$, and v has at most two 2-neighbors by (20). In view of (17), if v is weak, then it loses 8 by the first rule, then gains 2 by the second; if v has a single 2-neighbor, then it loses at most 6 by (21) and the fact that G contains no bad configuration; if v has no 2-neighbor, then clearly it loses at most 4. Thus $c^*(v) \ge 0$ for every 4-vertex. Similar calculations, using (22)–(26), show that $c^*(v) \ge 0$ for $5 \le d(v) \le 7$. For $d(v) \ge 8$, $c^*(v) \ge 7d(v)-22-4d(v)=3d(v)-22 \ge 0$. Thus the sum of $c^*(v)$ over all vertices of G is non-negative, which contradicts $\mathrm{mad}(G)< 22/7$. $\square$

6 Concluding Remarks

The bound of 22/7 in Theorem 2 can probably be improved. Some preliminary calculations suggest that a bound of at least 16/5 is possible, using much the same kind of proof, but with a larger set of reducible configurations and more elaborate discharging rules; there are however a huge number of cases to consider. Presumably, further increases still are possible if we exclude more graphs. After 28/9, the smallest value of $\mathrm{mad}(G)$ taken by a $P_{11}$-critical graph appears to be 13/4, attained by the graphs obtained from a forbidden graph by replacing the path $a_1 v a_2$ (in the notation of Fig. 1) by a single arc. Let $\mathcal{S}_\rho$ denote the set of $P_{11}$-critical graphs (modulo isomorphism) with maximum average degree less than $\rho$. Then an oriented G with $\mathrm{mad}(G)<\rho$ is $P_{11}$-colorable if and only if it has no subgraph in $\mathcal{S}_\rho$. We have proved that $\mathcal{S}_\rho$ is the set of forbidden graphs for $28/9< \rho \le 22/7$, and $\mathcal{S}_\rho =\emptyset$ for $\rho \le 28/9$.

Problem 26

What is the smallest value of $\rho$ for which $\mathcal{S}_\rho$ is infinite?

We prove below that this number is at most $65/19=3.42..$. by constructing infinitely many $P_{11}$-critical graphs G with $\mathrm{mad}(G)<65/19$. One way to construct such graphs is by subdivision.

Let G be an unoriented graph, and construct the subdivision $\tilde{G}$ of G, by replacing each edge of G with a path of length 2.

Lemma 27

If G is a graph, then $\mathrm{mad}(\tilde{G})=\frac{4 \mathrm{mad}(G)}{2+\mathrm{mad}(G)}$

Proof

First, if H is any graph, we compute

$$\begin{aligned} \mathrm{ad}({\tilde{H}})=\frac{2||\tilde{H}||}{|\tilde{H}|}=\frac{4||H||}{|H|+||H||}=\frac{4\mathrm{ad}(H)}{2+\mathrm{ad}(H)} \end{aligned}$$

(28)

Clearly we may assume that G is connected. If G is a tree, then so is $\tilde{G}$, and $\mathrm{mad}(G)=\mathrm{ad}(G)$, $\mathrm{mad}(\tilde{G})=\mathrm{ad}(\tilde{G})$, so the lemma holds in this case. Otherwise $\tilde{G}$ contains a cycle. Let M be a subgraph of $\tilde{G}$ with $\mathrm{ad}(M)$ maximal, and subject to this, |M| minimal; $\mathrm{ad}(M) \ge 2$, and M has no isolated or pendant vertices, since the removal of such a vertex would not decrease the average degree. Thus $M=\tilde{H}$ for some subgraph H of G, and the lemma follows from (29). $\square$

Fig. 3

A non-$P_{11}$-colorable planar graph

We can make $\tilde{G}$ into an oriented graph by making each of the paths introduced in the construction of $\tilde{G}$ directed. It is clear that $\tilde{G}$ oriented in this way is $P_{11}$-colorable if and only if $\chi (G) \le 11$. There exists a sequence $H_n$ of 12-critical graphs with $\mathrm{mad}(H_n)<65/19$. To construct $H_n$ take n disjoint copies $G_1, G_2, \ldots G_n$ of $K_{11}$. For each $1 \le i \le n$, let $v_i, w_i \in G_i$ ($1 \le i \le n$), and add an edge between $w_i$ and $v_{i+1}$ ($1 \le i \le n-1$). Finally add a new vertex v joined to all existing vertices except for $v_i$ with $2 \le i \le n$ and $w_i$ with $1 \le i \le n-1$. If we have an 11-coloring of $H_n$, then induction shows that $v, w_1, w_2, \ldots w_{n-1}$ must all take the same color, but then this color is not available to color $G_n$, a contradiction. It is routine to check that every proper subgraph of $H_n$ is 11-colorable. Hence each $H_n$ is 12-critical, and so the $\tilde{H_n}$ are $P_{11}$-critical. We have $|H_n|=11n+1$ and $||H_n||=55n+(n-1)+(9n+2)=65n+1$, whence $\mathrm{mad}(H_n)=\frac{2(65n+1)}{11n+1}$. This is increasing in n and has limiting value 130 / 11, whence $\mathrm{mad}(\tilde{H_n}) \rightarrow 65/19$.

Conjecture 28

Every planar graph of girth at least 5 is $P_{11}$-colorable.

Since $\mathrm{mad}(G)< 10/3$, for every planar graph of girth at least 5 (see e.g. [4]), this result would follow if $\mathcal{S}_{10/3}$ contained no planar graphs. It is even possible that Conjecture 28 might hold with girth 4. On the other hand, it is known [3], that there are planar graphs with oriented chromatic number at least 18, so in particular there exist planar graphs which are not $P_{11}$-colorable. Figure 3 gives a simple example of such a graph (we leave the details as an exercise).