Keywords: coloration dorsale, graphe planaire, forêt, NP-complet

Coloration dorsale (circulaire) : arbres dorsaux dans les graphes planaires Résumé : On considère un graphe G (non-orienté) et un sous-graphe H de G. Le nombre chromatique q-dorsal BBC q (G, H) est le plus petit entier k tel que G puisse être coloré proprement avec les couleurs {1, . . . , k} de telle sorte qu'en plus pour toute arête de H, les couleurs de ses deux extrémités diffèrent d'au moins q. Dans ce rapport, nous étudions le cas où G est planaire et H est une forêt. Nous donnons une série de résultats de NP-complétude ainsi que des bornes supérieures pour BBC q (G, H), suivant le type de forêt (couplage, galaxie, arbre couvrant). Nous abordons également une version circulaire du problème.

Introduction

All the graphs considered in this paper are simple. Let G = (V, E) be a graph, and let H = (V, E(H)) be a spanning subgraph of G, called the backbone. A k-colouring of G is a mapping f : V → {1, 2, . . . , k}. Let f be a k-colouring of G. It is a proper colouring if | f (u)f (v)| ≥ 1. 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 BBC q (G, H) is the smallest integer k for which there exists a q-backbone k-colouring of (G, H).

If f is a proper k-colouring of G, then g 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, this q-backbone colouring 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
If H is empty (i.e. E(H) = / 0), then BBC q (G, H) = χ(G). Hence for any k ≥ 3, deciding if BBC q (G, H) ≤ k is NP-complete because deciding if a graph is k-colourable is NP-complete (See [START_REF] Garey | A guide to the theory of NP-completeness[END_REF]). However, when we impose G or H to belong to certain graph classes, the problem sometimes become polynomial-time solvable. A trivial example is when we impose H to have chromatic number at least r > (k + q -1)/q. Then BBC q (G, H) ≥ rqq + 1, and so deciding if BBC(G, H) ≤ k can be done instantly by always returning 'no'. A less trivial example is when we impose H to have minimum degree 1. For such an H, deciding if BBC(G, H) ≤ q + 1 is also polynomial-time solvable, because BBC q (G, H) = q + 1 if and only if G is bipartite. This simple observation was already made by Broersma et al. [START_REF] Broersma | λ-backbone colorings along pairwise disjoint stars and matchings[END_REF] when H is a 1-factor (a spanning subgraph in which every vertex has degree exactly 1). Furthermore, if we also impose H to be connected, we show in Theorem 17 that deciding if BBC(G, H) ≤ q + 2 can be done in polynomial time. In contrast, if the condition of H being connected is removed, then it is NPcomplete (Theorem 18).

