An Oriented 6-Coloring of Planar Graphs with Girth at Least 9

Abstract

We prove that every oriented graph with a maximum average degree less than 18/7 admits a homomorphism into $P_{7}^{*}$, the Paley tournament of order seven with one vertex deleted. In particular, every oriented planar graph of girth at least 9 has a homomorphism into $P_{7}^{*}$, whence every planar graph of girth at least 9 has oriented chromatic number at most 6.

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. All oriented 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 into the complete graph $K_n$.

An oriented graph H is a homomorphism bound for a class $\mathcal{C}$ of oriented graphs—in short a $\mathcal{C}$ -bound—if H admits a homomorphism from every graph in $\mathcal{C}$. Given a class $\mathcal{C}$, the natural first question is whether or not a (finite) $\mathcal{C}$-bound exists. This question is settled in many cases by a theorem of Raspaud and Sopena [13]. Recall first that a proper vertex coloring of a graph is acyclic if every cycle takes at least three colors. The acyclic chromatic number of a graph is then the smallest number of colors required for such a coloring. It is shown in [13] that if the acyclic chromatic number of G is at most k, for every $G \in \mathcal{C}$, then there exists a $\mathcal{C}$-bound of order $k\cdot 2^{k-1}$; this bound is tight for $k \ge 3$ [9].

Given that a $\mathcal{C}$-bound exists, the next obvious question is how small it can be. By analogy with the unoriented case, we define the oriented chromatic number $\chi _o(G)$ of an oriented graph G to be the smallest order of a graph admitting a homomorphism from G, that is a $\{G \}$-bound. We then define the oriented chromatic number $\chi _o(\mathcal{C})$ of a class $\mathcal{C}$ of oriented graphs by $\chi _o(\mathcal{C})=\sup _{G \in \mathcal{C}} \chi _o(G)$ (this of course may be $\infty$). We define the uniform chromatic number $\chi _u(\mathcal{C})$ of $\mathcal{C}$, to be the smallest order of a $\mathcal{C}$-bound (again possibly infinite). Clearly $\chi _o(\mathcal{C}) \le \chi _u(\mathcal{C})$, and this inequality may be strict. A simple example is given by the class $\mathcal{T}$ of oriented triangles. This class has—up to isomorphism—only two members. Clearly $\chi _o(\mathcal{T})=3$, because each triangle has a homomorphism to itself, but $\chi _u(\mathcal{T})=4$, because a graph must have at least four vertices to contain both triangles. However there is one important case in which the two chromatic numbers coincide. If $\mathcal{C}$ is complete—that is any finite disjoint union of graphs in $\mathcal{C}$ is also in $\mathcal{C}$—then $\chi _o(\mathcal{C})=\chi _u(\mathcal{C})$. To see this, suppose that $\mathcal{C}$ is complete and $\chi _o(\mathcal{C})=n$. If $\mathcal{C}$ does not have a homomorphism bound of order n, then, for each oriented graph H of order n, there is a graph $C_H$ in $\mathcal{C}$ which has no homomorphism to H. But the disjoint union over all H of $C_H$ then has chromatic number $>n$, a contradiction. Thus, if $\mathcal{C}$ is a complete class of oriented graphs, then the following statements are equivalent: $\chi _o(\mathcal{C}) \le n$, $\chi _u(\mathcal{C}) \le n$, there is a $\mathcal{C}$-bound of order n, there is an oriented graph H of order n, such that each $G \in \mathcal{C}$ is H-colorable.

One complete class which has received much attention is the class $\mathcal{P}$ of oriented planar graphs. The problem of determining $\chi _o(\mathcal{P})$ can be viewed as an oriented analog of the four color problem. By a theorem of Borodin [1], every planar graph has acyclic chromatic number of most 5, whence, by the aforementioned theorem of Raspaud and Sopena, $\chi _u(\mathcal{P}) \le 80$, and this remains the best upper bound known. In the other direction, it is known that $\chi _u(\mathcal{P}) \ge 18$ [6]. A related problem is to determine the value of $\chi _u(\mathcal{P}_n)$, where $\mathcal{P}_{n}$ is the class of oriented planar graphs with girth at least n, the girth of a graph being the length of its shortest cycle. Here the gaps between the best known upper and lower bounds are smaller, with the exact value being known for $n \ge 12$. The best known bounds are: $11 \le \chi _o(\mathcal{P}_{4}) \le 40$ [8, 11], $7 \le \chi _o(\mathcal{P}_{5}) \le 16$ [5, 12], $7 \le \chi _o(\mathcal{P}_{6}) \le 11$ [4, 5], $6 \le \chi _o(\mathcal{P}_{7}) \le 7$ [2, 7], $5 \le \chi _o(\mathcal{P}_{n}) \le 7$ for $8 \le n \le 10$ [2, 7], $5 \le \chi _o(\mathcal{P}_{11}) \le 6$ [7, 10] and $\chi _o(\mathcal{P}_{n}) = 5$ for $n \ge 12$ [3, 7].

All upper bounds here have been proved by actually exhibiting a homomorphism bound for the class. For example the Paley tournament $P_{11}$ bounds $\mathcal{P}_6$ [4], and $P_{7}^{*}$ bounds $\mathcal{P}_{11}$ [11], where $P_{7}^{*}$ is the Paley tournament $P_7$ with one vertex deleted (it doesn’t matter which; the Paley tournaments are vertex transitive). We discuss these tournaments in the next section.

The average degree, ad(G), of a graph G is defined by $\mathrm{ad}(G)=2||G||/|G|$, where ||G|| and |G| denote respectively the number of edges and of vertices in G. From this we define the maximum average degree, $\mathrm{mad}(G)$, of G as the maximum of ad(H) taken over all subgraphs H of G. It is an easy consequence of Euler’s formula that every planar graph of girth n has maximum average degree less than $2n/(n-2)$ (see e.g. [4]), and most of the $\mathcal{P}_n$-bounds referred to above actually bound the larger class of all oriented graphs with maximum average degree less than $2n/(n-2)$; this is also true in the main result of this paper.

Theorem 1

Every oriented graph G with $\mathrm{mad}(G)<18/7$ is $P_{7}^{*}$-colorable. In particular, $P_{7}^{*}$ bounds $\mathcal{P}_9$.

Conjecture 2

Every oriented graph G with $\mathrm{mad}(G)<8/3$ is $P_{7}^{*}$-colorable. In particular, $P_{7}^{*}$ bounds $\mathcal{P}_8$.

This conjecture, if true, is sharp; we will exhibit an oriented graph G with $\mathrm{mad}(G)=8/3$ which is not $P_{7}^{*}$-colorable.

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, $^{\ge }k$ -vertex) is a vertex of degree k (resp. $\le k$, $\ge k$). The distance between two vertices v and w in a connected graph is the length of a shortest path between them, and is denoted by d(v, w).

