Joergen Bang-Jensen

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

Anders Yeo
email: andersyeo@gmail.com

The complexity of finding arc-disjoint branching flows

Keywords: disjoint branchings, branching flow, polynomial algorithm, NP-complete

The concept of arc-disjoint flows in networks was recently introduced in [2]. This is a very general framework within which many well-known and important problems can be formulated. In particular, the existence of arc-disjoint branching flows, that is, flows which send one unit of flow from a given source s to all other vertices, generalizes the concept of arc-disjoint out-branchings (spanning out-trees) in a digraph. A pair of out-branchings B + s,1 , B + s,2 from a root s in a digraph D = (V, A) on n vertices corresponds to arc-disjoint branching flows x 1 , x 2 (the arcs carrying flow in x i are those used in B + s,i , i = 1, 2) in the network that we obtain from D by giving all arcs capacity n -1. It is then a natural question to ask how much we can lower the capacities on the arcs and still have, say, two arc-disjoint branching flows from the given root s. We prove that for every fixed integer k ≥ 2 it is • an NP-complete problem to decide whether a network N = (V, A, u) where u ij = k for every arc ij has two arc-disjoint branching flows rooted at s.

• a polynomial problem to decide whether a network N = (V, A, u) on n vertices and u ij = n-k for every arc ij has two arc-disjoint branching flows rooted at s.

The algorithm for the later result generalizes the polynomial algorithm, due to Lovász, for deciding whether a given input digraph has two arc-disjoint out-branchings rooted at a given vertex. Finally we prove that under the so-called Exponential Time Hypothesis (ETH), for every > 0 and for every k(n) with (log (n)) 1+ ≤ k(n) ≤ n 2 (and for every large i we have k(n) = i for some n) there is no polynomial algorithm for deciding whether a given digraph contains two arc-disjoint branching flows from the same root so that no arc carries flow larger than n -k(n).

De la complexité de trouver deux flots de branchement arc-disjoints

Résumé :

Le concept de flots arc-disjoints a été récemment introduit dans [START_REF] Bang-Jensen | Arc-)disjoint flows in networks[END_REF]. C'est un cadre très général à l'intérieur duquel peuvent se formuler beaucoup de problèmes célèbres et importants. En particulier, l'existence de flots de branchement arc-disjoints, c'est-à-dire, des flots qui envoient depuis une source s une unité de flot s vers tous les autres sommets, généralise le concept de branchements sortants arc-disjoints dans un digraphe. Une paire de branchements sortants B + s,1 , B + s,2 disjoint d'une racine s dans un digraphe D = (V, A) à n sommets correspond à des flots de branchement arc-disjoints x 1 , x 2 (les arcs portant le flot x i sont ceux de B + s,i , i = 1, 2) dans le réseau obtenu en donnant à tous les arcs de D une capacité de n -1. Il est alors naturel de se demander jusqu'où on peut diminuer les capacités des arcs tout en continuant à avoir deux flots de branchement arc-disjoints depuis la racine s. Nous prouvons que pout tout entier k ≥ 2 fixé

• il est NP-complet de décider si un réseau N = (V, A, u) avec u ij = k pour tout arc ij a deux flots de branchement arc-disjoints enracinés en s.

• on peut décider en temps polynomial si un réseau N = (V, A, u) à n sommets tel que u ij = n -k pour tout arc ij a deux flots de branchement arc-disjoints enracinés en s.

L'algorithme pour le dernier résultat généralise l'algorithme polynomial, du à Lovász, pour décider si un digraphe donné a deux branchements sortants arc-disjoints enracinés en un sommet donné. Enfin nous prouvons que sous l'hypothèse de complexité Exponential Time Hypothesis (ETH), pour tout > 0 et pour tout k(n) tel que (log (n)) 1+ ≤ k(n) ≤ n 2 , il n'y a pas d'algorithme polynomial pour décider si un digraphe donné contient deux flots de branchement arc-disjoints depuis le même sommet tels qu'aucun arc ne porte un flot supérieur à n -k(n).

Mots-clés : branchements disjoints, flot de branchement, algorithme polynomial, NP-complet

Introduction

Notation follows [START_REF] Bang-Jensen | Digraphs: Theory, Algorithms and Applications[END_REF]. We denote the vertex set and arc set of a digraph D by V (D) and A(D), respectively and write D = (V, A) where V = V (D) and A = A(D). Unless otherwise specified, the numbers n and m will always be used to denote the number of vertices, repectively arcs in the digraph in question. The digraphs may have parallel arcs but no loops. Paths and cycles are always directed unless otherwise specified. We will use the notation [k] for the set of integers {1, 2, . . . , k}.

An (s, t)-path in a digraph D is a directed path from the vertex s to the vertex t. The underlying graph of a digraph D, denoted U G(D), is obtained from D by suppressing the orientation of each arc. A digraph D is connected if U G(D) is a connected graph. When xy is an arc of D we say that x dominates y. For a digraph D = (V, A) the out-degree, d + D (x) (resp. the in-degree, d - D (x)) of a vertex x ∈ V is the number of arcs of the kind xy (resp. yx) in A, where we count parallel arcs. When X ⊆ V we shall also write d + X (v) to denote the number of arcs vx with x ∈ X.

An out-tree rooted at s, also called an s-out-tree, is a tree containing the vertex s in U G(D) such that every vertex v different from s has exactly one arc entering in the tree. Equivalently, s has a unique directed path to every other vertex of the tree using only arcs of the tree. An s-out-branching is a spanning s-out-tree. We use the notation T + s , B + s to denote an s-out-tree, respectively an s-out-branching.

Branchings in digraphs are important from a practical point of view and appear in many applications and hence it is relevant to consider quality measures for branchings. This has been done in a number of papers, see e.g. [START_REF] Daligault | FPT Algorithms and Kernels for the Directed k-Leaf Problem[END_REF][START_REF] Vergnas | Sur les arborescences dans un graphe orienté[END_REF][START_REF] Lokshtanov | On the directed degree-preserving spanning tree problem[END_REF][START_REF] Thomassé | Covering a strong digraph by α -1 disjoint paths: a proof of Las Vergnas' conjecture[END_REF]. An s-out-branching B + s is k-safe if no matter which out-neighbour v of s in B + s we consider, the s-out-tree T + s that we will obtain after deleting all the vertices of the out-tree T + v rooted at v in B + s contains at least k vertices (s and at least k -1 other vertices). In applications (where an s-out-branching is used to route information or similar from the root s) it is desirable to use an out-branching which is k-safe for a high value of k, because this means that no matter which arc we cut, s can still reach k other vertices using only arcs from the remaining s-out-tree.

In terms of protection against arc-faults, branchings are not a very good way of sending information from one source to all other vertices: If we insist that the vertex sets of the routes that we use to send the information from s to all other vertices may only intersect in a prefix of each route (this is equivalent to saying that the union of the routes is an s-out-branching), then the set of routes may be very vulnerable to arc-deletions. As an example consider the digraph H consisting of vertices s = v 1 , v 2 , . . . , v 2p+1 and arcs {sv 2 , sv 3 , v 2 v 3 } ∪ {v 3 v i |i ≥ 4}. This digraph contains no 3-safe s-out-branching. On the other hand, if instead we use each of the arcs sv 2 , sv 3 on p of the paths from s to V -s, then deletion of one of the arcs sv 2 , sv 3 disconnects s from only half of the other vertices. We may then ask what is the best way to route the information from s to all other vertices, while preserving a high degree of protection against arc-faults. This leads to the study of branching flows. Before we can formally define these, we need to recall a bit of flow theory.

