Julio Araujo

Frédéric Havet
email: frederic.havet@cnrs.fr

Mathieu Schmitt
email: mathieu.schmitt@ens-lyon.fr

Steinberg-like theorems for backbone colouring $

Keywords: Graph Colouring, Planar Graph, Backbone Colouring, Steinberg's Conjecture

come   L'archive ouverte pluridisciplinaire

Introduction

In this paper, all graphs are considered to be simple and we use standard terminology as the one in [START_REF] Bondy | Graph theory[END_REF].

Let G = (V, E) be a graph, and H = (V, E(H)) be a spanning subgraph of G, called its backbone. A k-colouring of G is a mapping f : V → {1, . . . , k}. Let f be a k-colouring of G. It is a proper colouring if |f (u) -f (v)| ≥ 1 for every edge uv ∈ E(G). It is a q-backbone colouring for (G, H) if f is a proper colouring of G and |f (u) -f (v)| ≥ q for all edges uv ∈ E(H). The chromatic number χ(G) is the smallest integer k for which there exists a proper k-colouring of G. The q-backbone chromatic number of (G, H), denoted by BBC q (G, H), is the smallest integer k for which there exists a q-backbone k-colouring of (G, H) [START_REF] Broersma | Backbone colorings for graphs: Tree and path backbones[END_REF].

Note that if f is a proper k-colouring of G, then the function g : V → {1, . . . , q • k -q + 1} defined by g(v) = q • f (v) -q + 1 is a q-backbone colouring of (G, H), for any spanning subgraph H of G. Moreover it is well-known that if G = H and f is a proper χ(G)-colouring of G, this q-backbone colouring g of (G, H) is optimal. Therefore, since BBC q (H, H) ≤ BBC q (G, H) ≤ BBC q (G, G), we have q • χ(H) -q + 1 ≤ BBC q (G, H) ≤ q • χ(G) -q + 1.

(

) 1
One can generalise the notion of backbone colouring by allowing a more complicated structure of the colour space. A natural choice is to impose a circular metric on the colours. We can see Z k 1 as a cycle of length k with vertex set {1, . . . , k} together with the graphical distance | • | k . Then |a -b| k ≥ q if and only if q ≤ |a -b| ≤ k -q. A circular q-backbone k-colouring of G or q-backbone Z k -colouring of (G, H) is a mapping f : V (G) → Z k such that c(v) = c(u), for each edge uv ∈ E(G), and |c(u) -c(v)| k ≥ q for each edge uv ∈ E(H). The circular q-backbone chromatic number of a graph pair (G, H), denoted CBC q (G, H), is the minimum k such that (G, H) admits a circular q-backbone k-colouring.

Note that if f is a circular q-backbone k-colouring of (G, H), then f is also a q-backbone k-colouring of (G, H). On the other hand, observe that a q-backbone k-colouring f of (G, H) is a circular q-backbone (k + q -1)-colouring of (G, H). Hence for every graph pair (G, H), where H is a spanning subgraph of G, we have BBC q (G, H) ≤ CBC q (G, H) ≤ BBC q (G, H) + q -1.

(

Combining Inequalities ( 1) and ( 2), we observe that

q • χ(H) ≤ CBC q (G, H) ≤ q • χ(G). (3)
In this paper, we focus on the particular case when G is a planar graph and H is a forest (i.e. an acyclic graph). Inequality [START_REF] Bondy | Graph theory[END_REF] and the Four-Colour Theorem [START_REF] Appel | Every planar map is four colorable[END_REF] imply that for any planar graph G and spanning subgraph H, BBC q (G, H) ≤ 3q + 1. However, for q = 2, Broersma et al. [START_REF] Broersma | Backbone colorings for graphs: Tree and path backbones[END_REF] conjectured that this is not best possible if the backbone is a forest. Conjecture 1. If G is planar and H is a forest in G, then BBC 2 (G, H) ≤ 6. This conjecture would be tight even if H is a Hamilton path as there are examples of planar graph G and Hamilton path H in G, for which BBC 2 (G, H) = 6. Furthermore, Havet et al. [START_REF] Havet | Circular) backbone colouring: Forest backbones in planar graphs[END_REF] proved that given a planar graph G and a Hamilton path H in G, it is NP-complete to decide whether BBC 2 (G, H) ≤ 5. Campos et al. [START_REF] Campos | Backbone colouring: Tree backbones with small diameter in planar graphs[END_REF] proved Conjecture 1 when H is a tree of diameter at most 4.

For larger values of q, Havet et al. [START_REF] Havet | Circular) backbone colouring: Forest backbones in planar graphs[END_REF] proved the following.

Theorem 2. If G is planar and H is a forest in G, then BBC q (G, H) ≤ q + 6.

For q ≥ 4, they also show that Theorem 2 is best possible. On the other hand, they conjecture that if q = 3, Theorem 2 is not best possible.

Conjecture 3. If G is planar and H is a forest in G, then BBC 3 (G, H) ≤ 8.
1 Whenever we refer to Z k , we mean the group of integers modulo k, also denoted by Z/nZ.

2

Regarding circular backbone colouring, Havet et al. [START_REF] Havet | Circular) backbone colouring: Forest backbones in planar graphs[END_REF] proved the following.

Theorem 4. If G is planar and H is a forest in G, then CBC q (G, H) ≤ 2q + 4.
They also conjectured that this upper bound can be reduced by at least 1.

Conjecture 5. If G is planar and H is a forest in G, then CBC q (G, H) ≤ 2q+3.
Observe that Inequalities (1) and (3) imply that Conjectures 1, 3, and 5 for q ≤ 3, hold if G is has a 3-colouring. There are many sufficient conditions implying that a planar graph has a 3-colouring. For example, the celebrated Grötzsch's Theorem [START_REF] Grötzsch | Zur Theorie der diskreten Gebilde. VII. Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel[END_REF] asserts that planar graphs with girth at least 4 admit a 3-colouring.