An n-path is a path with n edges. A 2-path $v_0 v_1 v_2$ is directed if $[v_0 , v_1]=[v_1 ,v_2]$, undirected otherwise. Let ${\varvec{\epsilon }}=(\epsilon _1,\epsilon _2, \ldots \epsilon _k) \in {\{-1,1\}}^k$. We set $|{\varvec{\epsilon }}|=k$. We define an ${\varvec{\epsilon }}$ -path (trail) from v to w to be a path (trail) $v=v_0 v_1, \ldots v_k=w$ such that, for $i=1 \ldots k$, $[v_{i-1}, v_i]=\epsilon _i$.

Definition

Given a digraph G, $v \in V(G)$ and ${\varvec{\epsilon }} \in {\{-1,1\}}^k$

$$\begin{aligned} N^{\varvec{\epsilon }}(v)=\{ w \in V(G)\;|\; \text{ there } \text{ is } \text{ an } {\varvec{\epsilon }}\text{-trail } \text{ from } \text{ v } \text{ to } \text{ w } \} \end{aligned}$$

If $|{\varvec{\epsilon }}|=k$, we refer to $N^{\varvec{\epsilon }}(v)$ as an oriented k -th neighborhood of v. For $S \subseteq V(G)$ we set $N^{\varvec{\epsilon }}(S)=\cup _{v \in S} N^{\varvec{\epsilon }}(v)$.

2 The Target Graph: $P_{7}^{*}$

Let $q \equiv 3\;\text{ mod }\; 4$ be prime. The Paley Tournament $P_q$ is the tournament with vertex set $\mathbb {Z}_q$ and an arc from v to w if $w-v$ is a non-zero quadratic residue modulo q. (Since $q \equiv 3\;\text{ mod }\; 4$, $-$1 is not a quadratic residue, and so there are no opposite edges.) We then define $P_q^*=P_q - \{0\}$. When $k \in \mathbb {Z}_q^*:=\mathbb {Z}_q \setminus \{0\}=V(P_q^*)$, the map $v \rightarrow kv$ is an isomorphism of $P_q^*$ when k is a quadratic residue, and an anti-isomorphism when it is not. The group of isomorphisms acts transitively on the set of quadratic residues, and the group of isomorphisms and anti-isomorphisms together acts transitively on the whole of $V(P_{7}^{*})$. In particular, the tournament $P_{7}^{*}$ has vertex set $\mathbb {Z}_{7}^{*}=\{1,2,3,4,5,6\}$ and quadratic residue set $\{1,2,4\}$.

Tables 1 and 2 list respectively the oriented neighborhoods and the complements of the oriented second neighborhoods of the vertices of $P_{7}^{*}$. (We omit commas and braces when writing sets).

The next result is readily verified by inspection of these tables.

Lemma 3

In $P_{7}^{*}$

• 1. If $|{\varvec{\epsilon }}|=1$ and $|S|=2,3$, then $|N^{\varvec{\epsilon }}(S)| \ge |S|+2$.

• 2. If $|{\varvec{\epsilon }}|=2$ and $|S|\le 3$, then $|N^{\varvec{\epsilon }}(S)| \ge |S|+3$.

• 3. If $|{\varvec{\epsilon }}|=2$ and $n \in \mathbb {Z}_{7}^{*}$, then $|N^{\varvec{\epsilon }}(n)\cap N^{\varvec{\epsilon }}(-n)| =4$.

• 4. If $|{\varvec{\epsilon }}|\ge 3$ and $v \in \mathbb {Z}_{7}^{*}$, then $N^{\varvec{\epsilon }}(v) =\mathbb {Z}_{7}^{*}$.

Table 1 Oriented neighborhoods in $P_6^*$

Table 2 Complements of oriented second neighborhoods in $P_6^*$

Definition

A subset of $V(P_{7}^{*})=\mathbb {Z}_{7}^{*}$ is mixed if it contains both a quadratic residue and a non-quadratic residue. Note that each of the sets $N^{(1)}(v)$ and $N^{(-1)}(v)$ are mixed for each $v \in \mathbb {Z}_{7}^{*}$. Of course any set of at least 4 vertices is mixed, and indeed must contain a set of the form $\{n,-n\}$, a fact that will be useful later on.

3 List Coloring

Let G be an oriented graph, and suppose that with each vertex v of G we associate a list $L(v) \subseteq V(P_{7}^{*})$. An L-coloring of G is a $P_{7}^{*}$-coloring of G, where the color of each vertex v is contained in L(v). When such a coloring exists we say that G is L -choosable.

Lemma 4

The following graphs are L-choosable:

• 1. An oriented path $v_1 v_2 v_3 v_4$ , where $L(v_2)=L(v_3)=V(P_{7}^{*})$, $L(v_1),L(v_4)\ne \emptyset$.

• 2. An oriented triangle $T=v_1 v_2 v_3$ where $L(v_1)$ is mixed, $|L(v_3)| \ge 4$ and $L(v_2)=\mathbb {Z}_{7}^{*}$.

• 3. An oriented 4-cycle $v_1 \ldots v_4$ , where $L(v_2)=L(v_4)=V(P_{7}^{*})$, $L(v_1), L(v_3)$ are mixed, and we do not have $L(v_1)=L(v_3)=\{n,-n\}$ for any n.

• 4. An oriented 4-cycle $v_1 \ldots v_4$ with an extra arc between two opposite vertices, where $L(v_i)=V(P_{7}^{*})$ for all i.

Proof

(1) From Lemma 3(4).

(2) First suppose that $[v_1,v_3]=1$. By symmetry we may assume that $1 \in L(v_1)$. Let ${\varvec{\epsilon }}$ be the orientation of the path $v_1 v_2 v_3$. We must choose a color k for $v_1$, such that $N^{\varvec{\epsilon }}(k) \cap N^{(1)}(k)$ meets $L(v_3)$. An inspection of Tables 1 and 2 shows that $N^{\varvec{\epsilon }}(1) \cap N^{(1)}(1)=\{2,3,5\}$, except when ${\varvec{\epsilon }}=(-1,1)$, in which case it is $\{3,5\}$. Thus we can color $v_1$ 1, except when ${\varvec{\epsilon }}=(-1,1)$ and $L(v_3)=\{1,2,4,6\}$. In this last case we color $v_1$ by a non-quadratic residue k which is (by hypothesis) in $L(v_1)$. By Table 2, $N^{\varvec{\epsilon }}(k)=\mathbb {Z}_{7}^{*}$, so that $N^{\varvec{\epsilon }}(k) \cap N^{(1)}(k)=N^{(1)}(k)$, and we may color $v_3$ 4, 6 or 1, according as k is 3, 5 or 6. A similar argument applies when $[v_1,v_3]=-1$.

(3) Let the paths $v_1 v_2 v_3$, $v_1 v_4 v_3$ have orientations ${\varvec{\epsilon }}$, ${\varvec{\eta }}$ respectively. We must find a $k \in L(v_1)$ such that the intersection