A network N = (V, A, u) is a digraph D = (V, A) equipped with a non-negative capacity function u : A→R 0 on its arcs. A flow in N is any non-negative function x : A→R 0 which satisfies that x ij ≤ u ij for every ij ∈ A, where x ij , u ij denote, respectively, the flow value on ij and the capacity of ij. The balance-vector of a flow x is the function b x on V which to each vertex i ∈ V associates the value b x (i) = ij∈A x ij -pi∈A x pi .

If N = (V, A, u, b), that is, there is also a balance-vector specified for N , then a flow x is

feasible in N if it satisfies b x (v) = b(v) for all v ∈ V . Two flows x, y in a network N are arc-disjoint if x ij • y ij = 0 for every arc ij of N .
An important result in flow theory is the following which states that it is possible to decide in polynomial time whether or not there exists a feasible flow for a given network N = (V, A, u, b) (see e.g. [START_REF] Bang-Jensen | Digraphs: Theory, Algorithms and Applications[END_REF]Section 4.8]).

Theorem 1.1 For a given network N = (V, A, u, b) with arc-capacities given by u and vertexbalances prescribed by b one can check, using one max-flow calculation, whether there exists a feasible flow x in N .

A path flow along the path P (resp. cycle flow along the cycle C) in a network N is a flow x which has x ij = k for every arc on P (resp. C) for some positive value k and x ij = 0 for all arcs not on P (resp. C). An s-branching flow in a network N is a flow x in N with balance vector b x (v) = -1 for v = s and b x (s) = n-1, where n denotes the number of vertices in N .

The following folklore result (see e.g. [1, Section 3.5] or [START_REF] Bang-Jensen | Digraphs: Theory, Algorithms and Applications[END_REF]Section 4.3.1]) is very useful when working with flows.

Theorem 1.2 (Flow Decomposition Theorem) Every flow x in a network N on n vertices and m arcs is the arc-sum of at most n + m path and cycle flows. Furthermore, the path flows can be taken along paths P 1 , . . . , P q such that P i starts in a vertex s i with b x (s i ) > 0 and ends in a vertex t i with b x (t i ) < 0 for i ∈ [q]. In particular, if b x ≡ 0 there are no path flows in the decomposition and x is the arc-sum of at most m cycle flows. Given the flow x, a decomposition as above can be found in time O(nm).

Note that when we consider branching flows below, we are only interested in the acyclic part of such a flow, that is, the collection of paths from the root to all other vertices that we obtain by flow decomposition (we leave out flow along cycles since that does not contribute to the balance of the flow). By the Flow Decomposition Theorem, every branching flow x from s contains one or more out-branchings from s as a subdigraph (x sends one unit of flow from s to all other vertices).

As in the case of branchings, we may also measure the quality of an s-branching flow in terms of how vulnerable it is towards arc-deletions. If we have no restrictions on the flow values, a branching flow x may have flow equal to r ≤ n -1 on some arc out of s, corresponding to that arc belonging to r of the path flows whose arc sum forms the branching flow x. This means that if we keep only the arcs used by x and one arc fails (is deleted) then s may be unable to reach as many as r vertices after deleting that arc. In particular, if r = n -1, one arc failure can disconnect s from all other vertices in the chosen solution. Thus, from a practical point of view (say, in an application where branching flows are used to route information), it could be useful to restrict the maximum flow value in an arc to as small as possible. If follows from Theorem 1.1 that for every k, there is a polynomial algorithm to check whether a network N = (V, A, u ≡ k) has an s-branching flow from a given vertex s. Furthermore, also the min-cost version of this can be solved in polynomial time using any polynomial algorithm for minimum cost flows. These observations should be compared to the following result. Theorem 1.3 [START_REF] Bang-Jensen | Balanced branchings in digraphs[END_REF] The problem of deciding whether a digraph on n vertices has an (n -k)-safe out-branching is polynomial time solvable if k ≤ 2 and NP-complete for all k ≥ 3 (k is not part of the input).

Edmonds characterized digraphs with k arc-disjoint s-out branchings from a prescribed root s.

Theorem 1.4 (Edmonds' Branching Theorem) [START_REF] Edmonds | Edge-disjoint branchings[END_REF] A digraph D = (V, A) has k arc-disjoint s-out-branchings if and only if D has k arc-disjoint (s, v)-paths for every v ∈ V -s.

From Edmonds' Branching Theorem and the algorithmic proof of this due to Lovász [START_REF] Lovász | On two min-max theorems in graph theory[END_REF] (see also [START_REF] Bang-Jensen | Digraphs: Theory, Algorithms and Applications[END_REF]Section 9.3]), we obtain the following characterization of networks in which all capacities are equal to n -1 that have k arc-disjoint branching flows:

Theorem 1.5 A network N = (V, A, u ≡ |V |-1
) has k arc-disjoint s-branching flows x 1 , x 2 , . . . , x k if and only if there are k arc-disjoint (s, v)-paths in N for every v ∈ V \ {s}. Furthermore, there is a polynomial algorithm for constructing such flows x 1 , x 2 , . . . , x k when they exist.

The purpose of this paper is to study the complexity of the problem of deciding the existence of arc-disjoint branching flows in networks whose arc-capacities are bounded. We first show that when all capacities are bounded by a constant k, the problem becomes NP-complete as soon as k ≥ 2. The problem is trivial for k = 1 (see below).

In the second part of the paper we consider the case in which we still have uniform capacities, but now they are all n -k for some constant k. The case k = 1 is the same as asking for a pair of arc-disjoint s-out-branchings and hence polynomial by our remarks above. For k = 2 the problem is still fairly simple: we just need a pair of arc-disjoint s-out-branchings both of which are 2-safe and this can be checked in polynomial time. For larger values of k the problem becomes more complicated, but we use structural observations about branching flows in networks with high capacities (n -k for all arcs) to reduce the problem to that of checking the existence of a pair of arc-disjoint s-out-branchings for at least one digraph in a family of digraphs of polynomial size in n and k. Our method extends Lovász's algorithmic proof of Edmonds' Branching Theorem. The key idea is that, if the capacities are n -k and there is a branching flow from s in N then there exists one in which only vertices that are close to s will receive flow on more than one arc.

Finally we prove that under the so-called Exponential Time Hypothesis (ETH), for every > 0 and every k(n) with (log (n)) 1+ ≤ k(n) ≤ n 2 (and for every large i we have k(n) = i for some n) there is no polynomial algorithm for deciding whether a given digraph contains two arc-disjoint branching flows from the same root so that no arc carries flow larger than n -k(n).

Arc-disjoint branching flows in bounded capacity networks

Clearly a unit capacity network has two arc-disjoint branching flows from a given root s if and only if s has at least two arcs to every other vertex. So the first interesting case is arc-disjoint branching flows in networks with maximum capacity 2. Here the complexity of the uniform capacity case was open but if we allow some capacities to be only one it was shown in [START_REF] Bang-Jensen | Arc-)disjoint flows in networks[END_REF] that the problem is already NP-complete (note that the proof in [START_REF] Bang-Jensen | Arc-)disjoint flows in networks[END_REF] does not extend to a proof for the uniform capacity case).

Theorem 2.1 [START_REF] Bang-Jensen | Arc-)disjoint flows in networks[END_REF] It is NP-complete to decide whether a network N = (V, A, u), where u ij ∈ {1, 2} for all ij ∈ A, has two arc-disjoint s-branching flows.

Our first goal is to use Theorem 2.1 to prove that it is NP-complete to decide the existence of arc-disjoint branching flows from the same root in networks where all the capacities equal some fixed number k ≥ 2. This easily implies that it is also NP-complete to decide the existence of arc-disjoint branching flows from the same root in networks where all the capacities are at most k.