One of the most famous conjectures on planar graphs was posed in 1976 by Steinberg (see [START_REF] Steinberg | The state of the three color problem[END_REF]).

Conjecture 6 (Steinberg, 1976). If G is a planar graph with no cycles of length 4 or 5, then χ(G) ≤ 3.

Note that this long standing conjecture could be proved by showing that CBC 2 (G, G) = 6, for a planar graph G containing no C 4 nor C 5 as a subgraph.

In this paper, we give evidences to the above conjectures. We first settle Conjecture 5 for q = 2 when G is a planar graph without cycles of length 4 or 5.

Theorem 7. If G is a planar graph with no cycles of length 4 or 5 and H is a forest in G, then CBC 2 (G, H) ≤ 7.

We then improve the upper bound when H is a path forest. A forest is a path forest if all its connected components are paths.

Theorem 8. If G is a planar graph without cycles of length 4 or 5, and H is a path forest in G, then CBC 2 (G, H) ≤ 6.

Hence when G is a planar graph with no cycles of length 4 or 5 and H is a path forest, Conjecture 1 and Conjecture 5 for q = 2 hold. It also implies that Conjecture 5 for q = 3 holds for such graph pair (G, H) thanks to the following lemma.

Lemma 9. Let k and q be positive integers, G a graph and H a subgraph of G. If CBC q (G, H) ≤ q × k, then CBC q (G, H) ≤ q × k, for all q ≥ q.

Proof. Let c be a q-backbone qk-colouring of (G, H). Define k intervals of colours I j = {(j -1)q + 1, . . . , jq}, for every 1 ≤ j ≤ k. We now define a proper q -backbone q k-colouring of (G, H) c as the following: if c(v) ∈ I j , then c (v) = c(v) + (j -1)(q -q), for every 1 ≤ j ≤ k and v ∈ V (G). Note that c must be a proper colouring of G since c is a proper colouring of G. Moreover, for an edge uv ∈ E(H), we have that c(u) and c(v) cannot lie on the same interval

I j , for some 1 ≤ j ≤ k. Thus, k -q = (k -q) + (q -q) ≥ |c(u) -c(v)| ≥ q + (q -q) = q .
Corollary 10. If G is a planar graph without cycles of length 4 or 5, and

H is a path forest in G, then CBC 3 (G, H) ≤ 9.
The remainder of this paper is devoted to the proofs of Theorems 7 and 8. Both results are proved by supposing that a minimal counter-example with respect to the number of vertices exists. In Section 2, we present general properties of such counter-examples that we use in both proofs. Then, we prove Theorems 7 and 8 in Sections 3 and 4, respectively.

Preliminaries

In this section, we first introduce some useful definitions and notations. We then establish properties that we shall use to prove the two above-mentioned theorems. We first prove simple properties of a planar graph without cycles on 4 or 5 vertices, then we establish some properties of minimal counter-examples to Theorems 7 and 8.

Definitions and notations

Let S ⊆ V (G) be a subset of vertices of G and F ⊆ E(G) be a subset its Let (G, H) and (G , H ) be graph pairs such that H ⊆ G and H ⊆ G . We say that (G , H ) is a subpair of (G, H) if H ⊆ H and G ⊆ G. We say that (G , H ) is a proper subpair of (G, H) if it is a subpair of (G, H) and H ⊂ H or G ⊂ G. Note that the previous or condition is not exclusive.

A graph pair (G,

H) is (k, 2)-minimal if CBC 2 (G, H) > k, but CBC 2 (G , H ) ≤ k for every proper subpair (G , H ) of (G, H).
For every colour 1 ≤ a ≤ k, let [a] k be the set of colours b ∈ {1, . . . , k} satisfying |a -b| < 2 or |a -b| > k -2. Note that [a] k has always 3 colours.

We say that c is a partial circular 2-backbone k-colouring of (G, H) if c is a circular 2-backbone k-colouring of a subpair of (G, H). Let c be a partial circular 2-backbone k-colouring of a graph pair (G, H). We say that a colour a is available (or possible) at vertex v ∈ V (G) if none of its neighbours in G is coloured a and none of its neighbours in H has a colour in [a] k . We denote by Av c (G, H, v) the set of available colours at v in c.

We emphasize that this definition of available colour does not require that the vertex v is not coloured. If v is already coloured, observe that it can be recoloured by any available colour and we obtain another feasible partial circular 2-backbone colouring of the same subpair of (G, H).

Similarly, we say that a colour a is forbidden at vertex v due to S ⊆ N G (v) if there exists u ∈ S ∩ N G (v) coloured a, or if there exists u ∈ S ∩ N H (v) with colour in [a] k . When we consider S = N G (v), we simply mention forbidden at vertex v. We denote the set of forbidden colours at v in c by Fb c (G, H, v).

We also define a colour a is strongly forbidden at vertex v due to S ⊆ N G (v) if one cannot obtain a partial circular 2-backbone k-colouring by assigning to v the colour a and (re)colouring each vertex u ∈ S with one colour in Av c (G, H, u).

We often omit G, H and c from these notations when they are clear in the context. Observe that Av(v) = Z k \ Fb(v).

In the following sections, the graph H is a forest. Then, a vertex of degree 0 (resp. 1, at least 2) in H is called an isolated vertex (resp. a leaf, a node). We also denote by leaf(H) the number of leaves in H, by isol(H) the number of isolated vertices in H and by comp(H) the number of its connected components.