$$\begin{aligned} I_k:=N^{\varvec{\epsilon }}(k) \cap N^{\varvec{\eta }}(k) \end{aligned}$$

(1)

meets $L(v_3)$. If $[v_1, v_2]=[v_1, v_4]=1$ (resp. $-$1), then we may choose k to be a quadratic (resp. non-quadratic) residue. Table 2 shows that $I_k$ excludes at most one vertex, and since $|L(v_3)| \ge 2$, we are done. We may thus assume $[v_1, v_2] \ne [v_1, v_4]$, and symmetrically that $[v_3, v_2] \ne [v_3, v_4]$. Now ${\varvec{\epsilon }} \ne {\varvec{\eta }}$, and the paths $v_1 v_2 v_3$, $v_1 v_4 v_3$ are either both undirected or both directed. Table 2 shows that in both cases $|I_k| = 4$ for all k. We are thus done unless the sets $I_k$ ($k \in L(v_1)$) are all the same. Since $I_k = I_m$ only if $m=k$, when the paths are undirected, and only if $m=\pm k$, when the paths are directed, this only happens when both paths are directed, and for some k, $L(v_1) = \{k,-k\}$. In this case $I_k=\mathbb {Z}_{7}^{*} \setminus {\{k,-k\}}$, but then $L(v_3) \ne \{k,-k\}$ by assumption, so we are done in this case too.

(4) We may suppose that the extra arc is from $v_1$ to $v_3$. Color $v_1$ 1. Since 3 and 5 lie in every second oriented neighborhood of 1, as well as in $N^{(1)}(1)$, we can use either of these to color $v_3$. $\square$

Remark

Clearly (4) can be improved; for example $L(v_1)$ could be any mixed set. In (3), the condition that $L(v_1)$ and $L(v_3)$ are both mixed can be relaxed to the condition that one of these sets is mixed and the other has at least two members. However the proof becomes messier, and the result stated will be enough for our needs.

Definition

A structured graph is a quadruple $C=(G,W,v_0,L)$, where G is a connected oriented graph, $W \subseteq V(G)$ is an independent set, $v_0 \in V(G) \setminus W$, and L is a list assignment from V(G) to subsets of $V(P_{7}^{*})$, with the following two properties:

$$\begin{aligned}&\forall w \in W, \; d(w)=2 \end{aligned}$$

(2)

$$\begin{aligned}&|L(v)| \ge 2d(v)\;\;(\forall v \ne v_0), \; \text{ and } L(v)=V(P_{7}^{*})\;\;\text{ if } v \in W \end{aligned}$$

(3)

We set $H=H(C)=G-W$. We note that $d(v) \le 3$ for $v \ne v_0$, as no list can contain more than 6 vertices. We refer to the vertices in W as light. A W -path will mean a 2-path whose internal vertex is in W. Two vertices are W -adjacent or are W -neighbors if they are joined by a W-path. For $u \in V(H)$, we define $N_u$ to be the set of neighbors and W-neighbors of u in H, $W_u$ to be the set of light neighbors of u, and $G_u=G-(W_u \cup \{u\})$.

We will show under certain conditions that, when H is a forest, a structured graph G has an L-coloring. The method will be induction—removing a vertex u from a supposed minimal counterexample to create a smaller one. The vertex removed will always be a leaf or an isolated vertex in H. Let u be such a vertex. Deleting the vertex u from G will always be understood to include deleting its light neighbors as well; thus the graph obtained by deleting u from G is $G_u$. We will say that deleting u from G deletes a set $S(v) \subseteq V(P_{7}^{*})$ at each vertex $v \in N_u$ (or from the corresponding list L(v)), to mean the following: if $L_u$ is the list assignment on $V(G_u)$ given by $L_u(v)=L(v) \setminus S(v)$ for $v \in N_u$, and $L_u(v)=L(v)$ for $v \notin N_u$, then every $L_u$-coloring of $G_u$ can be extended to an L-coloring of G.

Let $v \in N_u$. We will show that, deleting u deletes at most two colors at v for each path or W-path between u and v. The most straightforward case is where u is an isolated vertex in H. Here we choose any color $c \in L(u)$, then, for each W-path uwv, we can delete from L(v) the colors not in $N^{\varvec{\epsilon }}(c)$, where ${\varvec{\epsilon }}$ is the orientation of the path uwv. From Table 2 we see that we delete at most two colors per path. Moreover, if c is a quadratic (resp. non-quadratic) residue, and $[v,w]=1$ (resp. -1), then at most one color is deleted via this path. Thus, if L(u) is mixed, we can choose a color $c \in L(u)$ so that any specified W-neighbor v loses only one color at most via a given W-path (hence the sets S(v) referred to above need not be uniquely determined). A slightly different approach is required when $d_H(u)=1$; here we color $G_u$ first, then u, and finally $W_u$. The following lemma summarizes the general result.

Lemma 5

Let $(G,W,v_0,L)$ be a structured graph, and $u \in V(H) \setminus \{v_0\}$ with $d_H(u) \le 1$, then

• 1. Deleting u from G deletes at most two colors at each vertex in $v \in N_u$ for each arc or W-path joining u and v.

• 2. If $d_G(u)=d_H(u)=1$ and $|L(u)| \ge 3$, then deleting u from G deletes at most one color at the vertex in $N_u$.

• 3. If $d_H(u)=0$, and there are k W-paths from u to $v \in N_u$, then we can color u so as to delete at most $2k-1$ colors at v (and at most two colors for each W-path from u to w at every other $w \in N_u$).

Proof

Case 1, ${\mathbf{d}_\mathbf{G}}\mathbf{(u)}= \mathbf{1}$: Let y be the unique vertex in $N_u$, and let ${\varvec{\epsilon }}$ be the orientation of the unique edge or W-path from u to y, then u deletes from L(y) the colors not in $N^{{\varvec{\epsilon }}}(L(u))$. Since $|L(u)| \ge 2$, Lemma 3(1), (2) shows that at most two colors are thus deleted, or at most one if either $|L(u)| \ge 3$ or $|{\varvec{\epsilon }}|=2$.

Case 2, ${\mathbf{d}_\mathbf{G}}\mathbf{(u)} > \mathbf{1}$: Since $d(u) \ge 2$, $|L(u)| \ge 4$, and so there is an $n \in \mathbb {Z}_{7}^{*}$ such that $\{n,-n\} \subseteq L(u)$, and in particular L(u) is mixed. The discussion before the statement of the theorem deals with the case $d_H(u)=0$, so we suppose that $d_H(u)=1$, and let y be the unique neighbor of u in H. If $v \in N_u$, then for each W-path uwv from u to v we delete from L(v) the colors not in $N^{\varvec{\epsilon }}(n) \cap N^{\varvec{\epsilon }}(-n)$, where ${\varvec{\epsilon }}$ is the orientation of uwv. By Lemma 3(3) this removes at most 2 colors for each path. In addition we delete from L(y) the colors not in $N^{([u,y])}(\{n,-n\})$, of which, by Lemma 3(1), there are at most two.