Inria

Theorem 2.2 For every fixed integer k ≥ 2, it is NP-complete to decide whether a network N = (V, A, u ≡ k) with special vertex s has two arc-disjoint s-branching flows.

Proof: We will reduce from the case when the capacity of each arc is either 1 or 2, which is NP-hard by Theorem 2.1. So let N = (V , A , u ) be a network, where u ij ∈ {1, 2} for all ij ∈ A . We will create a new network N = (V, A, u ≡ k) as follows.

For each arc ij ∈ A we do the following. Add k new vertices, y 1 ij , y 2 ij , . . . , y k ij and add two parallel arcs from s to y 1 ij and from y r ij to y r+1 ij for all r = 1, 2, . . . , k -1. Finally remove the arc ij and add the arcs iy

u ij ij and y k ij j.
Let N denote the network obtained after performing the above operation for all ij ∈ A and setting all capacities to k. Clearly N can be constructed in polynomial time given N = (V , A , u ). We will show that N has two arc-disjoint s-branching flows if and only if N has two arc-disjoint s-branching, which would complete the proof by Theorem 2.1.

First assume that there are two arc-disjoint branching flows, x 1 and x 2 , from s in N . For each ij ∈ A modify the flows as follows. Let a r,1 ij and a r,2 ij be the two parallel arcs from y r ij to y r+1 ij for r = 1, 2, . . . , k -1 and let a 0,1 ij and a 0,2 ij be the two parallel arcs from s to y 1 ij . Initially, for all r = 0, 1, . . . , k -1, add the arc a r,1 ij to x 1 with flow k -r and add the arc a r,2 ij to x 2 also with flow k -r. Also let the flow on iy u ij ij and y k ij j be zero in both branching flows. Now for each q = 1, 2, add an additional flow of x q ij to all the following arcs (which form a path).

iy u ij ij , a u ij ,q ij , a u ij +1,q ij , a u ij +2,q ij , . . . , a k-1,q ij , y k ij j
As x 1 and x 2 are arc-disjoint flows we note that x 1 ij = 0 or x 2 ij = 0 (or both). Therefore we have only added flow to the arcs iy u ij ij and y k ij j in at most one of x 1 and x 2 . This implies that even after the above operation the flows are arc-disjoint. Furthermore we note that no arc has received a flow of more than k, as if we add a flow of x q ij to an arc a r,q ij then r ≥ u ij , which implies that the flow in a r,q ij is at most k

-r + x q ij ≤ k -u ij + u ij ≤ k.
Furthermore the resulting flows are branching flows as, in each of them, the flow entering any vertex (except s) is one more than the flow leaving the vertex. Therefore after performing the above operation for all ij ∈ A we have obtained the desired branching flows in N .

Conversely assume that there are two arc-disjoint branching flows, x 1 and x 2 , from s in N . Without loss of generality assume that there is no directed cycle in x 1 or in x 2 (as we can easily remove such cycles by the Flow Decomposition Theorem). Consider some ij ∈ A . We will first show that we may assume that the flow from s to y 1 ij is k in both x 1 and in x 2 (each flow using a separate arc from s to y 1 ij ). Assume that this is not the case and without loss of generality the flow from s to y 1 ij is less than k in x 1 . As all parameters in the network are integer-valued we may assume that all flows are integer-valued. We must have at least one unit of flow on iy u ij ij in x 1 , as otherwise we cannot have a balance of -1 on all vertices y 1 ij , y 2 ij , . . . , y k ij . Therefore there exists a path P from s to i in x 1 with a flow of at least 1 on all arcs of P . If P uses the arc from s to y 1 ij or the arc y k ij j, then adding the arc iy u ij ij to P gives us a directed cycle, a contradiction. Now remove one unit of flow along all arcs of P and iy u ij ij and add one unit of flow to the arc sy 1 ij and if u ij = 2 then also add one unit of flow to the arc y 1 ij y 2 ij . The resulting flow is still a branching flow and no capacities are violated, but we have increased the flow from s to y 1 ij by 1. Continue this process until the flow from s to y 1 ij is k in both x 1 and in x 2 .

As the amount of flow entering the set {y 1 ij , y 2 ij , . . . , y k ij } has to be k larger than the amount of flow leaving the set in both x 1 and x 2 , we note that in x 1 the flow on iy u ij ij and on y k ij j is the same. Analogously in x 2 the flow is the same and the flow is zero for either x 1 or x 2 (or both). Assume without loss of generality that x 2 has no flow on iy u ij ij (and therefore also no flow on y k ij j). As the capacity on the arc y

u ij ij y u ij +1 ij
is k and there are k -u ij vertices in

{y u ij +1 ij , y u ij +2 ij , . . . , y k ij } we note that the arc y k ij j cannot have flow more than k -(k -u ij ) = u ij . So removing all vertices y 1 ij , y 2 ij , .
. . , y k ij and all arcs touching these vertices, but adding back the arc ij with flow the same as we had in iy u ij ij (and also in y k ij j) gives us two arc-disjoint branching flows where the flow on ij is bounded by u ij . Therefore doing the above process for all ij ∈ A gives us the desired branching flows in N .

Arc-disjoint k-safe branchings

Recall that n denotes the number of vertices of the digraph in question. In the next section we will consider branching flows in networks where the capacities are n -k for some constant k. To study these, it turns out that it is relevant to study the problem of finding arc-disjoint k-safe sout-branchings in digraphs with n vertices for some given constant k. When k = 2 the connection is straightforward as every s-branching flow in N = (V, A, u) with u ≡ n -2 corresponds to a 2-safe branching (at least two children at the root). Hence there are arc-disjoint s-branching flows x 1 , x 2 from s in N if and only if the network contains two arc-disjoint branchings, each of which uses at least two arcs from the root and such branchings are 2-safe. For higher values of k we can make use of Theorem 3.1 which also plays an important role in the next section.

The following consequence of the so-called strong version of Edmonds' Branching Theorem (see e.g. [START_REF] Schrijver | Combinatorial optimization. Polyhedra and efficiency[END_REF]Theorem 53.1]) will be useful in our search for arc-disjoint k-safe branchings. We include the proof for completeness.

By Edmonds' Branching Theorem, there are two arc-disjoint s-out-branchings if and only if we have

d -(X) ≥ 2 for all X ⊆ V -s (1)
Theorem 3.1 Let D be a digraph with two arc-disjoint s-out-trees T + s,1 , T + s,2 . Then D contains two s-out-branchings B + s,1 , B + s,2 such that A(T + s,i ) is contained in A(B + s,i ) for i = 1, 2 if

and only if (1) holds and D -A(T +

s,i ) has an out-branching (in which case it has one which contains all the arcs of T + s,3-i ) for i = 1, 2. Furthermore, such branchings can be found in polynomial time when they exist.

Proof: The two conditions above are clearly necessary and can be checked in polynomial time, so assume that they are both satisfied. We will show how to modify the algorithmic proof of Edmonds' Branching Theorem by Lovász, for the case of two branchings (see e.g. [START_REF] Bang-Jensen | Digraphs: Theory, Algorithms and Applications[END_REF]Section 9.3] or [START_REF] Schrijver | Combinatorial optimization. Polyhedra and efficiency[END_REF]Section 53.1]) so that we achieve two arc-disjoint branchings

B + s,1 , B + s,2 with A(T + s,i ) ⊆ A(B + s,i ) for i = 1, 2.
We give the full proof as it is not very long and also makes it easy to check that there is a polynomial algorithm for constructing the desired branchings.