In this paper, we will focus on the particular case when G is a planar graph and H is a forest (i.e. an acyclic graph). Inequality [START_REF] Borodin | On the partition of a planar graph of girth 5 into an empty graph and an acyclic subgraph[END_REF] and the Four-Colour Theorem imply that for any planar graph G and spanning subgraph H, BBC(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 a planar graph and F a forest in G, then BBC 2 (G, F) ≤ 6.

If true Conjecture 1 would be best possible. Broersma et al. [START_REF] Broersma | Backbone colorings for graphs: tree and path backbones[END_REF] gave an example of a graph Ĝ with a forest F such that BBC 2 ( Ĝ, F) = 6. See Figure 1. It is then natural to ask how large BBC q (G, F) could be when G is Figure 1: A planar graph Ĝ with a forest F (bold edges) such that BBC q ( Ĝ, F) = q + 4. planar and F is a forest for larger values of q. We prove the following.

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

RR n°8152

In fact, we prove a more general result in Proposition 13 : for any pair (G, H) with H a subgraph of G, BBC q (G, H) ≤ (χ(G) + q -2)χ(H)q + 2.

For q ≥ 4, Theorem 2 is best possible. Indeed, we show a planar graph G * together with a spanning tree T * such that BBC q (G * , T * ) = q + 6 for all q ≥ 4. See Figure 2 and Proposition 15. Furthermore, we show in Theorem 32,

z 2 y 3 y 4 y 1 y 2 z 1
Figure 2: A planar graph G * and a tree T * (bold edges) such that BBC q (G * , T * ) = q + 6 for q ≥ 4.

that for any fixed q ≥ 4, given a planar graph G and a spanning tree T of G, it is NP-complete to decide if BBC q (G, T ) ≤ q + 5.

On the other hand, we believe that if q = 3, Theorem 2 is not best possible. A star is a tree in which a vertex v, called the center is adjacent to every other. A galaxy is a forest of stars. As evidence in support of Conjectures 1 and 3, Broersma et al. [START_REF] Broersma | λ-backbone colorings along pairwise disjoint stars and matchings[END_REF] showed that if F is a galaxy in a planar graph G, then BBC q (G, F) ≤ q + 4. This result is best possible even if F has maximum degree 3 as shown by the example of Figure 1. Furthermore, we show in Theorems 21 and 29 that, for any q ≥ 2, it is NP-complete to decide if BBC q (G, F) ≤ q + 3 given a planar graph G and a galaxy of maximum degree 3.

However, if the backbone is a matching, i.e. a galaxy with maximum degree 1, then fewer colours are needed. Indeed, Broersma et al. [START_REF] Broersma | λ-backbone colorings along pairwise disjoint stars and matchings[END_REF] showed that if M is a matching in a planar graph G, then for any q ≥ 3, BBC q (G, M) ≤ q + 3. They conjectured that the same holds for q = 2.

Conjecture 4 (Broersma et al. [START_REF] Broersma | λ-backbone colorings along pairwise disjoint stars and matchings[END_REF]). If G is a planar graph G and M a matching in G, then BBC 2 (G, M) ≤ 5.

It is natural to ask the same question for galaxies with maximum degree at least 2. When q = 2, we answer in the negative by showing that there are pairs of planar graphs and spanning forests of maximum degree 2 whose 2-backbone chromatic number is 6. Furthermore, we show that given a planar graph G and a spanning forest F of INRIA maximum degree 2, it is NP-complete to decide whether BBC 2 (G, F) ≤ 5 (Theorem 23). We also show that given a planar graph G with a hamiltonian path P, it is NP-complete to decide whether BBC 2 (G, F) ≤ 5. This result refines a result of Broersma et al. [START_REF] Broersma | Backbone colorings for networks[END_REF][START_REF] Broersma | Backbone colorings for graphs: tree and path backbones[END_REF] who proved it for a general graph G.

For q = 3, the problem remains open.

Problem 5. If G is a planar graph G and F a galaxy of maximum degree 2, is is true that BBC q (G, F) ≤ q + 3, for all q ≥ 3?

Broersma et al. [START_REF] Broersma | λ-backbone colorings along pairwise disjoint stars and matchings[END_REF] proved that deciding if BBC q (G, M) ≤ q + 2 for a given graph G and matching M is NPcomplete. We prove in Subection 2.2 that it remains NP-complete even if we impose G to be planar. In contrast, we prove that deciding if BBC q (G, T ) ≤ q + 2 for a given graph G and spanning tree T is polynomial-time solvable.

One can generalize the notion of backbone colouring by allowing a more complicated structure of the frequency space. The most natural one is to consider a circular metric. A circular k-colouring of G or Z k -colouring is a mapping f : V → Z k . The notions of circular q-backbone colouring and circular q-backbone chromatic number are defined similarly to those of q-backbone colouring and circular q-backbone chromatic number by replacing colouring by circular colouring. The circular q-backbone chromatic number of a graph pair (G, H) is denoted CBC q (G, H).

A circular q-backbone k-colouring is trivially a q-backbone k-colouring. On the other hand, a q-backbone k-colouring yields a circular q-backbone (k + q -1)-colouring. 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. (2)
Also,

q • χ(H) ≤ CBC(G, H) ≤ q • χ(G). (3)
Observe that if G is bipartite and H is non-empty, Equation (3) implies that CBC(G, H) = 2q. More generally, if χ(G) = H, then CBC(G, H) = q • χ(G). However if 2 ≤ χ(H) < χ(G), one can improve on the upper bound. We show in Proposition 33 that, for any pair (G, H) with H a subgraph of G,

CBC q (G, H) ≤ (χ(G) + q -2)χ(H). (4)
Since CBC(G, H) = χ(G) when H is empty and k-COLOURABILITY is NP-complete, for any fixed k ≥ 3, given a graph G and a subgraph H it is NP-complete to decide if CBC(G, H) ≤ k. But if insist that H is not empty, then CBC q (G, H) ≥ 2q by Proposition 3. Hence deciding if CBC q (G, H) is at most k with k ≤ 2q -1 can be done instantly by always returning 'no'. Less trivially, Proposition 36 shows that if H is a connected spanning subgraph of G, then CBC q (G, H) = 2q if and only if G is bipartite. Hence deciding deciding if CBC(G, H) = 2q can be done in polynomial time.

Inequality (4) implies that CBC q (G, F) ≤ 2q + 4 for any planar graph G and forest F in G. We believe that this upper bound can be reduced by at least one. Conjecture 6. If G is a planar graph and F a spanning forest of G, then CBC q (G, F) ≤ 2q + 3.

A natural question is to ask whether conjecture would be best possible. Problem 7. For any q ≥ 2, does there exist a planar graph G q and a spanning forest F q of G q such that CBC q (G q , F q ) = 2q + 3? Conjecture 6 holds if the backbone F is a galaxy. It follows directly from (2) and the fact that BBC q (G, F) ≤ q + 4 in such a case, as mentioned earlier. We believe however that one can use one colour less.

Conjecture 8. Let G be a planar graph and F a galaxy in G, then CBC q (G, F) ≤ 2q + 2.

If true, this conjecture would be tight, since the circular q-backbone chromatic number of a K 4 with backbone K 1,3 is 2q + 2. As evidence in support of this conjecture 6, Broersma et al. [START_REF] Broersma | λ-backbone colorings along pairwise disjoint stars and matchings[END_REF] deduced from the Four-Colour Theorem that if G is a planar graph and M a matching in G then CBC q (G, M) ≤ 2q + 2.

Broersma et al. also give an example of a planar graph G and a matching M such that (G, M) has no 2backbone Z 5 -colouring. We show in Theorems 37 and 41 that for any fixed k ∈ {4, 5}, it is NP-complete to decide if BBC 2 (G, M) ≤ k for given planar graph G and matching M. For larger values of q, the following questions are still open.

Problem 9. Let G be a planar graph and let M be a matching M in G. For any q ≥ 3, is it true that CBC q (G, M) ≤ 2q + 1 ?

Problem 10. Is it NP-complete to decide if CBC(G, F) ≤ 6 for a planar graph G and spanning forest F? Problem 11. For any g ≥ 5, is it NP-complete to decide if CBC(G, M) ≤ 4 for a planar graph G of girth at least g and matching M?

We prove in Theorem 34 that if G has girth at least 5, then CBC(G, M) ≤ 2q + 1. We wonder if the same holds for planar graph of girth 4.

Problem 12. Let G be a planar graph of girth 4 and let M be a matching in G. Is it true that CBC q (G, M) ≤ 2q+1 ?

2 Backbone colouring 2.1 About Conjectures 1 and 3 Proposition 13. Let G be a graph and let H be a subgraph of G. Then BBC q (G, H) ≤ (χ(G) + q -2)χ(H)q + 2.

Proof. Let g be a χ(G)-colouring of G and h a χ(H)-colouring of H. Let f be the colouring defined by:

f (v) = (h(v) -1)(q -2 + χ(G)) + g(v), if h(v) is odd, (h(v) -1)(q -2 + χ(G)) + χ(G) -g(v) if h(v) is even.
It is simple matter to check that f is a q-backbone ((χ(G) + q -2)χ(H)q + 2)-colouring of (G, H).

A parachute on v or a parachute with harness v is a complete graph on four vertices whose three edges incident to v are in the backbone. Proposition 14.

(i) For q ≥ 2, in a q-backbone (q + 3)-colouring of a parachute, the harness is coloured in {1, q + 3}.

(ii) For q ≥ 3, in a q-backbone (q+4)-colouring of a parachute, the harness is coloured in {1, 2, q+3, q+4}.

(iii) For q ≥ 4, in a q-backbone (q + 5)-colouring of a parachute, the harness is coloured in {1, 2, 3, q + 3, q + 4, q + 5}.

Proof. Let y be the harness.

(ii) If 3 ≤ φ(y) ≤ q + 2, then at most two colours can appear on its neighbours. Because those three vertices form a clique, they have three different colours and so φ(y) ∈ {1, 2, q + 3, q + 4}.

(iii) If 4 ≤ φ(y) ≤ q + 2, then at most two colours can appear on its neighbours. Because those three vertices form a clique, they have three different colours and so φ(y) ∈ {1, 2, 3, q + 3, q + 4, q + 5}.

Proposition 15. Let G * and T * be the graph and its spanning tree depicted Figure 2. For any q ≥ 4, BBC q (G * , T * ) ≥ q + 6.

INRIA

Proof. Assume for a contradiction that there is a q-backbone (q + 5)-colouring φ of (G * , T * ). By Proposition 14-(iii), the vertices y 1 , y 2 , y 3 , y 4 , z 1 , z 2 are coloured in {1, 2, 3, q + 3, q + 4, q + 5}. Without loss of generaltiy, we may assume that φ(y 2 ) ∈ {1, 2, 3}. But then φ(z 1 ) and φ(z 2 ) must be in {q + 3, q + 4, q + 5}, because y 2 z 1 and y 2 z 2 are in E(T * ). And φ(y 1 ), φ(y 2 ) and φ(y 3 ) are in {1, 2, 3} because y 3 z 1 and y 1 z 2 and y 4 z 2 are in E(T * ). But {y 1 , y 2 , y 3 , y 4 } is a clique in G * , so they must all get different colours, a contradiction. Proof. Assume that Conjecture 1 holds. Let G be a planar graph and F a forest in G. Then (G, F) admits a 2backbone 6-colouring φ. Let ψ be defined by

ψ(v) = φ(v) if φ(v) ∈ {1, 2}, ψ(v) = φ(v) + 1 if φ(v) ∈ {3, 4}, and ψ(v) = φ(v) + 2 if φ(v) ∈ {5, 6}. One easily check that ψ is a 3-backbone 8-colouring of (G, F).
2.2 q-backbone (q + 2)-colouring Theorem 17. Given a connected graph G and a spanning connected subgraph H, one can decide in polynomial time if BBC q (G, H) ≤ q + 2.

Proof. Observe first that if H is not bipartite, then BBC(H, H) = 2q + 1 by (1), and so BBC(G,

H) ≥ q + 3. So we first check if H is bipartite. If not, we return 'no'. If it is, we get a bipartition (A, B) of H.
Observe that if (G, H) has a q-backbone (q + 2)-colouring, then (free to rename A and B) all the vertices of A are coloured in {1, 2} and all the vertices of B in {q + 1, q + 2}, because H is connected. We then can transform our instance into an instance I(G, H) of 2SAT as follows. For each vertex v, we create a variable x v . Intuitively, for a vertex x ∈ A (resp. x ∈ B), the variable x v will be true if and only if v is coloured 1 (resp. q + 2) and false if and only if v is coloured 2 (resp. q + 1). Now for each edge uv, we create the following clauses.

• If u and v are both in A or both in B, we create the clauses x u ∨ x v and xu ∨ xv ;

• if u ∈ A and v ∈ B, we create the clause x u ∨ x v .
It is easy to check that (G, H) has a q-backbone (q + 2)-colouring if and only if I(G, H) is satisfiable.

Since 2SAT is well-known to be polynomial-time solvable, we can decide in polynomial time if BBC q (G, H) ≤ q + 2.

Theorem 18. For any q ≥ 2, the following problem is NP-complete problem. Input: A planar graph G and a 1-factor F of G. Question: BBC q (G, F) ≤ q + 2?

Proof. The problem is trivially in NP since a q + 2-backbone colouring of (G, F) is clearly a certificate.

Reduction from NOT-ALL-EQUAL 3SAT, which is defined as follows: Input: A set of clauses each having three literals. Question: Does there exists a suitable truth assignment, that is such that each clause has at least one true and at least one false literal?

This problem was shown NP-complete by Schaefer [START_REF] Schaefer | The complexity of satisfiability problems[END_REF].

Let C = {C 1 , . . . ,C n } be a collection of clauses of size three over a set U of variables. We will construct a graph pair (G, F) such that F is a 1-factor of G. Since V (F) = V (G), we only precise which edges are in E(F).

The following gadget will be useful. A forcing gadget at v or a forcing gadget with head v is the graph depicted Figure 3.

A key point in the reduction will be the following claim.

v 5 v v v 6 v 3 v 4 v 7 v 2 v 1
Figure 3: A forcing gadget with head v (left) and its symbol (right) (Edges of E(F) are in bold.)

Claim 19. In any q-backbone (q + 2)-colouring of a forcing gadget, its head is coloured in {1, q + 2}.

Proof. Consider a forcing gadget, whose vertices are named as in Figure 3, and φ a q-backbone (q + 2)-colouring of it. Since all the vertices are matched in F, there all must be coloured in {1, 2, q + 1, q + 2}. Assume for a contradiction that φ

(v) = 2. Then φ(v 1 ) = q + 2. Thus φ(v 2 ) ∈ {1, q + 1}. Now if φ(v 2 ) = q + 1, then necessarily φ(v 3 ) = 1.
Therefore, whatever the colouring may be, v 4 and v 5 are both adjacent to a vertex coloured 1. Hence {φ(v 4 ), φ(v 5 )} = {2, q + 2}. Therefore {φ(v 2 ), φ(v 3 )} = {1, q + 1}. But then v 6 cannot be coloured.

Similarly, we get a contradiction if φ(v) = q + 1.

For every variable u ∈ U, create a variable subgraph P u which is obtained from the path (a 1 (u), b 1 (u), a 2 (u), b 2 (u), . . . , a n (u), b n (u)) by adding a forcing gadget on each of its vertex.

For every clause C i = 1 ∨ 2 ∨ 3 , create a clause gadget D i as shown Figure 4. Then for each clause C i and each literal of C i , we add a path of length three (c i (l), c i (l), c i (l), a i (u)) if is the non-negated variable u, and (c i (l), c i (l), c i (l), b i (u)) if is the negated variable ū. We also add two forcing gadgets with heads c i (l) and c i (l).

c i ( 2 ) c i ( 1 ) d i ( 1 ) d i ( 3 ) c i ( 3 ) d i ( 2 )
It is easy to see that the resulting graph G may be drawn in the plane such that the crossed edges are those of type c i ( )c i ( ) for some literal . In particular, the two endvertices of a crossed edge are heads of forcing gadgets.

As long as there is a crossing C between two edges t(C)u(C) and v(C)w(C), we replace these two edges by the crossing gadget CG(C) depicted Figure 5, so that the only edges that are possibly crossed (if there were several crossings on tu or uv) are t(C)t (C), u(C)u (C), v(C)v (C) and w(C)w (C). After this process, there is no more crossing so the resulting graph G is planar. Let us now prove that (G, F) admits a q-backbone (q + 2)-colouring if and only if C has a suitable truth assignment.

INRIA u(C) t(C) v(C) w(C) u (C) d(C) a(C) c(C) b(C) v (C) w (C) t (C)
Assume first that (G, F) admits a q-backbone (q + 2)-colouring φ. Let u be a variable. Since there are heads of forcing gadgets, by Claim 19, all the a i (u) and b i (u) are coloured in {1, q + 2}. Moreover, since they form a path, all the a i (u) are coloured with the same colour and all the b i (u) are coloured with the other. Hence one can define the truth assignment ψ by ψ(u) = true if φ(a i (u)) = 1 for 1 ≤ i ≤ n, and

ψ(u) = f alse if φ(a i (u)) = q + 2 for 1 ≤ i ≤ n.
We shall prove that ψ is suitable.

Claim 20. For all crossing C in G , we have {φ(t(C)), φ(u(C))} = {1, q + 2} and {φ(v(C)), φ(w(C))} = {1, q + 2}.

Subproof. By induction on the reverse order of creation of the crossing gadget. By construction, t(C), u(C), v(C), w(C), t (C), u (C), v (C), and w (C) are heads of forcing gadgets. So they are coloured 1 or q + 2. Without loss of generality, we may assume that φ(t(C)) = 1.

If the edge t(C)t (C) was crossed and then replaced by a series of crossing gadget, by induction, φ(t (C)) = q + 2. It is also trivially the case if t(C)t (C) still exists. Hence {φ(a(C)), φ(b(C))} = {1, q + 1}.

Assume for a contradiction that φ(u(C)) = q + 2. Then, as above, {φ(c(C)), φ(d(C))} = {1, q + 1}. This is a contradiction, because a(C)c(C) and a(C)d(C) are edges. Hence φ(u(C)) = q + 2, and so φ(u

(C)) = 1 and {φ(c(C)), φ(d(C))} = {2, q + 2}.
In particular, one vertex of {a(C), b(C), c(C), d(C)} is coloured 1 and another is coloured q + 2. Now assume for a contradiction that {φ(v(C)), φ(w(C))} = {1, q + 2}. Then v(C) and w(C) are both coloured 1 or both coloured q + 2, and so v (C) and w (C) are both coloured q + 2 or both coloured 1, respectively. This is a contradiction, as all vertices of {a(C), b(C), c(C), d(C)} are adjacent to some vertex in {v (C), w (C)}. ♦

Let C i = 1 ∨ 2 ∨ 3 be clause. Claim 20 implies that for j ∈ {1, 2, 3}, φ(c i ( j )) = 1 if ψ(u) = f alse and φ(c i ( j )) = q + 2 if ψ(u) = true. Now the three c i ( j ), 1 ≤ j ≤ 3, cannot be all coloured 1 (resp. q + 2), for otherwise {φ(d i ( 2 )), φ(d i ( 3 ))} must be {2, q + 2} (resp. {1, q + 1}) and so d i ( 1 ) cannot be coloured, because it must be coloured in {1, q + 2} as head of a forcing gadget. Thus at least one of the c i (l j ) is coloured 1 and at least one is coloured q + 2, and so C i has at least one true and at least one false literal.

Hence ψ is suitable.

Reciprocally, assume that C has a suitable truth assignment ψ. For all u ∈ U and all 1 ≤ i ≤ n, let us define

φ(a i (u)) = 1 and φ(b i (u)) = q + 2 if ψ(u) = true, and φ(a i (u)) = q + 2 and φ(b i (u)) = 1 if ψ(u) = f alse. Similarly, for every literal , we set φ(c i ( )) = 1, φ(c i ( )) = q+2, φ(c i ( )) = 1, if is false, and φ(c i ( )) = q+2, φ(c i ( )) = 1, φ(c i ( )) = q + 2, if is true.
One can extend φ into a q-backbone (q + 2)-colouring of (G, F). Indeed, it is sufficient to show that we can extend it to forcing, clause and crossing gadgets.

If v is the head of a forcing gadget and φ

(v) = 1, we can set φ(v 1 ) = q + 2, φ(v 2 ) = q + 1, φ(v 3 ) = 1, φ(v 4 ) = q + 2, φ(v 5 ) = 2, φ(v 6 ) = 2,
and φ(v 7 ) = q + 2. Similarly, we can extend the colouring to the forcing gadget if φ(v) = q + 2.

Consider a clause gadget D i . Since C i has at least one true and at least one false literal, at least one vertex of c i ( 1 ), c i ( 2 ) c i ( 3 ) is coloured 1 and at least one is coloured q + 2. If c i ( 1 ) is coloured q + 2, and c i ( 2 ) and c i ( 2 ) are assigned 1, then we can set φ(d i ( 1 )) = 1, φ(d i ( 2 )) = 2, and φ(d i ( 3 )) = q + 2. If c i ( 1 ) and c i ( 2 ) are coloured 1, and c i ( 3 ) is assigned q + 2, then we can set φ(d i ( 1 )) = q + 2, φ(d i ( 2 )) = q + 1, and φ(d i ( 3 )) = 1.

Finally consider a crossing gadget such that {φ(t(C)), φ(u(C))} = {φ(v(C)), φ(w(C))} = {1, q + 2}. By symmetry, we may assume that φ(t(C)) = φ(v(C)) = 1 and φ(u(C)) = φ(w(C)) = q + 2. Then we can set φ(t Proof. We will denote the vertices of the no-3-gadget by their names in Figure 6. Assume for a contradiction that there is a 2-backbone 5-colouring φ of a no-3-gadget such that φ(x) = 3. The forcing gadget is the one depicted Figure 7.

(C)) = φ(v (C)) = q + 2, φ(u (C)) = φ(w (C)) = 2, φ(a(C)) = 1, φ(b(C) = q + 1, φ(c(C)) = q + 2,
Claim 25. In any 2-backbone 5-colouring of a forcing gadget, its head is coloured in {1, 5}.

Proof. Consider a forcing gadget, whose vertices are named as in Figure 3, and φ a 2-backbone 5-colouring of it.

Let us prove that φ(w) = 3 and so that φ(v) ∈ {1, 5}. Assume for a contradiction that φ(w) = 3. Without loss of generality, we may assume that φ(w) ∈ {1, 2}.

Observe that the vertices x, y, z, x , y , z are not assigned 3 because they are roofs of no-3-gadgets. If φ(w) = 1, then (φ(x), φ(y), φ(z)) and (φ(x ), φ(y ), φ(z )) is either (4, 2, 5) or (5, 2, 4). Hence the vertices x, x and z are all coloured in {4, 5}, which is impossible, since they form a triangle.

If φ(w) = 2, then (φ(x), φ(y), φ(z)) and (φ(x ), φ(y ), φ(z )) is either (4, 1, 5) or (5, 1, 4). Hence the vertices x, x and z are all coloured in {4, 5}, which is impossible, since they form a triangle.

To get the equivalence between the 3-colourability of the original graph H and the existence of a 2-backbone 5-colouring of (G, F), it remains to prove that for any α ∈ {1, 5}, there is a 2-backbone 5-colouring of the forcing gadget such that the head is coloured α.

We denote the vertices by their names in Observe that no vertex in {x, y, z, x , y , z } has been coloured 3. Hence, it remains to prove that for any β ∈ {1, 2, 4, 5}, there is a 2-backbone 5-colouring of the forcing gadget such that the head is coloured β. By symmetry, φ and 6φ, it suffices to prove that one exists for β ∈ {1, 2}. We denote the vertices by their names in Figure 6. Let us denote by β the colour of {1, 2} \ {β}.

φ(a) = 3, φ(b) = β, φ(c) = 5, φ(d) = 4, φ(e) = β, φ( f ) = β, φ(a ) = 3, φ(b ) = 5, φ(c ) = β, φ(d ) = 5, φ(e ) = β, φ( f ) = 3, φ(g) = 1, φ(h) = 5, φ(i) = 3.

Hamiltonian-path backbone

Theorem 26. The following problem is NP-complete problem. Input: A planar graph G with a hamiltonian path P. Question: BBC 2 (G, P) ≤ 5?

To prove this theorem, we shall use a reduction similar to the one of Theorem 21. However, we do not reduce directly from PLANAR 3-COLOURABILITY but use an intermediate problem whose NP-completeness is proven by reducing PLANAR 3-COLOURABILITY to it.

This intermediate problem is the following: TRACEABLE PLANAR 3-COLOURABILITY Input: A planar graph G with a hamiltonian path P. Question: Is G 3-colourable? Lemma 27. TRACEABLE PLANAR 3-COLOURABILITY is NP-complete.

Proof. Reduction from PLANAR 3-COLOURABILITY. Let H be a connected planar graph. We will construct a planar graph G having a hamiltonian path P such that χ(G) ≤ 3 if and only if χ(H) ≤ 3.

To do so, we shall construct a sequence of pairs andχ(G i ) ≤ 3 if and only if χ(H) ≤ 3. Then the path P := P V (H) will be a hamiltonian path of G := G V (H) and χ(G) ≤ 3 if and only if χ(H) ≤ 3.

(G i , P i ) for 1 ≤ i ≤ |V (H)| such that P i is a path in the planar connected graph G i , |V (P i )| = |V (G i )| -|V (H)| + i,
Let x be a vertex of H. We set G 1 := H and P 1 := (x). Trivially, (G 1 , P 1 ) verifies the above property. Assume now that i ≥ 1 and let us construct (G i+1 , P i+1 ) from (G i , P i ). Let P i = (v 1 , v 2 , . . . , v ) be a path. Since G i is connected, there exists j such that v j is adjacent to a vertex y in V (G i ) \ V (P i ). If j = 1, then let P i+1 := (y, v 1 , v 2 , . . . , v ), and G i+1 := G i ; if j = p, then let P i+1 := (v 1 , v 2 , . . . , v , y), and G i+1 := G i ; if y is also incident to v j+1 , let P i+1 := (v 1 , . . . , v j , y, v j+1 , . . . , v )). In those three cases, (G i+1 , P i+1 ) has trivially the desired property.

So we may assume that 1 < j < and y is not adjacent to v j+1 . Let y 1 , y 2 , . . . y r be the neighbours of v j in their order around it such that v j+1 = y r , y k = y and v j-1 = y q for q < r.

Let G i+1 be the graph obtained from G i as follows. For all 1 ≤ s ≤ k -1, remove the edge v j y s , add three vertices a s , b s , c s and the edges a s b s , b s c s , c s a s , v j a s , v j b s , b s y s ; Add the edges c s a s+1 for all 1 ≤ s ≤ k -2, and v j+1 a 1 . Finally add a vertex y and the edges yy and y c k-1 . Let P i+1 be the path obtained from P i by replacing the edge v j v j+1 by the subpath 8, which illustrates the construction when k = 5. Clearly, the number of vertices not covered by P i+1 in G i+1 is one less than the number of vertices not covered by

(v j , y, c k-1 , b k-1 , a k-1 , . . . , c 1 , b 1 , a 1 , v j+1 ). See Figure
y v j y 1 y 3 G i y = y 5 y 4 y 2 v j-1 v j+1 v j y 1 G i+1 y = y 5 y 4 y 3 b 3 c 1 c 2 b 2 a 2 b 1 a 1 b 4 a 3 c 3 a 4 c 4 y 2 v j-1 v j+1
P i in G i . So, since |V (P i )| = |V (G i )| -|V (H)| + i, we have |V (P i+1 )| = |V (G i+1 )| -|V (H)| + i + 1.
It remains to prove that G i+1 is 3-colourable if and only if G i is. Assume first that G i+1 admits a proper 3-colouring φ in {1, 2, 3}. We claim that it also induces a proper 3-colouring of G i . Indeed, without loss of generality, we may assume that φ(v j ) = 1 and φ(v j+1 ) = 2. Then for all 1 ≤ s ≤ s-1, φ(a s ) = 3 and φ(c s ) = 2, so φ(b s ) = 1. Hence φ(y s ) = 1. Therefore, for all 1 ≤ s ≤ s-1, φ(y s ) = φ(v j ). Since the v j y s , 1 ≤ s ≤ k -1, are the only edges of G i which are not in G i+1 , φ is a proper 3-colouring of G i .

Conversely, assume that G i admits a 3-colouring φ in {1, 2, 3}. It induces a partial proper 3-colouring of G, such that φ(v j ) = φ(y s ) for all 1 ≤ s ≤ k -1. Let us extend it. Without loss of generality, φ(v j ) = 1 and INRIA φ(v j+1 ) = 2. For all 1 ≤ s ≤ s -1, set φ(a s ) = 3, φ(b s ) = 1, and φ(c s ) = 2. Finally, colour y with the colour in {1, 2, 3} \ {φ(y), φ(c k-1 )}. This gives a proper 3-colouring of G i+1 .

Proof of Theorem 26. Reduction from TRACEABLE PLANAR 3-COLOURABILITY. Let (H, Q) be an instance of this problem. We shall construct a graph G and a hamiltonian path P of G such that BBC(G, P) ≤ 5 if and only if χ(H) ≤ 3. To do so we start from H and for each edge xy of Q, we will plug in an edge gadget E(xy) containing a hamiltonian path P(xy) from x to y. The union of all the P(xy), xy ∈ E(Q), will then be a hamiltonian path P of the resulting graph G.

To construct the edge gadget, we use an auxiliary forcing gadget depicted Proof. We denote the vertices by their names in Figure 9. Suppose for a contradiction that there is a 2-backbone 5-colouring φ such that φ(v) / ∈ {2, 4}. By the symmetry φ → 6φ, we may assume that φ(v) ∈ {1, 3}. If φ(v) = 3, then all the vertices a, b, c, d, e are coloured in {1, 2, 4, 5}. On the path (a, b, c, d, e), vertices coloured {1, 2} alternate with vertices coloured {4, 5}. Hence a, c, and e are all coloured in {1, 2}, or all coloured in {4, 5}, which is a contradiction as they form a clique.

If φ(v) = 1, then all the vertices a, b, c, d, e are coloured in {2, 3, 4, 5}. Now φ(b) is at distance 2 from the two distinct colours φ(a) and φ(c), hence φ(b) ∈ {2, 5}. Similarly, φ(d) ∈ {2, 5}. But φ(c) is at distance 2 from φ(b) and φ(d), so φ(b) = φ(d). Then the three vertices a, c, and e are all coloured in {2, 3, 4, 5} \ {φ(b) -1, φ(b), φ(b) + 1}, which has cardinality 2. This is a contradiction as those three vertices form a clique. Now the edge gadget is the one depicted Figure 10.

Let us now prove that BBC(G, P) ≤ 5 if and only if χ(H) ≤ 3.

Assume first that (G, P) admits a 2-backbone 5-colouring φ. Since H is a subgraph of G, φ induces a proper colouring on H. We shall prove that every vertex of H is coloured in {1, 3, 5}, thus proving that this proper colouring uses (at most) 3 colours.

Every vertex v of H is contained in an edge xy of Q, so it is contained in the edge gadget E(xy) in G. So it is adjacent to two vertices (namely v 1 and v 2 if v = x, and v 2 and v 3 if v = y), which are heads of forcing gadgets and adjacent. Hence by Claim 40, one of these vertices is coloured 2 and the other is coloured 4. Hence v must be coloured in {1, 3, 5}.

Let us now assume that H is 3-colourable. Then there exists a proper colouring φ of H with {1, 3, 5}. Let us now extend into a 2-backbone 5-colouring of (G, P). It is sufficient to prove that we can extend it to every edge-gadget.

Frédéric Havet , Andrew D. King , Mathieu Liedloff , Ioan Todinca ‡ a 1

x y To extend it the edge-gadget E(xy) (we use the names of Figure 10), set φ(v 1 ) = φ(v 3 ) = 2 and φ(v 2 ) = 4. Now, since for any pair (α, β) ∈ {1, 2, 3, 4, 5} 2 , there is a 2-backbone 5-colouring of the path of length 4 such that the first vertex is coloured α and the last vertex is coloured β, it suffices to prove that we can extend φ to the forcing gadget.

e 1 a 2 e 2 a 3 v 1 v 2 v 3 e 3
Consider such a forcing gagdet (with vertex names as in Figure 9). Then φ(v) ∈ {2, 4}. By the symmetry φ → 6φ, we may assume that φ(v) = 2. Then setting φ(a) = 4, φ(b) = φ(d) = 1, φ(c) = 3 and φ(e) = 5, we obtain the desired extension.

Hence, BBC(G, P) ≤ 5.

2.4 q-backbone (q + 3)-colouring for q ≥ 3 Theorem 29. For any q ≥ 3, the following problem is NP-complete problem. Input: A planar graph G and a galaxy F with maximum degree 3. Question: Is BBC q (G, F) ≤ q + 3?

Proof. Reduction from PLANAR 3-COLOURABILITY. We shall need the graph, which we call a kite, depicted Figure 11. The vertex named t on the figure is the tip of the kite, the one named u its corner.

Claim 30. If φ is a q-backbone (q + 3)-colouring of a kite such that φ(t) ∈ {1, 2, 3, q + 1, q + 2, q + 3}, then either φ(t) ∈ {1, 2, 3} and φ(u) = q + 3, or φ(t) ∈ {q + 1, q + 2, q + 3} and φ(u) = 1.

Proof. Observe that the vertices v, z 1 , z 2 , z 3 are harnesses of parachutes. This by Proposition 14-(i), they must be assigned 1 or q + 3.

Assume that φ(v) = 1, then φ(z 1 ) = φ(z 2 ) = φ(z 3 ) = q + 3. Thus {φ(s 1 ), φ(s 2 )} = {q + 1, q + 2} and so φ(u) = q + 3 and φ(t) ∈ {1, 2, 3}.

Similarly if φ(u) = q + 3, we obtain φ(u) = 1 and φ(t) ∈ {q + 1, q + 2, q + 3}.

Let H be a planar graph. Let (G, F) be the graph pair obtained from H as follows. Firstly, for each face f of H, we create a parachute P f with harness v f , and for each vertex x incident to f , we create a kite K f (x) with tip x and corner u f (x). We then link the vertex v f to all the u f (x). Secondly, for every vertex x ∈ V (H), we add a vertex y x and the edge xy x in the backbone.

Clearly, the resulting graph G is planar and the resulting backbone F is a galaxy with maximum degree 3. Let us now prove that BBC q (G, F) ≤ q + 3 if and only if H is 3-colourable. Assume first that (G, F) admits a q-backbone (q + 3)-colouring φ. Observe that each vertex x in V (H) is coloured in {1, 2, 3, q + 1, q + 2, q + 3}, because it is adjacent to y x in F.

Let x be a vertex in V (H). Free to consider q + 4φ, we may assume that φ(x) ∈ {1, 2, 3}. Consider a face f incident to x in H. By Claim 30, the kite K f (x) has its corner coloured q + 3. Together with Proposition 14-(i), this implies that φ(v f ) = 1. Thus, the corner of the kites in f cannot be coloured 1, therefore there are coloured q + 3 and so by Claim 30, all the vertices incident to f in H are all coloured in {1, 2, 3}. Applying this reasoning to each face of H, we obtain that all vertices of H are coloured in {1, 2, 3}. Hence, φ induces a proper 3-colouring on H.

Conversely, assume that H admits a proper 3-colouring c. One can extend into a q-backbone (q + 3)-colouring of (G, F) as follows. For every x ∈ V (H), we colour y x with q + 3; for every face f , we colour the vertex v f with 1 and the corners of the kites by q + 3. One can then extend the colouring to each kite (as in the proof of Claim 30) to obtain a q-backbone (q + 3)-colouring of (G, F).

The reduction above can be modified to have a spanning tree T for the backbone in place of the galaxy F. It suffices consider a spanning tree U of H and do the following: add a path of length two in the backbone along each edge of the tree U; for each kite, add tz 3 and vz 3 in the backbone and add paths of length two in the backbone along edges z 1 v and z 2 v. This will prove the following statement.

Theorem 31. The following problem is NP-complete problem. Input: A planar graph G and a spanning tree T of G. Question: Is BBC 2 (G, T ) ≤ 5?

2.5 q-backbone (q + 5)-colouring Theorem 32. For any q ≥ 4, the following problem is NP-complete problem. Input: A planar graph G and a spanning tree T of G.

Theorem 35 (Borodin and Glebov [START_REF] Borodin | On the partition of a planar graph of girth 5 into an empty graph and an acyclic subgraph[END_REF]). The vertex set of every planar graph of girth at least 5 can be partitioned into an independent set and a set which induces a forest.

Let (S, F) be a partition of V (G) such that S is stable and F induces a forest. Let us colour every vertex of S with 1. Now since F is a forest, it has an ordering v 1 , . . . , v p such that for every i, v i has at most one neighbour in {v 1 , . . . , v i-1 }. We colour the vertices of F according to this ordering as follows. If v i has no neighbour in {v 1 , . . . , v i-1 }, then colour it with q + 1. If v i has a neighbour u in {v 1 , . . . , v i-1 } and uv i / ∈ E(M), then colour it with a colour of {q + 1, q + 2} not assigned to u. If v i has a neighbour u in {v 1 , . . . , v i-1 } and uv i ∈ E(M), then assign 2q + 1 (resp. 2 to v i ) if u is coloured q + 1 (resp. q + 2). It is easy to check that the obtained colouring is a q-backbone Z 2q+1 -colouring of (G, M).

Circular q-backone 2q-colouring

Proposition 36. Let G be a graph and H a spanning connected subgraph of G. Then CBC q (G, H) = 2q if and only if G is bipartite.

Proof. If G is bipartite, then χ(G) = χ(H) = 2. Thus, by Equation 3, CBC q (G, H) = 2q.

Assume now that (G, H) admits a circular q-backbone 2q-colouring f . Let v be a vertex of G. Without loss of generality, we may assume that f (v) = 1. Then all the neighbours of v in H must be coloured q + 1. And so on, by induction, all the vertices at even distance from v in H are coloured 1 and all the vertices at odd distance from v in H are coloured q + 1. Since H is connected and spans G, it follows that all vertices are coloured 1 or q + 1, so G is bipartite.

Proposition 36 implies that given a graph G and a spanning connected subgraph H, deciding if CBC q (G, H) = 2q can be done in polynomial time. In contrast, if the condition of G be connected is removed, when q = 2, the problem becomes NP-complete, as shown by the following theorem.

Theorem 37. The following problem is NP-complete problem. Input: A planar graph G and a matching M in G. Question: Is CBC 2 (G, M) ≤ 4?

Proof. The problem is trivially in NP since a circular 2-backbone 4-colouring of (G, F) is clearly a certificate.

To prove it is NP-complete, we give a reduction from NOT-ALL-EQUAL 3SAT.

Let C = {C 1 , . . . ,C n } be a collection of clauses of size three over a set U of variables. We will construct a graph pair (G, M) such that M is a matching in G.

To do so we need some definitions and gadgets. Colours 1 and 3 are said to be twins and so do the colour 2 and 4. Trivially two vertices joined by an edge of M receives distinct twin colours. Two colours are siblings if they are equal or twins.

A link with ends u and v and central edge w 1 w 2 is a subgraph with vertex set {u, v, w 1 , w 2 } and edge set {uw 1 , uw 2 , vw 1 , vw 2 } with w 1 w 2 ∈ M. Two ends of a link are said to be linked.

Claim 38. In a circular 2-backbone 4-colouring c, the colours of the ends of a link are siblings.

Proof. The two vertices w 1 and w 2 are joined by an edge of M, so {c(w 1 ), c(w 2 )} ∈ {{1, 3}; {2, 4}}. Hence if u is coloured in {1, 3} (resp. {2, 4}), then {c(w 1 ), c(w 2 )} is {2, 4} (resp. {1, 3}), and so v is coloured in {1, 3} (resp. {2, 4}).

For each variable u ∈ U, we create a variable gadget G u which is obtained from the distinct vertices a u 1 , a u 2 , . . . , a u n by linking, from 1 ≤ i ≤ n -1, the vertices a u i and a u i+1 by an link with central edge b u i c u i . Claim 38 (and its proof) immediately implies the following.

(i) In any circular 2-backbone 5-colouring of (H 2 (x, y), M 2 (x, y)), vertices x and y receive colours which are cyclically 2 apart.

(ii) Any precoloring of x and y with colours that are cyclically 2 apart can be extended into a circular 2-backbone 5-colouring of (H 2 (x, y), M 2 (x, y)).

Let H be an instance of PLANAR C 5 -COLOURING. Replace each edge xy ∈ E(G) an edge gadget (H 2 (x, y), M 2 (x, y)) to obtain a planar graph G and a matching M (the union of the M 2 (x, y)). By Claim 42-(i), every circular 2-backbone 5-colouring of (G, M) induces a C 5 -colouring of H (the vertices of the C 5 are the colours (1, 3, 5, 2, 4)). Conversely, by Claim 42-(ii), any C 5 -colouring of H can be extended into a circular 2-backbone 5-colouring of (G, M). Hence H admits a C 5 -colouring if and only if (G, M) admits a circular 2-backbone 5-colouring.

Remark 43. Adding long paths along existing edges to transform the matching into a spanning tree, one derives that deciding if CBC(G, T ) ≤ 5, given a planar graph G and a spanning tree T of G, is NP-complete.

Further research

Campos et al. [START_REF] Campos | Backbone colouring: tree backbones with small diameter in planar graphs[END_REF] proved that if G is planar and T has diameter at most 3, then BBC 2 (G, T ) ≤ 5. Hence one can the find the 2-backbone chromatic number of such a pair in polynomial time. One can ask of the complexity for larger diameter. If G is a triangle-free planar graph, then, by Grötzsch's Theorem [START_REF] Grötzsch | Ein dreifarbensatz fr dreikreisfreie netze auf der kugel[END_REF], it is 3-colourable, and so BBC q (G, H) ≤ 2q + 1 and CBC(G, H) ≤ 3q for any subgraph H of G. Hence both Conjectures 1 and 6 for q = 2, when G is triangle-free. A natural first step would be to extend prove the two conjectures or at least improve on the above upper bounds for larger values of q.

Steinberg's Conjecture (1976) states that every planar graph without 4-and 5-cycles is 3-colourable. Towards this, Erdős (1991) proposed the following relaxation of Steinberg's Conjecture: Determine the smallest value of k, such that every planar graph without cycles of length from 4 to k is 3-colourable. The best known bound for such a k is 7 which was proved by Borodin, Glebov, Raspaud and Salavatipour [START_REF] Borodin | Planar graphs without cycles of length from 4 to 7 are 3-colorable[END_REF]. Hence, an evidence to both Conjecture 6 and Steinberg's Conjecture would be to prove the following: Conjecture 45. If G is a planar graph without 4-and 5-cycles and F a spanning forest of G, then CBC(G, F) ≤ 7.

Conjecture 3 .

 3 If G is a planar graph and F a forest in G, then BBC 3 (G, F) ≤ 8. If true, Conjecture 3 would be tight. The pair (G * , F * ) of Figure 2 satisfies BBC 3 (G * , F * ) = 8. We show in Proposition 16 that Conjecture 1 implies Conjecture 3.

Conjecture 3 is implied by Conjecture 1 .

 1 Proposition 16. Conjecture 1 implies Conjecture 3.

Figure 4 :

 4 Figure 4: The clause D i . (Edges of E(F) are in bold, forcing gadgets are represented by their symbols.)

Figure 5 :

 5 Figure 5: The crossing gadget CG(C). (Edges of E(F) are in bold, forcing gadgets are represented by their symbols.)

Figure 6 :

 6 Figure 6: The no-3-gadget with roof x and its symbol.

  Assume first that φ(a) ∈ {4, 5}, then φ(b) ∈ {1, 2} and {φ(a), φ(c)} = {4, 5}. Hence φ(d) ∈ {1, 2} and so {φ( f ), φ(c)} = {4, 5}. Therefore φ(e) = 3 and so φ(d) = 1. Similarly, if φ(a) ∈ {1, 2}, we obtain that φ(d) = 5. Hence, φ(d) ∈ {1, 5}. Similarly, φ(d ) ∈ {1, 5}. Free to consider 6φ instead of φ, we may assume that φ(d) = 1 and φ(d ) = 5. Thus φ( f ) = 2. Now φ(g) ∈ {3, 4}. If φ(g) = 3, then {φ(i), φ(h)} = {1, 5}, and if φ(g) = 4, then {φ(i), φ(h)} = {1, 2}. In both cases, one of h and i is coloured 1, which is impossible because φ(d) = 1.

Figure 3 .Figure 7 :

 37 Figure 7: The forcing gadget with head v. (Edges of E(F) are in bold, no-3-gadgets are represented by their symbols.)

Figure 8 :

 8 Figure 8: Constructing (G i+1 , P i+1 ) from (G i , P i ) (Egdes of the paths are in bold.)

Figure 9 .Figure 9 :

 99 Figure 9: The forcing gadget with head v and fringes a and e (left) and its symbol (right)

Figure 10 :

 10 Figure 10: The edge gadget E(xy) and its hamiltonian path P(xy) in bold (Forcing gadgets are represented by their symbols.)

INRIA

2 Figure 11 :

 211 Figure 11: The kite

Problem 44 .

 44 For a fixed d ≥ 4, what is the complexity of finding the 2-backbone chromatic number of (G, T ), when G is planar and T a spanning tree of diameter d ? Since deciding if the 2-backbone chromatic number of (G, T ) is at most k, for any fixed k ≤ 4 can be done in polynomial in polynomial time, if Conjecture 1 holds, Problem 44 is equivalent to finding the complexity of deciding if BBC 2 (G, T ) ≤ 5.

RR n°8152

Question: Is BBC q (G, F) ≤ q + 5?

Proof. Reduction from PLANAR 3-COLOURABILITY.

Let H be a planar graph. We shall construct a planar graph G together with a spanning tree T such that H is 3-colourable if and only if BBC q (G < T ) ≤ q + 5. Take U be a spanning tree of H.

We first construct a graph G from H by adding for every edge e = uv of U we add a vertex x e linked to u and v. We let T be the spanning tree of G induced by the new edges. The pair (G, T ) is then obtained from (G , T ) by adding a parachute on every vertex. Clearly G is planar as for each edge e = uv the path ux e v can be drawn along the edge uv.

Suppose that (G, T ) admits a q-backbone (q + 5)-colouring. Then by Proposition 14-(iii), every vertex in G is coloured in {1, 2, 3, q + 3, q + 4, q + 5}. Now that the vertices of H form one of the part of the bipartition of T . Hence, the colours of the vertices of H are either all in {1, 2, 3} or all in {q + 3, q + 3, q + 5}. In both cases, φ induces a proper 3-colouring on H.

Conversely, it is straightforward to extend a a proper 3-colouring of H into a q-backbone (q + 5)-colouring of (G, T ).

Circular backbone colouring

The following Proposition is an analogue to Proposition 13 and its proof is similar.

Proposition 33. Let G be a graph and let H be a subgraph of G such that 2 ≤ χ(H) < χ(G). Then CBC q (G, H) ≤ (χ(G) + q -2)χ(H).

Proof. Let g be a χ(G)-colouring of G and h a χ(H)-colouring of H.

Assume first that χ(H) is even. Let f be the colouring defined by:

One can easily check that f is a circular q-backbone ((χ(G) + q -2)χ(H))-colouring of (G, H).

Assume now that χ(H) is odd. Let f be the colouring defined by:

One can easily check that f is a circular q-backbone ((χ(G) + q -2)χ(H))-colouring of (G, H).

Planar graphs of girth at least 5

Theorem 34. Let G be a planar graph of girth at least 5 and M a matching in G. Then CBC q (G, M) ≤ 2q + 1.

Proof. Our proof is based on a structural result of Borodin and Glebov [START_REF] Borodin | On the partition of a planar graph of girth 5 into an empty graph and an acyclic subgraph[END_REF]. See also [START_REF] Kawarabayashi | Decomposing a planar graph of girth 5 into an independent set and a forest[END_REF].

INRIA

Claim 39. In a circular 2-backbone 4-colouring of G u , all the a i u are coloured with two sibling colours and all the b i u with the two other colours (which are also siblings).

For each clause

, we create a triangle z i 1 z i 2 z i 3 . Now for j = 1, 2, 3, if i j is the nonnegated literal u, we join z i j with a u i , and if i j is the negated literal ū, we join z i j with b u i . Such edges are said to be red. So far, the obtained graph H is not planar, but we can clearly draw it such that only red edges cross. We can now subdivide every red edge into a red path such that every edge is crossed at most once. We then replace the red edges which are not crossed by a link (with the same end) and two red edges uv and xy that cross each other by the crossing gadget depicted Figure 12. The resulting graph G is planar and it comes with a matching M. Proof. Consider first a circular 2-backbone 4-colouring of the forcing gadget. u is linked to u , which is linked to v , which in turn is linked to v. Hence, by Claim 38, the colours of u and v are siblings. Assume that x is coloured in {1, 3}, then x is also coloured in {1, 3}, say 1. The vertices a and b are assigned twin colours, so one is coloured 2 and the other 4. We now distinguish two cases depending on the colour of u .

1. Assume u is coloured 3. Then v must also be coloured 3. The vertices c and d are assigned twin colours, so one is coloured 2 and the other 4. Hence y is coloured 1.

2. Assume u is coloured in {2, 4}. Without loss of generality, we may assume it is coloured 2. Then a is coloured 4 and b is coloured 2, so v is coloured 4. Hence y is coloured in {1, 3}.

In both cases the colour of x and y are siblings, and so, by Claim 38, the colours of x and y are siblings.

For any 4-tuple {c u , c v , c x , c y } such that c u and c v are siblings and c x and c y are siblings, finding the desired circular 2-backbone 4-colouring is straightforward and left to the reader.

We shall now prove that C admits a suitable truth assignment if and only if CBC(G, M) ≤ 4.

Assume first that (G, M) admits a circular 2-backbone 4-colouring. Let φ be the truth assignment defined by φ(u) = true if all the a i u are coloured in {1, 3}, and φ(u) = f alse if all the a i u are coloured in {2, 4}. Note that is INRIA well defined by Claim 39. Now by Claims 38 and 40, for each clause C i = i 1 ∨ i 2 ∨ i 3 , the vertex z i j is coloured in {1, 3} if and only if the literal i j is true. But since z i 1 z i 2 z i 3 is a triangle, at least three colours must appear on these vertices, and so at least one from {1, 3} and at least one from {2, 4}. Hence, at least one of the literals of C i is true and at least one is false. Thus φ is suitable.

Reciprocally, assume that C admits a suitable truth assignment φ. If φ(u) = true, then colour all the a i u with 1, all the b i u with 2 and all the c i u with 4. And if φ(u) = f alse, then colour all the a i u with 2, all the b i u with 1 and all the c i u with 3. Now, for each clause C i = i 1 ∨ i 2 ∨ i 3 , some literal, say i 1 , is true and some literal, say i 3 , is false. Then assign 1 to z i 1 , 2 to z i 3 , and colour z i 2 with 3 if i 2 is true and 4 otherwise. By Claims 38 and 40, this partial colouring may be extended into a circular 2-backbone 4-colouring of (G, M).

Theorem 41. The following problem is NP-complete problem. Input: A planar graph G and a matching M in G. Question: Is CBC 2 (G, M) ≤ 5?

Proof. The reduction is from PLANAR C 5 -COLOURING which is defined as follows: Input: A planar graph G. Question: Does G have a homomorphism onto C 5 , the cycle of length 5? This was proved to be NP-complete by MacGillivray and Siggers [START_REF] Macgillivray | On the complexity of H-colouring planar graphs[END_REF].

To make the reduction we need an edge gagdet. This gadget is built from the planar graph H 1 (u, v) together with the matching M 1 (u, v) depicted in Figure 13.

The graph H 2 (x, y) is obtained from H 1 (x, y) by replacing the edge uw by H 1 (w, u). The matching M 2 (x, y) is then the union of M 1 (x, y) \ {uw} and M 1 (w, u). Observe that x and y are incident to no edges of M 2 (x, y). The pair (H 2 (x, y), M 2 (x, y)) is the edge gadget.

Broersma et al. [START_REF] Broersma | λ-backbone colorings along pairwise disjoint stars and matchings[END_REF] proved that in any circular 2-backbone 5-colouring of (H 1 (u, v), M 1 (u, v)), vertices u and v receive colours which are cyclically 2 apart. In addition, its straightforward to see that any precolouring of u and v with colours that are cyclically 2 apart can be extended into a circular 2-backbone 5-colouring of (H 1 (u, v), M 1 (u, v)). These two facts imply the following claim.

Claim 42.