Now any $L_u$-coloring of $G_u$ can be extended to G by coloring u either by n or by $-n$, whichever is compatible with the color of y $\square$

Every time we delete a vertex u using Lemma 5, the number of colors deleted from L(v) is at most twice the reduction in d(v) as we pass from G to $G_u$: thus the inequality $|L(v)| \ge 2d(v)$ is preserved. In particular, if $(G,W,v_0,L)$ is a structured graph and $u \ne v_0$, then $(G_u, W \cap V(G_u), v_0, L_u)$ is also a structured graph, provided that $G_u$ is connected. It is now easy to show that $(G,W,v_0,L)$ is L-choosable when H is a forest and $|L(v_0)|>2d(v_0)$ (Lemma 6(1) below). When $|L(v_0)| \le 2d(v_0)$, we may be able to offset this by having $|L(v)| > 2d(v)$ for some other vertices. Roughly speaking, part (3) of Lemma 5, creates vertices satisfying this inequality, while part (2) preserves them. In the latter case, when v is deleted its property of having a “surplus” color is transferred to its neighbor.

The next two results give sufficient conditions for L-choosability of a structured graph.

Lemma 6

If $(G,W,v_0,L)$ is a structured graph, and H is a forest, then G is L-colorable in both of the following cases.

• 1. $|L(v_0)| > 2d(v_0)$

• 2. $W = \emptyset$, and $|L(v_0)|>2d(v_0)-m$, where m is the number of components of $H-\{v_0\}=G-\{v_0\}$ which contain a vertex v with $|L(v)| > 2d(v)$.

Proof

(1) Suppose that G is a minimal counterexample. Clearly $|G|>1$, but then there is a leaf $v \ne v_0$ of H. Choose v to maximize the distance $d(v,v_0)$, and delete it using Lemma 5(1). The distance condition ensures that $G_v$ is connected (otherwise the component of $G_v$ which does not contain $v_0$ contains a leaf w in H with $d(w,v_0)>d(v,v_0)$). We thus get a smaller counterexample, contradicting the minimality of G.

(2) Suppose that G is a minimal counterexample. Since G is connected, and $W = \emptyset$, $G=H$ is a tree. Clearly $|G|>1$, so that there is a leaf $v \ne v_0$ of H, with neighbor u. If $u \ne v_0$, then the terms in the inequality $|L(v_0)|>2d(v_0)-m$ are unchanged when v is deleted (using Lemma 5(2) when $|L(v)| \ge 3$). If $u = v_0$, then deleting v reduces $2d(v_0)$ by 2. If $|L(v)|=2$, then $|L(v_0)|$ is also reduced by at most 2, and m is unchanged. If $|L(v)| \ge 3$, then m is reduced by 1, and $|L(v_0)|$ by at most 1. Thus in all cases the inequality $|L(v_0)|>2d(v_0)-m$ is preserved, contradicting the minimality of G. $\square$

The next result—our main technical lemma—is essentially a combination of the two parts of Lemma 6, i.e. we allow both $|L(v_0)| \le 2d(v_0)$ and $W \ne \emptyset$. The proof is still by induction using Lemma 5, but the details are more elaborate. We first introduce some more terminology. Let $(G,W,v_0,L)$ be a structured graph, such that H is a forest. Let $\mathcal{W}$ be the set of light neighbors of $v_0$, $\mathcal{H}$ the set of components of H and $H_0 \in \mathcal{H}$ the tree which contains $v_0$.

Let $\mathcal{P} \subseteq \mathcal{H}$ be the set of trees in $\mathcal{H} \setminus \{H_0\}$ for which exactly two vertices, $v_1$ and $v_2$, are W-adjacent to (vertices in) $H_0$. Let $\mathcal{P}_1 \subseteq \mathcal{P}$ be the set of trees in $\mathcal{P}$ for which at least one of the vertices $v_1$, $v_2$ has exactly one W-neighbor in $H_0$, and this W-neighbor is not $v_0$. Let $\mathcal{P}_2=\mathcal{P} \setminus \mathcal{P}_1$; that is $\mathcal{P}_2$ contains the trees of $\mathcal{P}$ for which each of the vertices $v_1$ and $v_2$ is either W-adjacent to $v_0$ or has at least two W-neighbors in $H_0$. Let $\mathcal{T}$ be the set of the components of $H_0-\{v_0\}$. A tree $T \in \mathcal{T}$ is saturated if it has a vertex v with $|L(v)| > 2d(v)$. Let $\mathcal{S}$ denote the set of saturated trees. For a vertex v of $H - V(H_0)$, a W-path from v to $H_0$ is good if it finishes either at $v_0$ or in an unsaturated tree of $\mathcal{T}$. Let p(v) denote the number of good paths starting at v.

Let $\sigma : \mathcal{T} \rightarrow \mathbb {N}$ be defined by $\sigma (T)=5$ if T is saturated, and for $T \notin \mathcal{S}$, $\sigma (T)=4$ if T has at least three light neighbors, or if a vertex of T has two light neighbors; $\sigma (T)=2$ if T does not satisfy these conditions, but has at least one light neighbor, and $\sigma (T)=0$ if T has no light neighbors.

The tree score, $t=t(G)$ is then defined by

$$\begin{aligned} t={\Sigma }_{T \in \mathcal{T}} \sigma (T) \end{aligned}$$

Finally let