First we delete all arcs of T + s,2 , call the resulting digraph D and start the algorithm from the out-tree

T + s = T + s,1 in D . We say that a set X ⊆ V -V (T + s,2 ) is dangerous if it has in-degree 1 in D -A(T + s )
, where T + s is the current out-tree (containing T + s,1 ) which has been constructed

Inria so far by the algorithm. By submodularity of the in-degree function, if X, Y are both dangerous and they intersect, then so are X ∪ Y and X ∩ Y . Also, since D satisfies (1), every dangerous set must intersect V (T + s ).

We have two possible scenarios when trying to extend T + s . Note that, by our assumption, as long as V -V (T + s ) = ∅ there is at least one arc from V (T + s ) to V -V (T + s ): (a) Every dangerous set (possibly there are none) is contained in V (T + s ). (b) Some dangerous set intersects both V (T + s ) and V -V (T + s ). If (a) holds, then we can take any arc uv ∈ A(D ) with u ∈ V (T + s ) and add uv to T + s and continue. If (b) holds, then (as in the original proof by Lovász) let X be an inclusionwise minimal dangerous set intersecting both V (T + s ) and V -V (T + s ). It is easy to check that there is some arc uv ∈ A(D ) with u ∈ V (T + s ) ∩ X and v ∈ X -V (T + s ): Suppose not, then every arc which enters X -V (T + s ) also enters X and we would have

d - D (X -V (T + s )) = d - D (X -V (T + s )) = d - D -A(T + s ) (X -V (T + s )) ≤ d - D -A(T + s ) (X) = 1, contradicting (1). So there is an arc uv ∈ A(D ) with u ∈ V (T + s ) ∩ X and v ∈ X -V (T + s )
. This arc cannot enter a dangerous set since (by the remark above on intersecting dangerous sets) that would contradict the minimality of X. Hence we may extend T + s by adding uv and continue the algorithm until T + s is spanning. At that point, since every set not intersecting V (T + s,2 ) has in-degree at least one in D -A(T + s ), we can extend T + s,2 to a branching arc-disjoint from the first one and the proof is complete. Proof: By Theorem 3.1 it suffices to show that we can find two arc-disjoint out-trees T + s,1 , T + s,2 , each of which have out-degree 2 at s, such that there are arc-disjoint branchings extending each of these.

Call a set

X ⊆ V \ {s} tight if d -(X) = 2.
If X, Y ⊆ V \ {s} are distinct tight sets both containing two out-neighbours of s, then they cannot share exactly one out-neighbour of s: Suppose p, q, r are all out-neighbours of s such that X ∩{p, q, r} = {p, q} and Y ∩{p, q, r} = {q, r}. Then it follows from (1) the submodularity of the in-degree function that we have

2 + 2 = d -(X) + d -(Y ) ≥ d -(X ∪ Y ) + d -(X ∩ Y ) ≥ 3 + 2, (2)
a contradiction. It follows from the observation above and the fact that d + (s) ≥ 4 that we can find four out-neighbours p, q, r, t of s such that there is no tight set containing both p, q and no tight set containing both r, t. This is clear if there are no tight sets containing two neighbours of s and otherwise let X be a tight set containing two neighbours a, b of s. By the claim there is no tight set containing a but not b and conversely so the claim follows. Now let T + s,1 be the out-tree formed by the two arcs sp, sq and T + s,2 be the out-tree formed by the arcs sr, st and apply the algorithm of Theorem 3.1.

See [START_REF] Bang-Jensen | Balanced branchings in digraphs[END_REF] for a more results related to Corollary 3.2. Theorem 3.1 can be generalized to extensions of p arc-disjoint s-out-trees. In [?] Szegö attributes the following result to Frank. Theorem 3.3 Let D = (V, A) be a digraph and let T + s,1 , . . . , T + s,p be arc-disjoint s-out-trees in D. There exists arc-disjoint s-out-branchings B + s,1 , . . . , B + s,p in D such that

A(T + s,i ) ⊆ A(B + s,i ) for i ∈ [p] if and only if d - D (X) ≥ q(X) for all X ⊆ V, ( 3
)
where D is the digraph obtained from D by deleting all arcs of T + s,1 , . . . , T + s,p and q(X) denotes the number of s-out-trees among T + s,1 , . . . , T + s,p which do not intersect X.

The proof of a generalization of this result can be found in [?]. This proof, which is a direct generalization of the proof we used for Theorem 3.1, can be turned into a polynomial algorithm which either constructs the desired s-out-branchings or finds a set X violating (3) above.

Theorem 3.4 For every pair of fixed positive integer k, p, there exists a polynomial algorithm for checking whether a given input digraph D has p arc-disjoint k-safe s-out-branchings. Furthermore, such branchings can be found in polynomial time when they exist.

Proof: Observe that an s-out-branching is k-safe if and only if it contains an s-out-tree with at most 2k -1 vertices which is itself k-safe. Let B be the set of all k-safe s-out-trees from s on at most 2k -1 vertices. As k is a constant, this set can be constructed in polynomial time O(|V (D)| 2k-1 ). Now, by Theorem 3.3, it suffices to check, using the algorithmic version of the theorem for (at most) all possible collections of p arc-disjoint out-trees T + s,1 . . . , T + s,p ∈ B whether the current collection can be extended to p arc-disjoint s-out-branchings and return the branchings constructed if some iteration is successful. If no set of p arc-disjoint out-trees T + s,1 . . . , T + s,p ∈ B can be extended, then D has no set of p arc-disjoint k-safe out-branchings from s.

Arc-disjoint branching flows, the case of high capacities

We now study the complexity of finding arc-disjoint branching flows in networks where every arc has capacity n -k for some constant k. If x is an s-branching flow in D = (V, A), then let D x = (V, A x ) be the subdigraph of D with vertex set V and arc set A x = {a ∈ A | x(a) > 0}. Thus D x only contains the arcs with non-zero flow in x.

Growing and trimming a branching flow

Definition 4.1 Let D = (V, A) be a digraph of order n, let s ∈ V (D) be given, and let k be an integer. An (s, k)-branching flow, is a branching flow x from s in D, such that x(e) ≤ n -k for all arcs 1 e ∈ A. Note that x is also an (s, k)-branching flow in D x .

(s, k)-branching flows have the the nice property that an (s, k)-branching flow of an induced subdigraph of D (containing s) can be extended to an (s, k)-branching flow of D provided that every vertex of D is reachable from s. This extra condition is not too demanding because it is a trivial necessary condition for a digraph to have an (s, k)-branching flow. Proof: Since one can reach all vertices of D, there is an ordering v 1 , . . . , v p of the vertices of V (D) \ X such that for all 1 ≤ i ≤ p, there is an (s, v i )-path

P i in D i := D[X ∪ {v 1 , . . . , v i }].
Assume that D 0 = D[X] contains an (s, k)-branching flow x 0 . Let us prove by induction on i that D i contains an (s, k)-branching flow x i for all 0 ≤ i ≤ p.

Suppose now that i ≥ 1. By the induction hypothesis, D i-1 contains an (s, k)-branching flow x i-1 in D i-1 . Let x i be the flow obtained from x i-1 by adding one unit of flow on all arcs in P i . Clearly, x i is an (s, k)-branching flow in D i .

Hence x p is an (s, k)-branching flow in D p = D. Consider a digraph D and a vertex s from which all vertices of D are reachable. By Lemma 4.2, if D has an (s, k)-core, then it contains an (s, k)-branching flow. We shall now prove that this easy sufficient condition is also necessary (provided that D has order at least 2k). In order to prove this theorem, we need two lemmas. If there is no feasible s-branching flow in N , then there exists a set X ⊆ V , such that s ∈ X, |X| = k, there is only one arc, e, out of X in D x and e ∈ A .