Planar graphs with no cycles of length 4 or 5.

A well-known result on planar graphs is Euler's Formula:

Theorem 11 (Euler's Formula). If G is a connected plane graph, then

|V (G)| -|E(G)| + |F (G)| = 2.
Let τ (G) denote the number of triangles of a graph G.

Lemma 12. If G is a planar graph with no C 4 , then the three statements hold:

(i) every two (not identical) triangles do not share an edge;

(ii) every vertex v ∈ V (G) belongs to at most d G (v)/2 triangles; (iii) 3τ (G) ≤ |E(G)|.
Proof. To prove (i), observe that two triangles with different vertex sets cannot share at least one edge, otherwise there would be a C 4 in G. (ii) follows directly from (i) by observing that the graph induced by the neighbourhood of v contains no path of length 2, since there is no 4-cycles. Finally, we derive (iii) from (ii).

Indeed (ii) implies 3τ (G) ≤ v∈V (G) d G (v)/2 . Since v∈V (G) d G (v)/2 = |E(G)|, we obtain 3τ (G) ≤ |E(G)|.
Lemma 13. If G is a connected planar graph with no cycles of length 4 or 5 and

G = K 3 , then |E(G)| ≤ 2|V (G)| -4.
Proof. Without loss of generality, we may assume tat G is embedded in the plane. By Euler's Formula, we have 6|E

(G)| = 6|V (G)| + 6|F (G)| -12. Hence 4|E(G)| = 6|V (G)| - f ∈F (G) (d(f ) -6) -12 ≤ 6|V (G)| + 3|F 3 (G)| -12 where F 3 (G) is the set of 3-faces in G. Since G = K 3 , we observe that |F 3 (G)| ≤ τ (G), and then 3|F 3 (G)| ≤ |E(G)|, by Lemma 12-(iii). Hence, 3|E(G)| ≤ 6|V (G)| -12, that is |E(G)| ≤ 2|V (G)| -4.
Properties of (k, 2)-minimal pairs Lemma 14. Let (G, H) be a (k, 2)-minimal pair and c be a partial 2-backbone k-colouring of (G, H). If uv ∈ E(H) and 1 ≤ | Av(u)| ≤ 3, then at most 4 -| Av(u)| colours are strongly forbidden at v due to u.

Proof. Observe that a colour cannot be assigned to v due to u with uv ∈ E(H) if and only if it is in the set F = a∈Av(u) [a] k . Note that this set F is maximized when Av(u) has consecutive colours. Thus, F has at most 3 colours when

| Av(u)| = 1, F has at most 2 colours when | Av(u)| = 2 and F has at most 1 colour when | Av(u)| = 3. The total degree of a vertex v in (G, H) is d t (v, G, H) = d G (v) + 2d H (v).
We often simplify the notation d t (v, G, H) to d t (v) when G and H are clear from the context. Note that d t (v) is an upper bound on the maximum number of forbidden colours at v, when extending a circular 2-backbone k-colouring of (G, H) -v to v.

Lemma 15. If (G, H) is a (k, 2)-minimal pair, then G is connected. Proof. By contradiction, suppose that G is not connected and let C ⊂ V (G) be a connected component of G. Since (G, H) is (k, 2)-minimal, observe that (G, H) -C and (G, H)[C]
admit circular 2-backbone k-colourings c and c , respectively. Combining c and c , one obtains a circular 2-backbone k-colouring of (G, H). This is a contradiction to the hypothesis that CBC 2 (G, H) > k.

Lemma 16. If (G, H) is a (k, 2)-minimal pair, then d t (v) ≥ k, for all v ∈ V (G).
Proof. Assume for a contradiction that there is a vertex v such that d t (v) < k. By minimality of (G, H), (G, H) -v admits a circular 2-backbone k-colouring c. Now at most d t (v) colours are forbidden at v. Hence c can be extended into a circular 2-backbone k-colouring of (G, H), a contradiction.

Lemma 17. Let (G, H) be a (k, 2)-minimal pair. If uv ∈ E(H), then d t (u) + d t (v) ≥ 2k + 2. Proof. Let x ∈ {u, v}. Set r(x) = d t (x) -k. If r(x) ≥ 2,
then we have the result by Lemma 16. So we may assume that r(x) ≤ 1. By minimality of (G, H), there exists a circular 2-backbone k-colouring c of (G, H) -{u, v}.

Since uv ∈ E(H), the total degree of x in (G, H) -{u, v} is k + r(x) -3. Hence there is a set Av(x) of k -(k + r(x) -3) = 3 -r(x) available colours at x.
Let F be the set of strongly forbidden colours at u due to v. By Lemma 14,

|F | ≤ r(u) + 1. Since (G, H) is a (k, 2)-minimal pair, the colouring c cannot be modified into a circular 2-backbone k-colouring of (G, H). Thus |F | ≥ | Av(x)|, so r(u) + 1 ≥ 3 -r(v). Hence d t (u) + d t (v) ≥ 2k + 2.

Forest backbone

The aim of this section is to prove the following. Theorem 7. If G is a planar graph with no cycles of length 4 or 5 and H is a forest in G, then CBC 2 (G, H) ≤ 7.

From this point to the end of Section 3, let (G, H) be a minimal counterexample to Theorem 8 and whenever we use the notation [a], when a is a colour, we mean [a] 7 . By Lemmas 15, 16 and 17, observe that G must be connected, each vertex must have total degree at least 7 and, for each edge uv ∈ H, d t (u) + d t (v) ≥ 16. We now prove extra properties of such a counter-example.

Lemma 18. Let P = uvw be a path in H and c be a circular 2-backbone 7-colouring of (G, H) -{u, v, w}. If | Av(u)| = 3 and | Av(w)| = 3, then at most 3 colours are strongly forbidden at v due to {u, w} (no matter whether uw ∈ E(G)).

Proof. Suppose | Av(u)| = 3 and | Av(w)| = 3. Note that if we show that at most 3 colours are strongly forbidden when uw ∈ E(G), then we also show that the same holds when uw / ∈ E(G). In fact, we have the same amount of colours and one constraint less, the one that u and w must receive disjoint colours, to extend c to (G, H). So let us assume uw ∈ E(G).

Let A 1 = Av(u) and A 2 = av(w). Let N be the set colours of Z 7 that are consecutive to some colour of Av(u). Observe that |N | ≥ 4 and that |N | = 4 if and only if Av(u) = {i, i + 2, i + 4} for some i and N = Z 7 \ Av(u).

If N ∩ Av(w) = ∅, then |N | = |Z 7 | -| Av(w)| = 4. It follows that Av(w) = Av(u) = {i, i + 2, i + 4}
for some i, and the set of strongly forbidden colours at v is {i + 1, i + 3} (recall that uw ∈ E(G)).

Henceforth we may assume that N and Av(w) intersect. Thus there are two consecutive colours a 1 ∈ Av(u) and a 2 ∈ Av(w). Without loss of generality, we may assume that a 2 = a 1 + 1. Observe that the three colours not in [a 1 ] ∪ [a 2 ] are not strongly forbidden at v.

If a 1 -1 or a 2 + 1 is not strongly forbidden, we have the result. So we may assume that both a 1 -1 and a 2 +1 are strongly forbidden. Then Av(u) = [a 1 -1] or [a 1 -1] contains exactly two colours of each set Av(u) and Av(w) and the colour of Av(u) \ [a 1 -1] is the same as the colour of Av(w)

\ [a 1 -1]. Similarly, either Av(w) = [a 2 + 1] or [a 2 + 1]
contains exactly two colours of Av(u) and exactly two colours of Av(w) and the colour of Av(u)\[a 2 + 1] is the same as the colour of Av(w) \ [a 2 + 1]. Consequently, we necessarily have Av(u) = [a 1 -1] and Av(w) = [a 2 + 1]. Now a 1 and a 2 are not strongly forbidden at v and there are just two strongly forbidden colours at v due to {u, w}.

Lemma 19. If S = {s 1 , . . . , s t } is the set of neighbours of v in H such that d t (s i ) = 7, for every 1 ≤ i ≤ t, then d t (v) ≥ 8 + t. Proof. The total degree of v in (G, H) is d t (v) = 3t + d with d the total degree of v in (G, H) -S. In particular, if t ≥ 4, then d t (v) ≥ 3t ≥ 8 + t.
Therefore, we may assume that t ≤ 3. If t = 1, then Lemma 17 yields the results. Henceforth, we now assume t ∈ {2, 3}.

By minimality of (G, H), there exists a circular 2-backbone 7-colouring c of (G, H) -(S ∪ {v}). In (G, H) -(S ∪ {v}), the total degree of s i is at most 4. Hence, there is a set A i of at least 3 available colours at s i .

Let F 1,2 (resp. F 3 ) be the set of strongly forbidden colours at v by {s 1 , s 2 } (resp. {s 3 }). By Lemmas 17 and 18, we have

|F 3 | ≤ 4 -|A 3 | ≤ 1 and |F 1,2 | ≤ 3.
Since (G, H) is minimal, then all seven colours must be strongly forbidden at v. If t = 2, this yields 7

≤ d + |F 1,2 |. But d t (v) = d + 6. So d t (v) ≥ 13 -|F 1,2 | ≥ 10. If t = 3, this yields 7 ≤ d + |F 1,2 | + |F 3 |. But d t (v) = d + 9. So d t (v) ≥ 16 -|F 1,2 | -|F 3 | ≥ 11.
Corollary 20. If (G, H) be a (7, 2)-minimal pair such that G is a planar graph and H is a spanning forest of G, then

v∈V (G) d t (v) ≥ 8|V (G)| -isol(H) . Proof. Recall that Lemma 16 states that d t (v) ≥ 7, for every v ∈ V (G). In particular, if v is an isolated vertex of H, then d t (v) ≥ 7. If v is not isolated and d t (v) = 7
, then v each neighbour u of v in H has total degree at least 9, by Lemma 17.

Let u be a vertex such that d t (u) ≥ 9 and define t(u) as the number of neighbours v of u in H such that d t (v) = 7. Lemma 19 states that d t (u) ≥ 8 + t(u). In particular,

d t (u) + v∈N H (u) d t (v) ≥ 8.
Thus, let S 9 + (resp. S 8 , S 7 ) be the set of non-isolated vertices with total degree at least 9 (resp. exactly 8, exactly 7). Let S I denote the set of isolated vertices of H. Observe that {S 9 + , S 8 , S 7 , S I } form a partition of V (G) and then:

v∈V (G) d t (v) = v∈S 9 + d t (v) + v∈S8 d t (v) + v∈S7 d t (v) + v∈S I d t (v) ≥ 8 • |S 8 | + 8 • |S 9 + ∪ S 7 | + 7 • isol(H) = 8 • |V (G)| -isol(H)
Proposition 21. Let G be a connected plane graph and H be a spanning forest of G. Then

v∈V (G) (2d t (v) -14) + f ∈F (G) (d(f ) -6) = -12 -8 comp(H). Proof. Since H is a spanning forest of G, note that |E(H)| ≤ |V (G)|-comp(H).
Consequently, by using Euler's Formula, we have:

v∈V (G) (2d t (v) -14) + f ∈F (G) (d(f ) -6) = 2 v∈V (G) d G (v) + 4 v∈V (G) d H (v) -14|V (G)| + 2|E(G)| -6|F (G)| = 4|E(G)| + 8|E(H)| -14|V (G)| + 2|E(G)| -6|F (G)| ≤ 6|E(G)| -6|V (G)| -6|F (G)| -8 comp(H) = -12 -8 comp(H).
We are now ready to prove Theorem 7.

Proof of Theorem 7. Let (G, H) be a minimal counter-example with respect to the number of vertices. It is easy to check that the theorem holds when |V (G)| ≤ 3. Hence we have |V (G)| ≥ 4, and (G, H) is (7, 2)-minimal. By Lemma 15, G must be connected.

Set

Σ := v∈V (G) (2d t (v) -14) + f ∈F (G) (d(f ) -6)
. Proposition 21 states that Σ ≤ -12 -8 comp(H). We prove that such a counter-example does not exist by finding a contraction to this fact.

By Corollary 20, recall that

v∈V (G) d t (v) ≥ 8|V (G)| -isol(H). Conse- quently, v∈V (G) (2d t (v) -14) ≥ 2|V (G)| -2 isol(H).
Since G has no cycle of length 4 or 5,

f ∈F (G) (d(f ) -6) ≥ -3τ (G) ≥ -|E(G)| ≥ 4 -2|V (G)|,

Path forest backbone

Recall that a path forest is a forest whose connected components are paths. The aim of this section is to prove the following.

Theorem 8. If G is a planar graph without cycles of length 4 and 5, and H is a path forest, then CBC 2 (G, H) ≤ 6.

In order to prove this theorem, we also consider a minimum counter-example of Theorem 8. We also consider that G is embedded in the plane, so that its face set is defined. In Subsection 4.1, we establish some properties of this counter-example. Then, in Subsection 4.2, we use these properties to derive a contradiction via the Discharging Method.

We first need some definitions. For convenience, in this section we often abbreviate circular 2-backbone 6-colouring by colouring. With a slight abuse of notation, we also refer to the set of colours as Z 6 so that the modulo operation is already defined (recall that initially the set of colours of a proper k-colouring is {1, . . . , k}). We also write [c] instead of [c] 6 . Moreover, we say that two colours a and b are opposite if |a -b| 6 = 3.

Recall that (G , H ) is a subpair of (G, )] are the corresponding induced subgraphs. A configuration of (G, H) is an induced subpair in which the total degree of some of the vertices is constrained to given values.