$$\begin{aligned} \eta =\eta (G)=\left\{ \begin{array}{lll} 2 &{}\mathrm{if}\; |\mathcal{P}_2| \ge |\mathcal{W}| \\ 0 &{}\mathrm{if}\; L(v_0)=\mathbb {Z}_{7}^{*}, \mathcal{P}_2=\emptyset \hbox { and } |\mathcal{W}|=1. \\ 1 &{} \hbox {in all other cases}. \end{array} \right. \end{aligned}$$

The structured graph in Fig. 1 illustrates these terms. In this example $d(v_0)=4$, $|\mathcal{W}|=1$, $\mathcal{P}_1=\{H_1\}$, $\mathcal{P}_2=\{H_2\}$, $\mathcal{T}=\{T_1,T_2,T_3\}$, $\mathcal{S}=\{T_2\}$, $t=\sigma (T_1)+\sigma (T_2)+\sigma (T_3)=4+5+4=13$, and $\eta =2$.

Fig. 1

A structured graph: vertices in H are black, vertices in W are white. We suppose $|L(w)|\ge 5$, $|L(v)|=6$ if $v=v_0$ or $v \in W$, $|L(v)|=2d(v)$ otherwise

Lemma 7

Let $(G,W,v_0,L)$ be a structured graph, such that H is a forest, and suppose that:

$$\begin{aligned}&\hbox {no } v \in V(H) \hbox { has two } W-\hbox {paths to the same vertex in } V(H_0) \setminus \{v_0\}, \end{aligned}$$

(4)

$$\begin{aligned}&\hbox {each } T \in \mathcal{H} \setminus \{H_0\} \hbox { has at most three } W-\hbox {paths to } H_0, \nonumber \\&\hbox {and these start from at most two different vertices}, \end{aligned}$$

(5)

$$\begin{aligned}&\hbox {no two vertices in } H_0 \hbox { are } W\hbox {-adjacent}, \end{aligned}$$

(6)

$$\begin{aligned}&\hbox {if } |\mathcal{W}| \ge 2, \hbox { then } |L(v_0)|-2d(v_0) \ge -2, \end{aligned}$$

(7)

and

$$\begin{aligned} |L(v_0)|-2d(v_0)+|\mathcal{W}|-|\mathcal{P}_2|+\frac{t+2\eta -2|\mathcal{P}_1|}{5} \ge 1, \end{aligned}$$

(8)

then G is L-choosable.

(It is easy to check that the structured graph in Fig. 1 satisfies all these hypotheses.)

Proof

We suppose for a contradiction that G is a minimum order counterexample to this lemma. We progressively restrict the possibilities for G, finally showing that no such counterexample can exist. We outline the main steps first. We first show that

$$\begin{aligned} \hbox {If } v \hbox { is a leaf or an isolated vertex of } H - V(H_0),\hbox { then } p(v) \ge 2. \end{aligned}$$

(9)

Together with (5), this shows that

$$\begin{aligned} \hbox {Every component of } H \hbox { other than } H_0 \hbox { is an isolated vertex}. \end{aligned}$$

(10)

In particular $\mathcal{P}_1=\mathcal{P}_2=\emptyset$.

Next we consider the case $\mathcal{W}=\emptyset$, and show that this reduces to the case $\mathcal{H}=\{H_0\}$. In this case there are no light vertices at all, and so $\sigma (T)$ is either 0 or 5 according as T is unsaturated or saturated. Hence (8) becomes simply $|L(v_0)|-2d(v_0)+|\mathcal{S}|> 0$. But now G is L-colorable by Lemma 6(2). We complete the proof by showing that the cases $|\mathcal{W}|=1$, $|\mathcal{W}|=2$ and $|\mathcal{W}| \ge 3$ each reduce to the case $\mathcal{W}=\emptyset$.

We obtain a contradiction to the minimality of G if, when we delete some vertex v, we obtain a structured graph satisfying properties (4)–(8). As we have noted previously, Lemma 5 shows that, provided that $G_v$ is connected, we still have a structured graph after deletion, and clearly properties (4)–(6) also remain true. Thus we need only to check that (7) and (8) are also preserved.

We now prove (9). Suppose now that v is a leaf or an isolated vertex of $H - V(H_0)$, and that $p(v) \le 1$. First suppose that $p(v)=0$, and choose v to maximize $d(v,v_0)$, which ensures that $G_v$ is connected (by the proof of Lemma 6(1), with the additional observation that the leaf w found there now also satisfies $p(w)=0$).

We then delete v. All W-paths from v to vertices in $H_0$ end in trees of $\mathcal{T}$ which are already saturated, so t, $L(v_0)$, $d(v_0)$ and $\mathcal{W}$ are all unchanged. In view of (5), $|\mathcal{P}_1|$ and $|\mathcal{P}_2|$ do not increase, and $\eta$ can decrease only when $\mathcal{P}_2$ also decreases. Thus (7) and (8) still hold after v is deleted. We are thus reduced to the case where $p(v) \ge 1$ for each leaf or isolated vertex v of $H - V(H_0)$. Again by (5), it follows that each of the components in $\mathcal{H} \setminus \{H_0\}$ is now either an isolated vertex or a path $P \in \mathcal{P}$. Note that deleting v now always leaves $G_v$ connected.

Suppose now that $p(v)=1$, and let vwx be a good path. Thus either x is in an unsaturated tree or $x=v_0$. If v is an isolated vertex in H, then by using Lemma 5(3) we may delete v, deleting at most one color at x. If x lies in an unsaturated tree, then this tree becomes saturated when we delete v, so we do not reduce (in fact we increase) t, and the other terms of (8) are unchanged. Otherwise $x=v_0$, and we decrease $d(v_0)$ and $|\mathcal{W}|$ by 1 each, and $|L(v_0)|$ by at most 1; $\eta$ is not reduced, except possibly when $|L(v_0)|$ is unchanged. The other terms of (8) are unchanged. Thus (7) and (8) are preserved in either case.

If $d_H(v)=1$, then v is an end-vertex of a path $T \in \mathcal{P}$. If $T \in \mathcal{P}_1$, then (by choosing the other end-vertex if necessary) we can assume v chosen so that $x \ne v_0$. Conversely, in view of (5), if $T \in \mathcal{P}_2$, then we can choose v so that $x=v_0$.

By Lemma 5, deleting v removes at most two colors at x. When $T \in \mathcal{P}_1$, $x \ne v_0$, so this deletion decreases $|\mathcal{P}_1|$ by 1 and t by at most 2, and leaves the other terms of (8) unchanged. When $T \in \mathcal{P}_2$, $x = v_0$, and we decrease each of $d(v_0)$, $|\mathcal{W}|$ and $|\mathcal{P}_2|$ by 1, and $|L(v_0)|$ and $\eta$ by at most 1, while t and $|\mathcal{P}_1|$ are unchanged. Moreover, $\eta$ can decrease only if $|L(v_0)|$ remains the same. Thus (7) and (8) are again preserved in both cases. The minimality of G now implies (9), and so (10).

Inequality (8) now simplifies to

$$\begin{aligned} |L(v_0)|-2d(v_0)+|\mathcal{W}|+\frac{t+2\eta }{5} \ge 1. \end{aligned}$$

(11)

Since every vertex v of $H-V(H_0)$ now satisfies $d_H(v)=0$ and $d_G(v) \ge p(v) \ge 2$, L(v) contains at least four colors, and so in particular, is mixed. We are thus in the situation described just before the statement of Lemma 5, where we can choose a color for v, then delete it. As noted in Lemma 5(3) we can always do this so as to delete at most one color at one of the W-neighbors of v. By a careful choice of color, it is sometimes possible (and necessary) to do more than this (for example to delete only one color from two or more W-neighbors). For this reason we do not just use Lemma 5 in the remainder of the proof, but also refer directly back to information in Table 2.

Subcase 1: $\mathcal{W}=\emptyset$. Deleting a vertex v of $H - V(H_0)$ changes none of the terms in (11), except possibly t, so (11) will be preserved, provided that t is not reduced.

Let v be a vertex of $H-V(H_0)$. If all the good paths from v end in the same (unsaturated) tree T, then we may color v in such a way as to saturate T (that is in such a way that T becomes saturated.) Specifically, for some good path vwx we can use Lemma 5(3) to color v so as to delete at most one color from L(x), whence T becomes saturated. This increases $\sigma (T)$, and hence t.

Next suppose that the good paths from v end in three distinct trees, then, since L(v) is mixed, we may color v in such a way as to saturate at least two of them. (Let the three good paths be $vw_ix_i$ ($1 \le i \le 3$). Table 2 shows that it is enough to color v with a quadratic residue if $[v,w_i]=1$ for at least two values of i, and with a non-quadratic residue otherwise.) Thus deleting v increases $\sigma (T)$ by at least one for each of two of the trees, and reduces it by at most two for the other; again we do not decrease t.

We are thus reduced to the case where, for every vertex v of $H-V(H_0)$, all of the (two or three) good paths from v end in (exactly) two distinct unsaturated trees $T_1$ and $T_2$. If $\sigma (T_1)=\sigma (T_2)=2$, then we may color v in such a way as to saturate at least one of these trees, thus increasing $\sigma (T)$ by at least three for one tree, and reducing it by at most two for the other; thus we increase t. Otherwise we may assume that $t(T_2)=4$. By (4) and (10), the (at most two) W-paths from v to $T_2$ end in distinct vertices. Thus (since $t(T_2)=4$), $T_2$ has a light neighbor which is adjacent to a vertex $w \ne v$ of $H-V(H_0)$. The vertex w is thus W-adjacent to $T_2$, and to one other unsaturated tree $T_3$ (possibly $T_3=T_1$). We now color v to saturate $T_1$, and then w to saturate $T_2$. If $T_3=T_1$ or $\sigma (T_3) \le 2$, then again t is not reduced. If $T_3 \ne T_1$, and $\sigma (T_3)=4$, then, arguing as we did for $T_2$, $T_3$ is adjacent to a light vertex, which is not adjacent to w, and which cannot be adjacent to v either (else v has good paths ending in three different trees). Thus even after deleting v and w, $T_3$ retains at least one light neighbor, whence $\sigma (T_3)$ is reduced by at most two, and t is not reduced. Thus we can always delete v, and so, by minimality of G, we are reduced to the case $H=H_0$, in which case, as noted above, we are done.

Subcase 2: $|\mathcal{W}|=1$. Suppose that $\mathcal{W}=\{x\}$. In view of (6), there is a unique vertex v of $H-V(H_0)$ which has a W-path to $v_0$, and this path is $vxv_0$. Let ${\varvec{\epsilon }}$ be the orientation of this path. Table 2 shows that we can color v in such a way as to delete at most one color from $L(v_0)$ when $vxv_0$ is directed, and none at all when $vxv_0$ is undirected. We have $\eta \le 1$ before v is deleted and $\eta =2$ after, while t decreases by at most 4 ($\sigma (T)$ being reduced by at most two for each of up to two trees). Therefore (11) is preserved when $vxv_0$ is undirected. We suppose therefore that $vxv_0$ is directed, in which case $|L(v_0)|-2d(v_0)+|\mathcal{W}|$ is not decreased, and to preserve (11) it is enough to show the same is true of $t+2\eta$.

If $\eta =0$, then deleting v increases $\eta$ by 2, and decreases t by at most 4. If $\eta =1$ and $p(v)=2$, then $\eta$ increases by 1 and t decreases by at most 2. If $\eta =1$ and $p(v)=3$, then $L(v_0) \ne \mathbb {Z}_{7}^{*}$ and $L(v)=\mathbb {Z}_{7}^{*}$, whence Table 2 shows that $\{x \in L(v):\;|N^{\varvec{\epsilon }}(x) \cap L(v_0)| \ge |L(v_0)|-1\}$ contains at least four colors, and so is mixed (one choice of x in this set deletes a color which is already absent from $L(v_0)$). We may thus color v in order to saturate at least one of the trees which is W-adjacent to v, while still deleting only one color from $L(v_0)$. Thus we reduce t by at most one ($\sigma (T)$ being reduced by at most two for one tree, and increased by at least one for another), and increase $\eta$ by one.

Thus in all cases (11) still holds after deleting v, and we are reduced to the case $\mathcal{W}=\emptyset$.

Subcase 3: $|\mathcal{W}|=2$. First suppose that there are distinct vertices v, w of $H-V(H_0)$, each with a unique W-path to $v_0$. If either of these paths is undirected, then Table 2 shows that we may color v and w so as to delete at most one color altogether from $L(v_0)$. Since we also reduce $d(v_0)$ by two, inequality (7) gives $|L(v_0)|-2d(v_0)>0$ after deleting v and w, whence (11) still holds (all the other terms are non-negative), and we are reduced to the case $\mathcal{W}=\emptyset$.

Now suppose that both the paths are directed. Renaming if necessary, and using the fact that $|L(v)|, |L(w)| \ge 4$, there is an $n \in \mathbb {Z}_{7}^{*}$ such that $n \in L(w)$ and $\{n,-n\} \subseteq L(v)$. We color w by color n and v by color $\pm n$ in such a way as to saturate a tree W-adjacent to v (recall $p(v) \ge 2$). Thus after deleting v and w, we reduce $d(v_0)$ by 2 and $|L(v_0)|$ by at most 2. By (7), we now have $|L(v_0)|-2d(v_0) \ge 0$. We also have $|\mathcal{S}| \ge 1$, whence $t \ge 5$, and so (11) still holds, and we are reduced to the case $\mathcal{W}=\emptyset$.

In the remaining case, there is a vertex v of $H-V(H_0)$ with two W-paths to $v_0$. If one of the W-paths is undirected, then we may color v so that no colors are deleted from $L(v_0)$ via this path, so that deleting v deletes at most two colors from $L(v_0)$ altogether. This is also true if both paths are directed (in which case the color of v can be chosen arbitrarily from L(v)). Thus deleting v reduces $|\mathcal{W}|$ and $d(v_0)$ by 2, reduces $|L(v_0)|$ and t by at most 2, and increases $\eta$. Thus (11) is preserved, and we are reduced to the case $\mathcal{W}=\emptyset$. $\square$

Subcase 4: $|\mathcal{W}| \ge 3$. Suppose first that there is a vertex v of $H-V(H_0)$ with three W-paths to $v_0$. If two of these paths have different undirected orientations, and the third one is directed, then we can color v so that at most one color is deleted from $L(v_0)$ via this last path, two are deleted by one of the other paths, and none by the third. Thus $|L(v_0)|$ is reduced by at most 3 altogether when we delete v. The other cases are similar and easier (in fact we delete at most two colors in these cases). In view of this and arguments from the previous cases, we can color all the W-neighbors of $v_0$ in such a way as to reduce $|L(v_0)|$ by at most $|\mathcal{W}|$. By (7), $|L(v_0)|-2d(v_0) \ge |\mathcal{W}|-2 >0$ after these vertices are deleted, and so (11) still holds, as the remaining terms are non-negative, and we are reduced to the case $\mathcal{W}=\emptyset$. $\square$

Proof of Theorem 1

Suppose for a contradiction that G is a minimal graph with $mad(G)<18/7$ and no homomorphism into $P_{7}^{*}$. Clearly G is connected, has no $^{\le }1$-vertices, and no adjacent 2-vertices (for if v and w were adjacent 2-vertices, then a coloring of $G-\{v,w\}$ could be extended to G, using Lemma 4(1)). Also

$$\begin{aligned} G \hbox { has no 4-cycle with alternating 2-vertices and 3-vertices}. \end{aligned}$$

(12)

For if we had such a cycle, say $v_1 v_2 v_3 v_4$, with $d(v_1)=d(v_3)=3$, $d(v_2)=d(v_4)=2$, then we could extend a $P_{7}^{*}$-coloring of $G-\{v_1, v_2, v_3, v_4\}$, back to a $P_{7}^{*}$-coloring of G, using Lemma 4(3) (and the fact that oriented neighborhoods in $P_{7}^{*}$ are mixed sets, not of the form $\{n,-n\}$), contradicting the minimality of G.

Let $M_0$ be the subgraph of G induced by the (non-empty) set of $^{\ge }3$-vertices, and let $\mathcal{G}$ be the (undirected looped multi-) graph obtained by contracting to a vertex each component of $M_0$ and one edge of each 2-path whose middle vertex is of degree 2 (clearly the choice of edge is immaterial). Let $G_M$ be the vertex of $\mathcal{G}$ formed by contracting a component M of $M_0$. Thus $G_M$ and $G_N$ are adjacent in $\mathcal{G}$ if and only if M and N are joined by a 2-path in G. We define the projection map $\pi$ from the $^{\ge }3$-vertices of G to $V(\mathcal{G})$ by $\pi (v)=G_M$, when $v \in M$.

Let S be a connected subgraph of $\mathcal{G}$, with at least one edge. We define $\lambda (S) \subseteq V(G)$ to be the union of $\pi ^{-1}(V(S))$ together with the 2-vertices whose neighbors are both in this set. If $\lambda (S)$ contains at most one $^{\ge }4$-vertex, then we define a structured graph $C(S)=(R,W,v_0,L)$ as follows: $R=G[\lambda (S)]$, $v_0$ is the vertex in $\lambda (S)$ for which $d_G(v_0)\ge 4$, if such a vertex exists, and is otherwise an arbitrarily chosen vertex in $\lambda (S)$ for which $d_G(v_0)=2$; $W=\{v \in V(R)\; |\; d_G(v)=2\} \setminus \{v_0\}$. It remains to define the list assignment L. By minimality we have a $P_{7}^{*}$-coloring c of $G-X$, where X is the union of V(R), and the set of 2-vertices of G which have one neighbor in $\lambda (S)$. For each $u \in V(R)$, we let L(u) be the intersection of the sets $N^{\varvec{\epsilon }} (c(v))$, taken over all 2-paths vwu from $v\in V(G-X)$ to u, where ${\varvec{\epsilon }}$ denotes the orientation of the path. By Lemma 3(2), each path deletes at most 2 colors from L(u), so that $|L(u)| \ge 2d_R(u)$ for $u \ne v_0$. Clearly $C(S)=(R,W,v_0,L)$ is a structured graph, and if R has an L-coloring, then this would extend the coloring c from $G-X$ to G—a contradiction. Thus

$$\begin{aligned} \hbox {If } C(S)=(R,W,v_0,L), \hbox { then } R \hbox { is not } L\hbox {-colorable}. \end{aligned}$$

(13)

In the remainder of the proof, we show that there is always an S for which C(S) is colorable, which gives the required contradiction. We begin with a simple case. If $G_M$ is a vertex of $\mathcal{G}$, where M is a tree whose vertices are all of degree 3 in G, then we refer to both the tree M and the vertex $G_M$ as regular. We show

$$\begin{aligned} \mathcal{G} \hbox { does not have two adjacent regular vertices}. \end{aligned}$$

(14)

For suppose that S is the subgraph of $\mathcal{G}$ induced by two adjacent regular vertices $G_M$ and $G_N$, then in $C(S):=(R,W,v_0,L)$, $v_0$ is a 2-vertex and $|L(v_0)|=6$. Thus R is L-colorable by Corollary 6(1), contrary to (13). Next we show

$$\begin{aligned}&\hbox {If } H \hbox { is a regular tree}, u \hbox { is a leaf of } H \hbox { and } v \hbox { is its neighbor in } H, \nonumber \\&\hbox {then } u \hbox { and } v \hbox { have no common neighbor in } G. \end{aligned}$$

(15)

Suppose firstly that (exactly) one such neighbor w existed. Necessarily $d(w)=2$. Because H is regular, u and v each have one neighbor outside the set $\{u,v,w\}$, and for u this neighbor has degree 2. By minimality of G we can $P_{7}^{*}$-color $G-\{u,v,w\}$. By Tables 1 and 2 and Lemma 4(2), this coloring extends back to G—a contradiction. If u and v have two common neighbors $w_1$ and $w_2$, then, since G is connected and H is regular, $\{u,v,w_1,w_2\}=V(G)$, and by Lemma 4(4) G is again $P_{7}^{*}$-colorable.

We assign each vertex v an initial charge of $\omega _0(v):=18-7d(v)$, and then discharge in two steps.

First discharging: Each 2-vertex sends half its charge to each of its neighbors.

We let $\omega _1(v)$ denote the new charge on v after this discharging. If $G_M$ is a vertex of $\mathcal{G}$, then we define $\omega _1(G_M)$ to be the sum of $\omega _1(v)$ taken over the vertices of M. Thus (here $d(v)=d_G(v)$)

$$\begin{aligned} \omega _1(G_M)= & {} \sum _{v \in M} [(18-7d(v)+2(d(v)-d_M(v))] \nonumber \\= & {} \sum _{v \in M} [18-5d(v)-2d_M(v)] \nonumber \\= & {} \sum _{v \in M} [3-2d_M(v)] -5\sum _{v \in M} [d(v)-3] \end{aligned}$$

(16)

Suppose that M contains n vertices in G. If M contains a cycle, then it has average degree $\ge 2$, and the first sum in (16) is at most $3n-4n=-n <0$. If M is a tree then its degree sum is $2n-2$, whence the first sum in (16) is $4-n$. The second sum in (16) is always non-negative, and is strictly positive if M has a $^{\ge }4$-vertex. Thus $\omega _1(G_M)>0$ only if M is a regular tree of order at most 3, in which case we will refer to $G_M$ as a donor vertex of $\mathcal{G}$, and M as a donor tree.

Second discharging: Each donor vertex in $\mathcal{G}$ sends its charge to its neighbors, with an equal charge sent out along each edge (other than loops).

In order to do this we must be sure that each donor vertex $G_M$ of $\mathcal{G}$ has at least one incident edge which is not a loop. If $|M|=1$ there are 3 such edges. If $|M|=2$ there are 4, by (15). If $|M|=3$, that is M is a 2-path $v_1 v_2 v_3$, then (15) again shows that neither $v_1$ nor $v_3$ have a common neighbor with $v_2$, and (12) shows that $v_1$ and $v_3$ have at most one common neighbor other than $v_2$. Thus every donor vertex of $\mathcal{G}$ is able to discharge, and moreover the charge sent along each edge from an N-vertex donor tree is at most 1 / N.

We denote the charge on $G_M$ after this second discharging by $\omega _2(G_M)$. Since, by (14) regular vertices cannot be adjacent, they do not receive any charge; thus $\omega _2(G_M) \le 0$ if $G_M$ is regular. If $G_M$ is non-regular, then

$$\begin{aligned} \omega _2(G_M)\le & {} \sum _{v \in M}[(18-7d(v))+3(d(v)-d_M(v))]\nonumber \\= & {} 3\sum _{v \in M} [2-d_M(v)]-4\sum _{v \in M} [d(v)-3] \end{aligned}$$

(17)

The first term in (17) is 6 when M is tree, and $\le 0$ otherwise. Thus $\omega _2(G_M) \le 0$ whenever M contains a cycle, a vertex with $d_G(v) \ge 5$ or more than one vertex with $d_G(v)=4$. By assumption, $d_G(v) \ge 4$ for at least one vertex in M, so that $\omega _2(G_M) \le 2$. Moreover the estimate at (17) is based on the assumption that $G_M$ receives a charge of 1 through each incident edge in $\mathcal{G}$, and so can be reduced by 2 for each loop at $G_M$, and by 1/2, 2/3 and 1 respectively for each edge connecting M to a donor tree of order 2, a donor tree of order 3 or a non-donor.

Thus $\omega _2(G_M)>0$ only if M is a tree with one vertex $v_0$ of degree 4 in G, and none of higher degree, and which has no two vertices with a common neighbor (which would give a loop at $G_M$). If $A_2$ $A_3$ and A represent the number of paths in $\mathcal{G}$ from M to donors of order 2, donors of order 3, and non-donors respectively, then we also must have

$$\begin{aligned} \frac{1}{2} A_2+\frac{2}{3}A_3+A <2 \end{aligned}$$

(18)

Suppose that we have such an M. Let S be the subgraph of $\mathcal{G}$ induced by $G_M$ and its donor neighbors. We will show that Lemma 7 is applicable to the structured graph C(S) defined before (13).

Conditions (12) and (18) give (4) and (5) respectively, while the fact that no two vertices in M have a common neighbor gives (6). We verify that inequalities (7) and (8) also hold.

Let $\mathcal{N}$ be the set of non-donor neighbors of $G_M$. By (18) $|\mathcal{N}|+|\mathcal{P}|\le 1$ (since each member of $\mathcal{P}$ has at least two W-paths to M). Let $G_N$ be the sole member of $\mathcal{N}$, if it exists, in which case there is at exactly one W-path from N to M. If such a path exists, we let x denote its end-vertex in M. If $x=v_0$, then in C(S) $d(v_0)=3$, and $|L(v_0)| \ge 4$; otherwise $d(v_0)=4$, and $|L(v_0)|=6$. In either case (7) holds, and (8) will follow if we can show

$$\begin{aligned} |\mathcal{W}|-|\mathcal{P}_2|+\frac{t+2\eta -2|\mathcal{P}_1|}{5} \ge 3. \end{aligned}$$

(19)

Note that $|\mathcal{T}|+|\mathcal{W}|=d(v_0)$. For each $T \in \mathcal{T}$, $\sigma (T) \ge 4$, except possibly when $|\mathcal{N}|=1$ and $x \ne v_0$, in which case $\sigma (T) = 2$ is possible for the tree which contains x.

We first suppose that $\mathcal{P}_2=\emptyset$ and either $\mathcal{N} = \emptyset$ or $x \ne v_0$. In both these cases $t+2\eta -2|\mathcal{P}_1| \ge 4|\mathcal{T}|+2\eta -2$ (if $\mathcal{N}= \emptyset$, then $t \ge 4|\mathcal{T}|$; if $\mathcal{N} \ne \emptyset$, then $\mathcal{P}_1=\emptyset$). Also $|\mathcal{W}|-|\mathcal{P}_2|=|\mathcal{W}|=4-|\mathcal{T}|$. Thus (19) follows if $2\eta \ge |\mathcal{T}|-3$. When $|\mathcal{T}|=4$, $|\mathcal{W}|=0$, and so $\eta =2$; otherwise the inequality is trivial.

In the remaining case, either $|\mathcal{P}_2|=1$ or $|\mathcal{N}| =1$ with $x=v_0$. In both cases $|\mathcal{W}|-|\mathcal{P}_2|=3-|\mathcal{T}|$, and $t \ge 4|\mathcal{T}|$. Thus (19) follows if $2\eta \ge |\mathcal{T}|$. Suppose first that $|\mathcal{P}_2|=1$; this forces $|\mathcal{W}| \ge 1$ (otherwise, by the definition of $\mathcal{P}_2$, there would be at least four W-paths from the path in $\mathcal{P}_2$ to M, contrary to (18)). If $|\mathcal{W}| = 1$, then $\eta =2$, and if $|\mathcal{W}| \ge 2$, then $\eta =1$, so $2\eta \ge 4-|\mathcal{W}|=|\mathcal{T}|$ holds in either case. Now suppose that $x=v_0$. In this case recall that $|L(v_0)| \ge 4$, and clearly we may assume that equality holds. Thus we may assume that $\eta \ge 1$, which gives the required inequality for $|\mathcal{T}|\le 2$. If $|\mathcal{T}|=3$, then $|\mathcal{W}|=3-|\mathcal{T}|=0$, whence $\eta =2$, so again we always have $2\eta \ge |\mathcal{T}|$.

Thus in all cases (7) and (8) hold, so by Lemma 7, the underlying graph of C(S) is L-colorable, contrary to (13). We conclude that $\omega _2(G_M) \le 0$ for all the vertices of $\mathcal{G}$, so that the sum of these charges over all of the vertices in $\mathcal{G}$ is non-positive, whence the same is true for G, but this contradicts the hypothesis that $mad(G)<18/7$. $\square$

Fig. 2

A non-$P_{7}^{*}$-colorable graph

We finish with an example to show that Conjecture 2 is sharp. The oriented graph in Fig. 2 has maximum average degree 8/3, and we show that it is not $P_{7}^{*}$-colorable. In fact it is easier to consider colorings from $P_7$, because of the greater symmetry of that graph. Suppose then that the graph in the figure has a $P_7$-coloring. Since $P_7$ is arc transitive, we may assume that a and c are colored 0 and 1 respectively. Since each of b, c and d is joined to each of the other two vertices, by a directed 2-path, these vertices take distinct colors in $N^{(1)}(0)=\{1,2,4\}$. Thus e must be colored from $N^{(-1)}(2) \cap N^{(-1)}(4) \cap N^{(1)}(1) = \emptyset$, so no such coloring exists.