Proof: Let N be the network defined as in the statement of the lemma and let N k be the same as N , except all capacities are n -k. In both N and N k add a vertex t and an arc from all vertices in V (D) \ {s} to t of capacity 1 and let the resulting networks be called N t and N t k , respectively. By the assumption of the lemma, there exists an (s, t)-flow in N t k of value n -1, but there does not exist an (s, t)-flow in N t of value n -1. Let (X, V ∪ {t} \ X) be a minimum (s, t)cut in N t , which, by the Max-Flow Min-Cut Theorem (see e.g. [3, Theorem 4.5.3]), has capacity less than n -1. Recall that, by definition of an (s, t)-cut, s ∈ X. Thus by the existence of x, the cut (X, V ∪ {t} \ X) has capacity at least n -1 in N k . Therefore some arc of A must leave X, as otherwise the cut would have the same capacity in N t and N t k . We must have d + Dx (X) ≤ 1 as otherwise the capacity of the cut in N t would be at least 2(n -k -1) > n -2, a contradiction. Therefore there is exactly one arc, e, out of X in D x and we have e ∈ A . Finally if |X| < k then the capacity of (X, V ∪ {t} \ X) in N t k would be at most (|X| -1) + n -k < n -1, a contradiction, and if |X| > k then the capacity of (X, V ∪ {t} \ X) in N t would be (|X| -1) + n -k -1 > n -2, a contradiction. Therefore |X| = k, completing the proof. If Y is a critical set in D, then let e be the arc out of Y in D and let A = A(D) \ {e} and if no critical set exists in D then let A = A(D). By Lemma 4.5, we note that there exists an (s, k)-branchng flow y in D with y(e ) ≤ n -k -1 for all e ∈ A . Now, without loss of generality, we may assume that D = D y (that is, every arc in D has non-zero flow). We may also assume that D is acyclic, as if there exists a cycle in D then we can reduce the flow along this cycle until one of the arcs gets flow zero and therefore disappears from D y .

Let P be a longest path in D starting at s, such that if some arc has flow n -k in y, then this arc belongs to P . Let v be the last vertex on this path. We must have d + D (v) = 0 as otherwise there either exists a cycle in D or the path P wasn't longest possible. Let D = D-v and consider the flow y in D obtained from y by reducing the flow of each arc on P by one. By construction, no arc e ∈ A(D ) has y (e ) = n -k, which implies that y (e ) ≤ n -k -1 = |V (D )| -k for all e ∈ A(D ). It is now not difficult to see that y is an (s, k)-branching flow in D -v, which completes the proof.

Proof of Theorem 4.4:

We already proved that having an (s, k)-core is a sufficient condition for D to contain an (s, k)-branching flow, because all vertices are reachable from s.

Let us now prove that it is a necessary condition. Assume that D contains an (s, k)-branching flow. We repeatedly apply Lemma 4.6 and remove vertices from D, until we are left with D 2k of order 2k which contains an (s, k)-branching flow. Then V (D 2k ) is an (s, k)-core.

A polynomial algorithm for the case of capacities n minus a constant

We are now ready to apply the results developed in the previous subsection to obtain the desired algorithm.

Theorem 4.7 For every fixed natural number k there exists a polynomial algorithm for deciding whether a given input digraph D, with a prescribed vertex s contains two arc-disjoint (s, k)branching flows.

Proof: Let the digraph D = (V, A) on n vertices and the special vertex s be given. We may assume that n > 2k since otherwise the size of D is constant and we can solve the problem by a brute force method.

Inria

As the arc-set of every branching flow from s contains an s-out-branching, we first check whether D satisfies (1) and stop if this is not the case. Hence we assume below that D satisfies [START_REF] Ahuja | Network flows[END_REF]. Now for every choice of two sets, X, Y ⊆ V , such that |X| = |Y | = 2k, and s ∈ X ∩ Y , we will check whether they are (s, k)-cores in two arc-disjoint digraphs D X and D Y in which every vertex is reachable from s. We proceed as follows. For every subset of arcs A X ∈ D[X] and

A Y ∈ D[Y ], let D X core = (X, A X ) and D Y core = (Y, A Y )
and check if the following hold.

(i):

A X ∩ A Y = ∅.
(ii): There exists an (s, k)-branching flow in D X core and an (s, k)-branching flow in D Y core .

(iii): We can partition A(D) \ (A X ∪ A Y ) into A and A , such that there exists an s-outbranching in

D X = (V (D), A X ∪ A ) and also in D Y = (V (D), A Y ∪ A ).
Clearly, X and Y are (s, k)-cores in two arc-disjoint digraphs D X and D Y in which every vertex is reachable from s if and only if (i)-(iii) are possible. Hence, by Theorem 4.4, our algorithm is correct.

Let us now analyse its complexity. Part (i) can be checked in time O(n + m) and part (ii) can be checked in O(k 3 ) time, using a max-flow algorithm. Now let us show how to check part (iii) given that (i) and (ii) passed. Fix arbitrary spanning s-out-trees T + s,X , T + s,Y in D X core , D Y core respectively and let D * be the spanning subdigraph that we obtain from D by deleting the arcs in

(A X \ A(T + s,X )) ∪ (A Y \ A(T + s,Y )). We claim that (iii) holds if and only D * contains a pair of arc-disjoint s-out-branchings B + s,X , B + s,Y such that A(T + s,X ) ⊂ A(B + s,X ) and A(T + s,Y ) ⊂ A(B + s,Y
). This follows from the fact that every s-out-branching B + s in D X = (V (D), A X ∪ A ) can be converted to an s-out-branching B + s,X such that A(T + s,X ) ⊂ A(B + s,X ) by replacing the arcs of B + s that enters a vertex in X by A(T + s,X ). The same applies to every s-out-branching B + s in D Y = (V (D), A Y ∪ A ) and A(T + s,Y ). Now it follows from Theorem 3.1 that all we need to do is to check that D * contains a pair of arc-disjoint s-out-branchings and then check that D * -A X contains an s-out-branching and D * -A Y contains an s-out-branching. For a fixed choice of A X , A Y all of this can be done in time O(n 3 ) (the time to check that (1) holds).

Note that there are less than n 2k choices for choosing X and less than n 2k choices for choosing Y . As |A(X)|, |A(Y )| < 2k 2 we note that there are less than 2 (2k 2 ) options for choosing A X and analogously for choosing A Y . Therefore there are less than n 4k × 2 (4k 2 ) options for choosing X, Y , A X and A Y , which is a polynomial when k is a constant. Therefore the algorithm runs in polynomial time.

It is not difficult to see that using the algorithmic version Theorem 3.3 we obtain the following. Theorem 4.8 For every pair of fixed natural numbers k, p there exists a polynomial algorithm for deciding whether a given input digraph D, with a prescribed vertex s contains p arc-disjoint (s, k)-branching flows.

Modifying the first part of the proof of Theorem 3.4 we can even generalize as follows. We leave the easy details to the interested reader. Theorem 4.9 For every fixed natural number p and every collection of fixed natural numbers k 1 , . . . , k p there exists a polynomial algorithm for deciding whether a given input digraph D, with a prescribed vertex s contains p arc-disjoint branching flows x 1 , . . . , x p such that x i is an (s, k i )-branching flow.

s X 1 x1 x1 W 1 w 1 1 w 2 1 X 2 x2 x2 W 2 w 1 2 w 2 2 X 3 x3 x3 W 3 w 1 3 w 2 3 X 4 x4 x4 • • • X x x t Q c 1 c 2 c 3 • • • c m Figure 1: The digraph D, where C 1 = (v 1 ∨ v 2 ∨ v4 )
5 The case of capacities n -f (n)