H) if H ⊆ H and G ⊆ G. We say that (G , H ) is an induced subpair of (G, H) if V (H ) = V (G ) and H = H[V (G )] and G = G[V (G
In the remainder of this section, we represent a configuration (G , H ) by a representation of the graph G with the edges of H in bold and a number t inside the circle corresponding to vertex v if the total degree of v must be equal to t, except for the last configuration where we use ≤ 8 inside a circle to represent that the corresponding vertex has total degree at most 8.

Let C = (G , H ) be a configuration of (G, H). A vertex of C whose degree is not constrained to some value is called external. The set of external vertices of C is by Ext(C). The vertices of C whose degree is fixed to a number are the internal vertices of C and they form the set Int(C). Thus, Ext(C) and Int(C) form a partition of V (G ). We emphasize that, in all figures of configurations in this section, we depict all neighbours of an internal vertex.

In order to reach a contradiction and prove that no minimum counterexample to Theorem 8 exists, we show that several configurations are forbidden. By forbidden we mean that for these configurations one may extend some circular 2-backbone 6-colouring of (G, H) -Int(C) to (G, H).

One last notion we require is the following: given a configuration C of (G, H) and a vertex x ∈ Ext(C), we say that two colourings c 1 , c 2 of (G, H) -Int(C) are C-twin at x, if c 1 (x) = c 2 (x) and c 1 (x ) = c 2 (x ), for every x ∈ Ext(C) \ {x} (recall that by colouring we now mean circular 2-backbone 6-colouring).

Properties of a minimal counter-example

In the remainder of this section, (G, H) is always a minimum counterexample to Theorem 8. It means that G is planar containing no cycles on 4 or 5 vertices, H ⊆ G is a spanning path forest of G and (G, H) is a minimal (6, 2)-pair. In particular, recall that for every vertex set S ⊆ V (G), (G, H) -S admits a circular 2-backbone 6-colouring and (G, H)\e also does, for every edge e ∈ E(G).

We now establish some properties of (G, H). First recall that Lemmas 12, 16 and 17 yield the following.

Property 22. Every vertex v ∈ V (G) is incident to at most d(v)/2 triangles. Property 23. For each vertex v ∈ V (G), d t (v) ≥ 6.
Property 24. If uv ∈ E(H), then d t (u) + d t (v) ≥ 14.

We now study more deeply the structure of (G, H). Let C 0 be a configuration consisting of path uvw in H such that uw / ∈ E(G) and d t (v) = 6, i.e. Int(C) = {v} and Ext(C) = {u, w}. Let C 0 be the configuration C 0 when the edge uw ∈ E(G) exists (see Figure 1). (G ,H ) (u) ≤ 4, vertex u has at least two available colours with respect to c. Moreover, since u is a node (i.e. a vertex of degree at least 2 in H) there are three consecutive colours in Z 6 that are forbidden to u. So there are at least two available colours at u that are not opposite. Hence one can assign to u one of its available colours that does not belong to {c(w), c(w) + 3} and there would be at least one available colour to extend c to v. Consequently there is a circular 2-backbone 6-colouring of (G, H), a contradiction.

Let C 1 be a configuration on 5 vertices u , u, v, v and u , such that u uvv form an induced path P 1 in G and in H, u is not a neighbour of a vertex of P 1 in H, but it has exactly two neighbours of P 1 in G: u and v. Moreover, the total degree of u and v must be equal to 7, i.e. Int(C 1 ) = {u, v} (see Figure 2).

(v) ∈ Av(v) so that |c(u) -c(v)| 6 ≥ 2.
We then obtain a colouring of (G, H), a contradiction.

(ii) Suppose for a contradiction that d t (G,H) (u ) ≤ 7. The graph (G, H) -{u, v} admits a circular 2-backbone 6-colouring c. The number of available colours at u in this colouring is at least 2. Hence, we can extend c into two C 1 -twin colourings of (G, H) -{u, v} at u . This contradicts (i).

Let C 2 be a configuration on eight vertices u , u, v, v , w, u , v and z, such that u uvv w form an induced path P 2 in G and in H, the vertices u , v and z are not neighbours of a vertex of P 2 in H, but u and v have exactly two neighbours of P 1 in G: u and v, v and v , respectively; and the only neighbour of z in P 2 is v . Moreover, td t (u) = 7 and d t (v) = d t (v ) = 8. The configuration C 2 is obtained from C 2 by removing z and changing on the total degree of v to 7 (see Figure 3). Note that Int( Proof. (i) Suppose for a contradiction that there are two C-twin colourings at u , say c and c . First we claim that we can extend c and c to v with a colour c(v

C 2 ) = Int(C 2 ) = {u, v, v }. 8 7 8 8 7 7 u' u v v' w u'' v'' z u' u v v' w u'' v''
) = c (v ) which is not opposite to c(v ). Indeed, if c(v ) ∈ [c(w)], one we can choose c(v ) = c (v ) in {c(w) + 2, c(w) + 3, c(w) + 4} \ {c(z), c(v ) + 3}. Otherwise, c(v ) / ∈ [c(w)] and in this case one can choose c(v ) = c (v ) in {c(w) + 2, c(w) + 3, c(w) + 4} \ {c(v ), c(z)}.
Consider now that c and c were extended to v so that c(v

) = c (v ) is not opposite to c(v ). If |c(v ) -c(v )| 6 = 1, then c(v )
is forbidden to v by both v and v . So this case behaves exactly as if the edge vv did not exist in C and we have a configuration equivalent to C 1 . Thus, similarly to the proof of Property 26-(i), one derives that no pair of C-twin colourings at u exists. Henceforth |c(v ) -c(v )| 6 = 2. Without loss of generality, assume that c(v ) = 1 and c(v ) = 3. Observe that Av(v) = {5, 6} \ {c(u )} for both colourings c and c .

We distinguish few cases according to the value of c(u ). In each of them, we extend c to a colouring of (G, H), which is a contradiction.

• Case 1: c(u ) = 1. Recall that c and c are C-twin colourings at u . Thus, without loss of generality, assume that c(u (ii) Suppose for a contradiction that d t (G,H) (u ) ≤ 7. The graph (G, H) -{u, v, u , v } admits a colouring c. The number of available colours at u in c is at least 2. Hence, we can extend c into two C-twin colourings at u . This contradicts (i).

) = 3. One can then choose c(u) ∈ [3] \ [c(u )] and c(v) ∈ {5, 6} \ [c(u)]. • Case 2: c(u ) ∈ {2, 3}. The set Av(u) of available colours at u is Z 6 \ [c(u )]∪{c(u )},
Let C 3 be a configuration of (G, H) on four vertices u, w, v and z such that the only edges of H are uw and vw and the edges in E(G) \ E(H) are uv and wz. Moreover, the total degree of w must be 7 (see Figure 4).

(ii) if u is a node, then d t (u) ≥ 8.
Proof. Let c be a colouring of (G , H ) = (G, H) \ {uw, uv}. Without loss of generality, we may assume that c(v) = 1 and c(z) / ∈ {2, 3}. Suppose for a contradiction that d t (G,H) (u) ≤ 6 or that u is a node and

d t (G,H) (u) = 7. If d t (G,H) (u) ≤ 6
, u has at least four available colours in c, otherwise u has three available colours which are consecutive. In both cases, we can assign to u a colour c(u) ∈ {2, 5, 6}. If c(u) ∈ {5, 6}, then setting c(w) = 3, we obtain a colouring of (G, H), a contradiction. If c(u) = 2, then choosing c(w) ∈ {4, 5} \ {c(z)}, we obtain a colouring of (G, H), a contradiction. Let C 4 be a configuration of (G, H) on eight vertices u, u , u , v, v , v , w and z such that the only edges of H are u u, uw, wv and vv and the only edges in E(G) \ E(H) are u u, uv, vv and wz. The vertices of Int(C 4 ) are u, w and v and they must have total degree equal to 8, 7 and 8, respectively (see Figure 5). This completes the proof of the claim.

(i) By contradiction, suppose that d t (u ) ≤ 7. Let c be a colouring of (G, H)-{u, v, w}. Since u is not coloured by c and u u ∈ E(H), vertex u has at least two available colours in c. Thus one can, if necessary, recolour u so that c(u ) = c(u ) + 3, contradicting the previous claim.

(ii) By contradiction, suppose that u u ∈ E(G -H) and u is a node, and d t (u ) ≤ 8. Let c be a colouring of (G, H) -{u, v, w} and t be the neighbour of u in H that is distinct from u. By definition, we have c(t ) / ∈ [c(u )] and by the previous claim, c(u ) = c(u ) + 3. Combining these facts, one deduces that c(u ) ∈ [c(t )]. Moreover, since d t (u ) ≤ 8, u has at most one neighbour in G -{u, u , t } that is already coloured by c. Therefore, since u is not yet coloured, u has at least two available colours in c. Hence, one can recolour u with a colour distinct from c(u ) + 3, contradicting to the above claim.

Proof of Theorem 8

The proof uses the Discharging Method. Recall that (G, H) is a minimal counter-example to Theorem 8 and that G is embedded in the plane. We first assign an initial weight to each vertex and face of G, and prove that the total initial weight is negative. We then apply some discharging rules that do not change the total weight. Finally, using the properties established in the previous section, we prove that the final weight of each vertex and face of G is nonnegative, which contradicts the negativity of the total weight. This implies that no such a counter-example exists and proves Theorem 8.

Initial weight

Let us define a function initial weights ϕ : V (G) ∪ F (G) → Z of the vertices and faces of G as follows:

• If v is an isolated vertex in H, i.e. d H (v) = 0, then ϕ(v) = 2d t (v) -6; • If v is a leaf in H, i.e. d H (v) = 1, then ϕ(v) = 2d t (v) -10; • If v is a node in H, i.e. d H (v) = 2, then ϕ(v) = 2d t (v) -14; • Every face f ∈ F (G) has weight ϕ(f ) = d(f ) -6.
Observe that the only faces with negative weight are the 3-faces for which the weight is -3, since G has no C 4 nor C 5 . Let Φ = v∈V ϕ(v) + f ∈F ϕ(f ) be the total initial weight. The following lemma shows that Φ is negative.

Lemma 30. The total initial weight Φ equals -12.

Proof. We have

Φ = v∈V (2d t (v) -14) + f ∈F (d(f ) -6) + 4 leaf(H) + 8 isol(H).
We shall use Euler's Formula, and the three following easy facts, whose proof is left to the reader.

v∈V d(v) = f ∈F d(f ) = 2|E(G)| (4) v∈V d t (v) = 2|E(G)| + 4|E(H)| (5) |E(H)| = |V (G)| -leaf(H)/2 -isol(H) (6)
By ( 4) and ( 5), we have

Φ = 6|E(G)| + 8|E(H)| -14|V (G)| -6|F (G)| + 4 leaf(H) + 8 isol(H) Then using (6), we get Φ = 6|E(G)| -6|F (G)| -6|V (G)|.
Finally, by Euler's Formula, we obtain Φ = -12.

Discharging rules

We now apply a set of discharging rules that we apply to convert ϕ into a final function of weights ϕ in such a way that no charge is lost, i.e. the total charge should be the same in ϕ .

• Rule 1: Each vertex sends one unit of charge to each of its incident 3-faces.

• Rule 2: Each q-face, for every q ≥ 6, sharing two consecutive backbone edges with a 3-face sends one unit of charge to the node of total degree 6 this 3-face, if it exists.

• Rules 3: For each of the configurations depicted in Figure 6, vertex s sends one unit of charge to vertex t, if ϕ(s) ≥ 4. • Rules 4: For each of the configurations depicted in Figure 7, vertex s sends one unit of charge to vertex t.

Lemma 31. Whenever one of the Rules 4 is applied, the vertex s has total degree at least 8.

Proof. The total degree of s is imposed to be 8 in Rules Lemma 32. By Rules 3 and 4, a node sends at most two units of charge and a leaf sends at most one unit of charge.

Proof. In Rules 3 and 4, a vertex s sends charge to a vertex a distance at most 2 in H. Moreover, each time its sends to a vertex t at distance 2 in H, then the common neighbour of s and t in H does not send nor receive any charge by Rules 3 or 4. Therefore, by Rules 3 and 4, a vertex sends at most 1 in each direction along its path in H.

Final weight

We now show that all vertices and all faces have a non-negative final weight. Recall that we denote by ϕ the final weight function after all applications of the previously described rules. Lemma 33. Every face f ∈ F (G) has a non-negative final weight.

Proof. If f is a 3-face, then ϕ(f ) = -3, and f receives 1 for each of its vertices by Rule 1. So ϕ (f ) = 0. If f is not a 3-face, then f has degree at least 6. So we have ϕ(f ) ≥ 0. However, we have to be sure that Rule 2, the only rule to change the weight of faces, cannot create a face with negative weight. Assume that f shares two backbone edges with k 3-faces T i , 1 ≤ i ≤ k. Recall that no two triangles share an edge, by Lemma 12. Thus, one can find a cycle C in G by replacing the two backbone edges in T i ∩ f (and their common endvertex) by the third edge of T i . The cycles obtained from f by taking k or k -1 of such shortcuts are cycles of length d(f ) -k and d(f ) -k + 1, respectively. Since G has no cycles of length 4 and 5, it follows that d(f

) -k ≥ 6. Hence ϕ (f ) = d(f ) -6 -k ≥ 0.
Lemma 34. If x is an isolated vertex, then ϕ (x) ≥ 0.

Proof. Assume x is an isolated vertex. Observe that the charge of x is ϕ(x) = 2d t (x) -6 ≥ d t (x), by Property 23. No isolated vertex is involved in Rules 2, 3 or 4, so x is concerned only by Rule 1. Since x is adjacent to at most d(x)/2 3-faces, by Property 22, we deduce that ϕ (x) ≥ d t (x) -d(x)/2 ≥ 0. Lemma 35. If x is a leaf, then ϕ (x) ≥ 0.

Proof. Assume x is a leaf. Then ϕ(x) = 2d t (x) -10. Vertex x sends at most one unit of charge by Rules 3 and 4, by Lemma 32. By Property 22, x is incident to at most d(x)/2 3-faces. Since d(x)/2 = d t (x)/2 -1, we have ϕ (x) ≥ 2d t (x) -10 -( d t (x)/2 -1) -1. Thus, if d t (x) ≥ 7 then ϕ (x) ≥ 0.

Suppose now that d t (x) < 7, so d t (x) = 6 by Property 23. We have ϕ(x) = 2, so x does not send charge by Rules 3. By Lemma 31, x does not send charge u'

x v u'' If x is incident to two 3-faces, then none of the Rules 4 applies. So x sends a charge of at most 2, and ϕ (x) ≥ ϕ(x) -2 ≥ 0.

Assume now that x is incident to exactly one 3-face. If x sends a charge of 0 or 1 by Rules 4, then ϕ (x) ≥ ϕ(x) -1 -1 ≥ 0. To complete the proof we shall now prove that x cannot send a charge of 2 by Rules 4.

Suppose by contradiction that it does. Then x is the vertex s for two configurations C and C isomorphic to some depicted Figure 7. Observe that C and C cannot be both isomorphic to the configurations depicted in Figures 7(b

  edges. We denote by G[S] the subgraph of G induced by S, by G\F the graph obtained from G by removing the edges in F from its edge set E(G), by G -S the graph G[V (G)\S], by (G, H)-S the graph pair (G-S, H -S), by (G, H)[S] the graph pair (G[S], H[S]) and by (G, H)\F the graph pair ((G\F ), (H\F )).

Figure 1 :

 1 Figure 1: The configurations C 0 (left) and C 0 (right).

Figure 2 :

 2 Figure 2: The configuration C 1 .

Figure 3 :

 3 Figure 3: The configurations C 2 (left) and C 2 (right).

  in the colouring c. Observe that Av(v) = {5, 6}, | Av(u)| ≥ 2 and Av(u) = Av(v), since u forbids three consecutive colours and c(u ) ∈ {2, 3}. Thus one can find c(u) ∈ Av(u) and c(v) ∈ Av(v) so that |c(u) -c(v)| 6 ≥ 2. • Case 3: c(u ) ∈ {4, 6}. Without loss of generality, we may assume that c(u ) = 2. Then, choose c(u) ∈ [2] \ [c(u )] and set c(v) = 5. • Case 4: c(u ) = 5. Without loss of generality, assume that c(u ) = 3. Then, one can choose c(u) ∈ [3] \ [c(u )] and set c(v) = 6.

Figure 4 : Configuration C 3

 43 Figure 4: Configuration C 3

Figure 5 : Configuration C 4

 54 Figure 5: Configuration C 4

4 Figure 6 :

 46 Figure 6: Rules 3. To send charge s must have initial weight at least 4.

5 Figure 7 :

 57 Figure 7: Rules 4. The dotted line means that the edge does not belong to E(G).

Figure 8 :-

 8 Figure 8: Configuration D

  ) or 7(d), because x is incident to one 3-face. Hence one of these two configurations, say C, is isomorphic to either C 0 , C 1 , C 2 , or C 2 , depicted in Figures7(a), 7(c) and 7(e). Let t be the vertex of C corresponding to t in Figure7. Observe that t is not an external vertex of C, because G has no cycle of length 4 or 5. Consider a colouring c of (G , H ) = (G, H) \ (Int(C) ∪ {x, t }). We haved t (G ,H ) (t ) ≤ d t (G,H) (t ) -3 ≤ 4.Hence the set A(t ) of available colours at t has size at least 2. Furthermore,d t (G ,H ) (x) ≤ d t (G,H) (x) -6 = 2,so the set A(x) of available colours at x has size at least 4. Hence there exist two distinct colours c 1 and c 2 of A(x) and two colours c 1 and c 2 in A(t ) (not necessarily distinct) such that c 1 / ∈ [c 1 ] and c 2 / ∈ [c 2 ]. Thus there exists two C-twin colourings at x. This contradicts Properties 25-(i), 26-(i), or 27-(i).

  by Lemmas 12 and 13. Combining these inequalities, we get Σ ≥ 4 -2 isol(H) ≥ 4 -2 comp(H), because isol(H) ≤ comp(H) for any graph H.

	Hence 4-2 comp(H) ≤ Σ ≤ -12-8 comp(H), which is contradiction because
	comp(H) is positive.

  4.2 and 4.4. It is at least 8 in Rules 4.1, 4.3, and 4.5 by Properties 24, 26, and 27, respectively.

Preprint submitted to Discrete Applied MathematicsDecember 8, 2015

show that all faces and vertices have non-negative final weight. Thus Φ ≥ 0. This contradicts Lemma 30 and completes the proof of the theorem.

Acknowledgment

The authors would like to thank A. Silva, F. Benevides and A. Cezar for several remarks that improved the writing of the proof presented in Section 3.

$ Supported by the CNRS-FUNCAP programme GAIATO between the team COATI of I3S and the team ParGO of the Federal University of Ceará.

by Rules 4. Moreover x is incident to at most two 3-faces. So we have ϕ (x) ≥ ϕ(x) -2 ≥ 0.

For nodes, we distinguish several cases according to their total degree. Lemma 36. Let x be a node. If d t (x) ≥ 9, then ϕ (x) ≥ 0.

Proof. Assume d t (x) ≥ 9. Then ϕ(x) = 2d t (x) -14 ≥ d t (x) -5. Now x gives at most 2 by Rules 3 and 4 by Lemma 32, and 1 to every 3-face. As x is incident to at most d(x)/2 = d t (x)/2 -2 3-faces (by Property 22), we have -If ϕ(v) ≥ 4, then x receives 1 from v by Rule 3.3. Hence ϕ (x) ≥ ϕ(x) -1 + 1 = 0.