We now show that, under a common complexity theoretic assumption, we cannot decrease the capacities by much more than a constant before the problem of the existence of arc-disjoint branching flows becomes non-polymomial.

Exponential Time Hypothesis (ETH): [7]

There is a positive real s such that 3-SAT with n variables and m clauses cannot be solved in time 2 sn (n + m)O [START_REF] Ahuja | Network flows[END_REF].

If the ETH is true, then there is no algorithm that solves 3-SAT in subexponential time. That is, there is no 2 o(n) algorithm that solves a 3-SAT instances with n variables. Using the so-called Sparsification Lemma we can obtain the following lemma.

Lemma 5.1 [START_REF] Impagliazzo | Which problems have strongly exponential complexity[END_REF] Given ETH, there is a positive real s such that 3-SAT with n variables and m clauses cannot be solved in time 2 s m (n + m)O(1). Lemma 5.2 Assume the ETH holds and let > 0 be arbitrary and let k(n) be an integer function, such that (log(n)) 1+ ≤ k(n) ≤ n/2 for all n > 0. Furthermore assume that there exists a constant C * such that for all c ≥ C * there exists an n such that k(n) = c.

Then there is no polynomial (in n) algorithm for deciding if a digraph D of order n and with s ∈ V (D) contains two arc-disjoint (s, k(n))-branching flows.

Proof: Let F be an instance of 3-SAT, with variables v 1 , v 2 , . . . , v l and clauses

C 1 , C 2 , . . . , C m . That is, F = C 1 ∧ C 2 ∧ • • • ∧ C m .
We will construct a digraph D as follows (see Figure 1).

Let X 1 , X 2 , X 3 . . . , X l and W 1 , W 2 , . . . , W l-1 be independent vertex sets of size two. Let Q be an independent set of size q (q will be determined later) and let the vertex set of D be the following.

V (D) = {s, t, c 1 , c 2 , . . . , c m } ∪ X 1 ∪ X 2 ∪ • • • ∪ X l ∪ W 1 ∪ W 2 ∪ • • • W l-1 ∪ Q
Add all possible arcs from X i to W i and from W i to X i+1 for all i = 1, 2, 3, . . . , l -1. Add two parallel arcs from s to each vertex in X 1 and two parallel arcs from t to each vertex in Q. Add Inria both arcs from X l to t. Denote the vertices of X i as X i = {x i , xi } for i = 1, 2, . . . , l and if clause C j contains literal v s then add two parallel arcs from x s to c j and if C j contains literal vs then add two parallel arcs from xs to c j (for all j = 1, 2, . . . , m). Note that |V (D)| = n = 4l + m + q. Let q be determined such that k(4l + m + q) = k(n) = 2l + m. By the definition of k(n) we note that the following holds (as we may assume that 2l + m > C * , where C * is defined in the statement of the lemma).

(log(n)) 1+ ≤ k(n) = 2l + m ≤ n 2
We will now consider the problem of deciding if D contains two arc-disjoint (s, k(n))-branching flows. First assume that it does and let B 1 and B 2 denote the two arc-disjoint (s, k(n))branching flows. As all vertices in V (D) \ {s, c 1 , c 2 , . . . , c m } have in-degree two and all vertices in {c 1 , c 2 , . . . , c m } have out degree zero (and therefore in-degree exactly one in B i for i = 1, 2) we note that the arcs carying flow in B 1 and B 2 must form arc-disjoint out-branchings in D. Below we will use the name B i for both the flow B i and the corresponding branching in D.

Let P i be the (s, t)-path in B i for i = 1, 2. Note that |V (P i )| = 2l + 1 and that in B i we include an arc from t to every vertex in Q. Therefore we must send at least 2l + q units of flow through the first arc in P i in B i . As 2l + q = n -k(n) we must send exactly this much flow through the arc, which implies that all vertices in {c 1 , c 2 , . . . , c m } belong to a subtree, S i , in B i which does not start with the first arc of P i . Note that S i contains exactly one vertex in each X j , for j = 1, 2, . . . , l (the is on P ). If S i contains the vertex x j then let v j = T rue and if S i contains the vertex xj then let v j = F alse. It is not difficult to see that clauses C r are satisfied as the arc into c r indicates which literal is true. Therefore F is satisfied in this case.

Conversely, assume that F is satisfied by the truth assignment t. Let X contain x j if v j = T rue under t and let X contain xj otherwise.

Let X = (X 1 ∪ X 2 ∪ • • • ∪ X l ) \ X . Denote the vertices of W i by W i = {w 1 i , w 2
i } for all i = 1, 2, . . . , l -1. Let P i be the (s, t)-path containing all vertices in X and all vertices w i j for j = 1, 2, 3, . . . , l -1 and i = 1, 2. Let S i be the out-tree containing all vertices in X ∪ {c 1 , c 2 , . . . , c m } and all vertices w 3-i j for j = 1, 2, 3, . . . , l -1 and i = 1, 2 (which is possible as F is satisfied by t). Let B i be the out tree obtained by adding (a copy of) the arcs sx 1 and sx 1 and (a copy of) each arc from t to Q to P i and S i . Note that B 1 and B 2 are two arc-disjoint out-branchings, which can easily be made into (s, k(n))-branching flows (by sending the appropriate amount of flow through the arcs of B i ). We have now shown that there exists two disjoint (s, k(n))-branching flows if and only if F is satisfiable.

For the sake of contradiction assume that there is a polynomial (in n) algorithm for deciding if a digraph D of order n and with s ∈ V (D) contains two arc-disjoint (s, k(n))-branching flows. Let the algorithm have complexity O(n c ), for some constant c.

As (log(n)) 1+ ≤ k(n) we note that log(n) ≤ k(n) 1/(1+ ) , which gives us an algorithm with the following complexity.

O(n c ) = O 2 (k(n) 1/(1+ ) ) c = O 2 c((2l+m) 1/(1+ ) )
As l ≤ 3m, the running time is at most O(2 c(7m) ), where = 1/(1 + ) < 1. This is a contradiction to Lemma 5.1.

Let > 0 be arbitrary. By Lemma 5.2 we note that there is no polynomial (in n) algorithm (assuming the ETH) for deciding if a digraph D of order n and with s ∈ V (D) contains two arcdisjoint (s, log(n) 1+ )-branching flows. Furthermore, if c < 1/2 then there is also no polynomial algorithm for deciding if a digraph D of order n and with s ∈ V (D) contains two arc-disjoint (s, cn )-branching flows.

6 Remarks and open problems

Analogous statements in undirected graphs

A natural question is to ask whether the analogues of our results holds for undirected graph. Some of them do. For example, the analogous statement to Corollary 3.2 is easy to show. Proposition 6.1 A graph G contains a pair of edge-disjoint s-rooted spanning trees such that s has degree at least 2 in both if and only if d(s) ≥ 4 and D contains a pair of s-rooted spanning trees.

Proof: Suppose T, T are edge-disjoint s-rooted spanning trees and s has degree only 1 in T and at least 3 in T . Let K 1 , K 2 , . . . K p be the connected components of T -s and suppose w.l.o.g that x ∈ K 1 where x is the unique neighbour of s in T . If we add the edge sy from s to K 2 in T to the tree T we obtain a cycle C. Let uv be any edge on C that enters K 2 . Then T -+ uv and T -uv + sy are the desired spanning trees.

In contrast, the analogue of Theorem 3.1 does not hold for edge-disjoint spanning trees in undirected graphs. To see this, consider the graph G = (V, E) with V = {s, a, b, c, d} and edges E = {sa, sb, sc, sd, ab, ad, bc, cb} (so there are two parallel edges between b and c). G is the union of two spanning trees and G -{sa, sd} and G -{sb, sc} are both connected but there is no pair of spanning trees T 1 , T 2 such that T 1 contains the edges sa, sd and T 2 contains the edges sb, sc.

Still we can check for such trees efficiently using matroids. This is not new but we include the proof here for completeness. Theorem 6.2 Let p be a fixed natural number. There exists a polynomial-time algorithm for the following problem. Given an undirected graph G = (V, E) and p edge-disjoint forrests U 1 , . . . , U p ; decide whether G contains p edge-disjoint spanning trees T 1 . . . , T p such that E(U i ) ⊆ E(T i ) for i ∈ [p].

Proof: We show how to formulate this problem as a matroid partition problem. Given G = (V, E) and p disjoint subsets E 1 , . . . , E p of E, each inducing a forrest in G, we first define the following p subsets of E:

F i = {E ⊆ E \ E i : E ∪ E i induces a forest in G} for i ∈ [p].
It is well-known and easy to show that each F i is the set of independent sets of a matroid and hence, by Edmonds' Matroid Union Theorem, the family F = {X ⊂ E : ∃X 1 , . . . , X p ⊂ E such that X = X 1 ∪ . . . ∪ X p , X i ∩ X j = ∅ when i = j and X i ∈ F i , i ∈ [p]} is the set of independent sets of a matroid (see .e.g. [START_REF] Recski | Matroid theory and its applications in electric network theory and in statics[END_REF]). Now it follows that G contains the desired edge-disjoint trees if and only if the size of a base in the matroid M = (E, F) is p(|V | -1) -i∈[p] |E i |. Furthermore, applying the greedy algorithm for constructing a base of M we obtain either a solution or a proof that none exists in polynomial time.

The trees we will consider below are rooted at a prescribed vertex s and we say that T is s-rooted if it is rooted in s. Let us call an s-rooted spanning tree T k-safe if the tree that remains after deleting the subtree of any of the neighbours of s has at least k vertices. Theorem 6.3 For every pair of fixed integers k, p, there exists a polynomial-time algorithm for deciding whether an undirected graph G with prescribed root s contains a collection of p edgedisjoint k-safe s-rooted spanning trees.

Inria

Proof: Observe that an s-rooted spanning tree T is k-balanced if and only if it contains an s-rooted subtree with at most 2k -1 vertices which is itself k-balanced (we need 2k -1 only if s has degree 2 in T ). Now let T be the set of all k-balanced s-rooted trees on at most 2k -1 vertices in G. We can find the set T in time O(|V | 2k-1 ). For each collection of p edge-disjoint trees U 1 , . . . , U p of T each containing s we can test in polynomial time using the algorithm of Theorem 6.2 whether there are p edge-disjoint s-rooted spanning trees that extend U 1 , . . . , U p respectively. By the remark above this proves the theorem.

Further research

Theorem 4.7 asserts that for every fixed integer k, deciding whether an input digraph with a prescribed vertex s contains two arc-disjoint (s, k)-branching flows can be done in polynomial time. A natural question is to ask about the parameterized complexity of the problem with respect to the parameter k. The above result shows that the problem is in XP. A natural question is to ask whether it is fixed-parameter tractable (FPT) or not.

Corollary 3 . 2

 32 A digraph D contains a pair of arc-disjoint s-out-branchings such that s has out-degree at least 2 in both if and only if d + (s) ≥ 4 and D contains a pair of arc-disjoint branchings.

Lemma 4 . 2

 42 Let D be a digraph, let s be a vertex of D such that s can reach all vertices in D, and X a set of vertices containing s. If D[X] contains an (s, k)-branching flow, then D contains an (s, k)-branching flow.

Definition 4 . 3

 43 An (s, k)-core in D is a set X of vertices containing s, of cardinality 2k, and such that D[X] contains an (s, k)-branching flow.

Theorem 4 . 4

 44 Let k be a positive integer, let D be a digraph D of order at least 2k, and let s be a vertex from which all vertices of D are reachable. D contains an (s, k)-branching flow if and only if it has an (s, k)-core.

Lemma 4 . 5

 45 Let D = (V, A) be a digraph on n vertices and let k be a positive integer such that n > 2k. Assume that there exists an (s, k)-branching flow, x, in D and let A ⊆ A x be arbitrary. Let N be the network consisting of the digraph D x and with capacity u(e) = n -k on all e ∈ A x \ A and u(e) = n -k -1 for all e ∈ A .

Lemma 4 . 6

 46 Let k be a positive integer. If there exists an (s, k)-branching flow x in a digraph D of order greater than 2k, then there exists an (s, k)-branching flow in D -v for some vertex v ∈ V (D) \ {s}.Proof: Let x and D be defined as in the statement of the lemma. Any set, X, with s ∈ X and |X| = k and d + D (X) = 1 is called a critical set in D. We first show that at most one critical set exists in D. For the sake of contradiction assume that X and Y are distinct critical sets in D.As X = Y we note that |X ∩ Y | < k. As x has flow n -1 -(|X ∩ Y | -1) > n -k leaving X ∩ Y ,we note that there are at least two arcs, e 1 and e 2 , leaving X ∩ Y in D. Each e i leaves X or Y (or both). As only one arc leaves X and only one arc leaves Y we can without loss of generality assume that e 1 leaves X but not Y and e 2 leaves Y but not X. This implies that no arc leaves X ∪ Y as otherwise d + (X) or d + (Y ) would be greater than one. As n > 2k and |X ∪ Y | ≤ 2k -1 we get a contradiction to s being able to reach all vertices in D. Therefore at most one critical set exists in D.

Problem 6 . 4

 64 Does there exists an integer-valued function f a constant c and an algorithm that, given an integer k, an input digraph D and a vertex s in D, decides in time f (k) • n c whether D contains two arc-disjoint (s, k)-branching flows ?

Inria

RR n°8640

It is easy to check that every s-branching flow from s which decomposes into path flows (no cycle in the decomposition) is an (s, 1)-branching flow.Inria

route des Lucioles -BP 93 06902 Sophia Antipolis Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

Institute Mittag-Leffler, spring 2014. The research of Bang-Jensen was also supported by the Danish research council under grant number 1323-00178B † Project Coati, I3S (CNRS, UNSA) and INRIA, Sophia Antipolis, France (). The research of Yeo was supported by the Agence Nationale pour la Recherche under grant number ANR-13-BS02-0007 The research of Yeo was supported by the Danish research council under grant number 1323-00178B


Sylvie Boldo

published or not. The documents may come

Formal verification of tricky numerical computations

Formal verification of tricky numerical computations

Sylvie Boldo

Inria LRI, CNRS UMR 8623, Université Paris-Sud PCRI -Bâtiment 650 Université Paris-Sud 91405 ORSAY Cedex FRANCE sylvie.boldo@inria.fr Keywords: Floating-point, formal proof, deductive verification Computer arithmetic has applied formal methods and formal proofs for years. As the systems may be critical and as the properties may be complex to prove (many sub-cases, error-prone computations), a formal guarantee of correctness is a wish that can now be fulfilled. This talk will present a chain of tools to formally verify numerical programs. The idea is to precisely specify what the program requires and ensures. Then, using deductive verification, the tools produce proof obligation that may be proved either automatically or interactively in order to guarantee the correctness of the specifications. Many examples of programs from the literature will be specified and formally verified.


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 coloration de graphe, graphe planaire, coloration backbone, conjecture de Steinberg

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. Steinberg conjectured that if G is planar and G contains no cycles on 4 or 5 vertices, then χ(G) ≤ 3. If this conjecture is correct, then one could deduce that CBC 2 (G, H) ≤ 6, for any H ⊆ G. In this work, we first show that if G is a planar graph containing no cycle on 4 or 5 vertices and H ⊆ G is a forest, then CBC 2 (G, H) ≤ 7. Then, we prove that if H ⊆ G is a forest whose connected components are paths, then CBC 2 (G, H) ≤ 6.

Introduction

In this paper, all graphs are considered to be simple and we use standard terminology as the one in [?].

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.

(

) 2
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] Appel | Every planar map is four colorable[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. 1 Whenever we refer to Z k , we mean the group of integers modulo k, also denoted by Z/nZ.

RR n°8641

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.

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, in: Quo vadis, graph theory?[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.

Inria 2 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. 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.

Definitions and notations

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 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

(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

| 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.

Inria 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 counter-example 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. 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 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}.

Av(u) = [a 1 -1] or [a 1 -1]
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). Inria 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 and(G, H) is (7, 2)-minimal. By Lemma 15, G must be connected.

|V (G)| ≤ 3. Hence we have |V (G)| ≥ 4,
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). Consequently, 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 counter-example 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 counter-example 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). Proof. (i) Suppose for a contradiction that (G, H) -{u, v} admits two C 1 -twin colourings c and c at u . One of them, say c, satisfies c(u ) = c(v ). Note that c(u ) is forbidden to u and v. Consequently, with respect to the colouring c, the sets Av(u) and Av(v) of available colours at u and v have size at least 2 and they are not equal, since c(u ) = c(v ). Thus we can choose c(u) ∈ Av(u) and c(v

7 7 u' u v v' u''
) ∈ 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 (i) there is no pair of C-twin colourings at u , and

Int(C 2 ) = Int(C 2 ) = {u, v, v }. Property 27. If (G, H) contains a configuration C ∈ {C 2 , C 2 }, then RR n°8641 8 7 8 8 7 7 u' u v v' w u'' v'' z u' u v v' w u'' v''
(ii) d t (u ) ≥ 8.
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 (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 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. (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).

) = c (v ) is not opposite to c(v ). If |c(v ) -c(v )| 6 = 1, then c(v )
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).

7 8 u' u w v v' u'' z v''
(ii) if u u ∈ E(G -H) and u is a node, then d t (u ) ≥ 9.
Proof. Let us first prove a claim that we use to prove both statements. We claim that there exists no colouring c of (G, H) -{u, v, w} such that c(u ) = c(u ) + 3, no matter whether u u ∈ E(G) \ E(H). Let us prove this claim by contradiction and let c such a colouring. Observe that | Av(u)| ≥ 2 and | Av(v)| ≥ 2, and that Av(u) contains two consecutive colours, since c(u ) = c(u ) + 3. Without loss of generality, we assume that {1, 2} ⊆ A(u) and that c(z) ∈ {2, 3, 4}. Since | Av(v)| ≥ 2, we first extend the colouring c to v by colouring v with a colour c(v) = 5. Then, in order to reach a contradiction, we show that for every possible colour c(v) = 5 one can extend c into a colouring of (G, H):

• Case 1: c(v) ∈ {1, 2, 3}. Set c(w) = 5 and choose c(u) ∈ {1, 2} \ {c(v)}.
• Case 2: c(v) = 4. Set c(u) = 2 and c(w) = 6.

RR n°8641

• Case 3: c(v) = 6. Set c(u) = 1 and choose c(w) ∈ {3, 4} \ {c(z)}.

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 non-negative, 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)
Inria 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 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 Inria 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 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 ϕ 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.

(x) ≥ d t (x) -5 -( d t (x)/2 -2) -2 ≥ d t (x)/2 -5 ≥ 0. Lemma 37. Let x be a node. If d t (x) = 6, then ϕ (x) ≥ 0.
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 Lemmas 33, 34, 35,36, 37, 38, and 39 show that all faces and vertices have non-negative final weight. Thus Φ ≥ 0. This contradicts Lemma 30 and completes the proof of the theorem.

Inria

  Let S ⊆ V (G) be a subset of vertices of G and F ⊆ E(G) be a subset its 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 )).

Lemma 14 .

 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.

Lemma 18 .

 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)).

  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].

Figure 1 :

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

Figure 2 : 1 .

 21 Figure 2: The configuration C 1 .

Figure 3 :

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

  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 .

• Case 1 :

 1 c(u ) = 1. Recall that c and c are C-twin colourings at u . Thus, without loss of generality, assume that c(u ) = 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 )}, 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.

Property 28 .Figure 4 :

 284 Figure 4: Configuration C 3

Figure 5 : Configuration C 4

 54 Figure 5: Configuration C 4

Figure 6 :

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

Figure 7 :

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

Proof.-

  Assume d t (x) = 6. Then x sends no charge by Rules 3 because ϕ(x) = -2, nor by Rules 4 by Lemma 31. Moreover, by Rule 4.1, x receives 2 (1 of each of its neighbours). Now x is adjacent to at most one 3-face by Property 22, because d(x) = 2. If x is incident to no 3-face, then it does not gives anything by Rule 1. So ϕ (x) = ϕ(x) + 2 = 0. If x is incident to a 3-face, then it gives 1 to this 3-face by Rule 1, but it also receives 1 by Rule 2. Hence ϕ (x) = ϕ(x) + 2 -1 + 1 = 0. Lemma 38. Let x be a node. If d t (x) = 7, then ϕ (x) ≥ 0. Proof. Assume d t (x) = 7. Then x sends no charge by Rules 3 because ϕ(x) = 0, nor by Rules 4 by Lemma 31. Moreover, x is adjacent to at most one 3-face by Property 22, because d(x) = 3. If x is incident to no 3-face, then it does not send any charge, so ϕ (v) ≥ ϕ(x) = 0. Assume now that x is incident to a 3-face T . Therefore x sends a charge of 1 by Rule 1. • If T contains the two backbone edges incident to x, then we are in a Configuration C 3 . Let us use the notation of the Figure 4, so our vertex x is w. Observe that d t (u) ≥ 7 and d t (v) ≥ 7 by Property 24. -If ϕ(u) ≥ 4 or ϕ(v) ≥ 4, then by Rule 3.1, x receives at least 1. Hence ϕ (x) ≥ ϕ(x) -1 + 1 = 0 If ϕ(u) < 4 and ϕ(v) < 4, then u and v are nodes. Hence d t (u) ≤ 8 and d t (v) ≤ 8. Consequently, by Property 28, d t (u) = d t (v) = 8. Thus, we are in a Configuration C 4 with x = w. Let us use the notation of Figure 5. If u is not adjacent to u , then x receives 1 from u by Rule 4.2. If u u is an edge, then u is either a leaf with total degree at least 7 (by Property 28), or a node with total degree at least 9 (by Property 29). In both cases, ϕ(u ) ≥ 4, so x receives 1 from u by Rule 3.2. So ϕ (x) ≥ ϕ(x) -1 + 1 ≥ 0. • If T contains only one of the backbone edges incident to x, then we are in Configuration D depicted Figure 8. Let us use the notation of this figure. By Property 24, both u and v have total degree at least 7.

---

  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 have d 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.

RR n°8641

route des Lucioles -BP 93 06902 Sophia Antipolis Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

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.

This work was supported by the CNRS-FUNCAP programme GAIATO between the team COATI of I3S and the team ParGO of the Federal University of Ceará.