Jørgen Bang-Jensen

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

Nicolas Trotignon
email: nicolas.trotignon@ens-lyon.fr

Finding an induced subdivision of a digraph *

Keywords: NP-completeness, induced paths and cycles, linkings, 3-SAT

We consider the following problem for oriented graphs and digraphs: Given an oriented graph (digraph) G, does it contain an induced subdivision of a prescribed digraph D? The complexity of this problem depends on D and on whether G must be an oriented graph or is allowed to contain 2-cycles. We give a number of examples of polynomial instances as well as several NPcompleteness proofs.

Introduction

Many interesting classes of graphs are defined by forbidding induced subgraphs, see [START_REF] Chudnovsky | Excluding induced subgraphs[END_REF] for a survey. This is why the detection of several kinds of induced subgraphs is interesting, see [START_REF] Lévêque | Detecting induced subgraphs[END_REF] where several such problems are surveyed. In particular, the problem of deciding whether a graph G contains, as an induced subgraph, some graph obtained after possibly subdividing prescribed edges of a prescribed graph H has been studied. This problem can be polynomial or NP-complete depending on H and to the set of edges that can be subdivided. The aim of the present work is to investigate various similar problems in digraphs, focusing only on the following problem: given a digraph H, is there a polynomial algorithm to decide whether an input digraph G contains a subdivision of H?

Of course the answer depends heavily on what we mean by "contain". Let us illustrate this by surveying what happens in the realm of non-oriented graphs. If the containment relation is the subgraph containment, then for any fixed H, detecting a subdivision of H in an input graph G can be performed in polynomial time by the Robertson and Seymour linkage algorithm [START_REF] Robertson | Graph minors. XIII. The disjoint paths problem[END_REF] (for a short explanation of this see e.g. [START_REF] Bang-Jensen | Kriesell Disjoint directed and undirected paths and cycles in digraphs[END_REF]). But if we want to detect an induced subdivision of H then the answer depends on H (assuming P =NP). It is proved in [START_REF] Lévêque | Detecting induced subgraphs[END_REF] that detecting an induced subdivision of K 5 is NP-complete, and the argument can be reproduced for any H whose minimum degree is at least 4. Polynomial-time solvable instances trivially exist, such as detecting an induced subdivision of H when H is a path, or a graph on at most 3 vertices. But non-trivial polynomial-time solvable instances also exist, such as detecting an induced subdivision of K 2,3 that can be performed in time O(n 11 ) by the Chudnovsky and Seymour's three-in-a-tree algorithm, see [START_REF] Chudnovsky | The three-in-a-tree problem[END_REF]. Note that for many graphs H, nothing is known about the complexity of detecting an induced subdivision of H: when H is cubic (in particular when H = K 4 ) or when H is a disjoint union of 2 triangles, and in many other cases.

When we move to digraphs, the situation becomes more complicated, even for the subdigraph containment relation. All the digraphs we will consider here are simple, i.e. they have no loops nor multiple arcs. We rely on [START_REF] Bang-Jensen | Digraphs: Theory, Algorithms and Applications[END_REF] for classical notation and concepts. A subdivision of a digraph D, also called a D-subdivision, is a digraph obtained from D by replacing each arc ab of D by a directed (a, b)-path. From the NP-completeness of the 2-linkage problem, proved by Fortune, Hopcroft and Wyllie [START_REF] Fortune | The directed subgraph homeomorphism problem[END_REF], it is straightforward to construct an oriented graph H such that deciding whether a given oriented graph G contains a subdivision of H as a subgraph is NP-complete. See Theorem 33.

Let us now think about the induced subdigraph relation. An induced subdigraph of a digraph G which is a subdivision of D is called an induced subdivision of D. When D is a digraph, we define:

PROBLEM Π D Input: A digraph G.
Question: Does G contain an induced subdivision of D?

In Π D , the instance digraph G may have (directed) 2-cycles, where the 2-cycle is the digraph C 2 on 2 vertices a, b with 2 arcs ab and ba. Because of these 2-cycles, NP-completeness results are often quite easy to obtain, because no induced directed path can go through a 2-cycle (which by itself contains a chord). Hence 2-cycles are very convenient to force an induced directed path to go through many places of a large digraph that models an instance of 3-SAT. This yields NPcompleteness results that cover large classes of detection problems. See Section 4. In fact, it can be easily shown (see Section 2) that if D is the disjoint union of spiders (trees obtained from disjoint directed paths by identifying one end of each path into a vertex) and at most one 2-cycle, then Π D is polynomial-time solvable. However, except from those digraphs, we are not aware of any D for which Π D is polynomial time solvable. We indeed conjecture that there are none. As an evidence, we show that if D is an oriented graph, i.e. a digraph with no 2-cycles, then Π D is NP-complete unless it is the disjoint union of spiders (see Corollary 13).

It seems that allowing or not allowing 2-cycles is an essential distinction. Hence we also consider the restricted problem Π D in which the input graph G is an oriented graph.

PROBLEM Π D

Input: An oriented graph G.

Question: Does G contain an induced subdivision of D?

Observe that if Π D is polynomial-time solvable then Π D is also polynomial-time solvable. Conversely, if Π D is NP-complete then Π D is also NP-complete. Hence, NP-completeness results cover less cases for Π D .

Similarly to Π D , for several D's, Π D is solvable by very simple polynomial-time algorithms (See Section 2). However, in this case they are not the only ones. We could obtain several digraphs for which Π D is solvable in polynomial time with non-trivial algorithms.

We denote by T T 3 the transitive tournament on 3 vertices a, b, c and arcs ab, ac, bc. In Subsection 5.1, we use a variant of Breadth First Search that computes only induced trees to solve Π T T 3 in polynomial time.

We also study oriented paths in Subsection 5.2. An oriented path is an orientation of a path. The length of an oriented path P is its number of arcs and is denoted l(P). Its first vertex is called its origin and its last vertex its terminus. The blocks of an oriented paths are its maximal directed subpaths. We

Easily polynomial-time solvable problems

There are digraphs D for which Π D or Π D can be easily proved to be polynomial-time solvable. For example, it is the case for the directed k-path P k on k vertices. Indeed, a P k -subdivision is a directed path of length at least k -1 and an induced directed path of length at least k -1 contains an induced P k . Hence a digraph has a P k -subdivision if and only if it has P k as an induced subdigraph. This can be checked in time O(n k ) by checking for every set of k vertices whether or not it induces a P k .

A vertex of a digraph is a leaf if its degree is one, a node if its out-degree or its in-degree is at least 2, and a continuity otherwise, that is if both its out-and in-degree equal 1. A spider is a tree having at most one node. Proof. An oriented graph contains an induced subdivision of C 3 if and only if it is not acyclic.

Moreover, the following is polynomial-time solvable.

NP-completeness results for oriented graphs

In all proofs below it should be clear that the reductions can be performed in polynomial time and hence we omit saying this anymore. Before starting with the NP-completeness proofs, we state a proposition.

Proposition 6. Let D be a digraph and C a connected component

1 of D. If Π C is NP-complete then Π D is NP-complete. Similarly, if Π C is NP-complete then Π D is NP-complete.
Proof. Let D 1 , . . . , D k be the components of D and assume that Π D 1 is NP-complete. To show that Π D is NP-complete, we will give a reduction from

Π D 1 to Π D .
Let G 1 be an instance of Π D 1 and G be the digraph obtained from D by replacing D 1 by G 1 . We claim that G has an induced D-subdivision if and only if G 1 has an induced D 1 -subdivision.

Clearly, if G 1 has an induced D 1 -subdivision S 1 then the disjoint union of S 1 and the

D i , 2 ≤ i ≤ k is an induced D-subdivision in G.
Reciprocally, assume that G contains an induced D-subdivision S. Let S i , 1 ≤ i ≤ k be the con-

nected components of S such that S i is an induced D i -subdivision. Set G i = D i if i ≥ 2. Then the G i 's are the connected components of G. Thus S 1 is contained in one of the G i 's. If it is G 1 then
we have the result. Otherwise, it is contained in some other component say

G 2 = D 2 . In turn, S 2 is contained in some G j . Hence G j contains a D 1 -subdivision because S 2 contains a D 1 -subdivision since D 2 contains S 1 . Thus G j cannot be G 2 since G 2 already contains D 1 and |S 2 | ≥ |G 2 |. If j = 1
then we have the result. If not we may assume that j = 3. And so on, for every i ≥ 3, applying the same reasoning, we show that one of the following occurs:

• S i is contained in G 1 and thus G 1 contains a D 1 -subdivision because S i did.

• S i is contained in G j which cannot be any of the G i , 1 ≤ l ≤ i, for cardinality reasons. Hence we may assume that G j = G i+1 and that G i+1 and hence S i+1 contains a D 1 -subdivision.

Since the number of components is finite, the process must stop, so G 1 contains an induced D 1subdivision.

Induced (a, b)-path in an oriented graph

Our first result is an easy modification of Bienstock's proof [START_REF] Bienstock | On the complexity of testing for odd holes and induced odd paths[END_REF] that finding an induced cycle through two given vertices is NP-complete for undirected graphs. To be precise, suppose C p = (x i ∨ x j ∨ x k ), then we add the following three 3-cycles l1 p x i v i l 1 p , l 2 p x j v j l 2 p and l 3 p x k v k l 3 p . This concludes the construction of G 1 (I ). We claim that there is an induced directed (a, b)-path in G 1 (I ) if and only if I is satisfiable.

3 d 3 x 1 ∨ x2 ∨ x 3 x1 ∨ x 2 ∨ x3 b a x1 x2 x3 x 1 x 2 x 3 c 1
Suppose first that I is satisfiable and consider a truth assignment T which satisfies I . Now form a directed (a, b)-path P by taking the arcs aa 1 , c m b and the following subpaths: for each variable x i take the subpath a i xi vi b i if T sets x i true and otherwise take the subpath a i x i v i b i . For each clause C j we fix a litteral l j which is satisfied by T and take the subpath c j l j d j . It is easy to check that P is induced as we navigate it to avoid each of the arcs between the variable chain U and the clause chain W .

Suppose now that Q is an induced directed (a, b)-path in G 1 (I ). It follows from the construction that Q starts by a directed (a 1 , b n )-path through all variable gadgets which contains no vertices from W and continues with a directed (c 1 , d m )-path through all clause gadgets which contains no vertices from U. This follows from the presence of the directed 3-cycles that prevent Q from using any of the arcs going from a variable gadget to a clause gadget other than the arc b n c 1 . Similarly there is no induced directed (c 1 , d m )-path which contains any vertex from U. Now form a truth assignment by setting

x i true if and only if Q uses the subpath a i xi vi b i and false otherwise. Since Q is induced, for each clause C j if Q uses the subpath c j l j d j , then we claim that l j will be true with the truth assignment just described: if l j = x k for some k then since Q is induced the presence of the arc l j x k implies that Q uses the path a k xk vk b k and similarly, if l j = xk then Q uses the path a k x k v k b k and again C j is satisfied.

Induced subdivisions of directed cycles

We first show that for any k ≥ 4, the problem We move now to the detection of induced subdivisions of digraphs H when H is the disjoint union of one or more directed cycles, all of length 3. If there is just one cycle in H, the problem is polynomial-time solvable by Proposition 3. But from two on, it becomes NP-complete. We need results on the following problem.

Π C k is NP-complete.

PROBLEM DIDPP

Input: An acyclic digraph G and two vertex pairs (s 1 ,t 1 ), (s 2 ,t 2 ). Moreover, there is no directed path from {s 2 ,t 2 } to {s 1 ,t 1 }.

Question: Does G have two paths P 1 , P 2 such that P i is a directed (s i ,t i )-path, i = 1, 2, and G V (P 1 ) ∪ V (P 2 ) is the disjoint union of P 1 and P 2 ?

Problem k-DIDPP was shown to be NP-complete by Kobayashi [START_REF] Kobayashi | Induced disjoint paths problem in a planar digraph Discrete Applied Mathematics[END_REF] using a proof similar to Bienstock's proof in [START_REF] Bienstock | On the complexity of testing for odd holes and induced odd paths[END_REF].

Theorem 10. Let D be the disjoint union of two directed cycles with no arcs between them. Then Π D is NP-complete.

Proof. Let G be an instance of DIDPP and H the oriented graph obtained from it by adding new vertices u 1 , u 2 and the arcs t 1 u 1 , u 1 s 1 , t 2 u 2 and u 2 s 2 . Since G was acyclic it is not difficult to see that Suppose C p = (x i ∨ x j ∨ x k ), then we add the following three 2-cycles l 1 p x i l 1 p , l 2 p x j l 2 p and l 3 p x k l 3 p . This concludes the construction of G 2 (I ). See Figure 4. Finally, if all its connected components are spiders then Π D is polynomial-time solvable according to Theorem 5.

H is a yes-instance of Π D if and only if G is a yes-instance of DIDPP.

NP-completeness results for digraphs

l 2 xi a i x i d j l 3 l 1 c j b i
b 3 d 3 x 1 ∨ x2 ∨ x 3 x1 ∨ x 2 ∨ x3 b a x1 x2 x3 x 1 x 2 x 3 c 1
We believe that Corollary 13 can be generalized to digraphs.

Conjecture 14. Let D be a digraph. Then Π D is NP-complete unless D is the disjoint union of spiders and at most one 2-cycle.

As support for this conjecture, we give some other digraphs D (which are not oriented graphs), for which Π D is NP-complete. In particular, when D is the lollipop, that is the digraph L with vertex set {x, y, z} and arc set {xy, yz, zy}. Note that the lollipop seems to be the simplest digraph that is not an oriented graph nor a C 2 . So it should be an obvious candidate for a further polynomial case if one existed.

Theorem 15. Deciding if a digraph contains an induced subdivision of the lollipop is NP-complete.

Proof. Reduction from 3-SAT. Let I be an instance of 3-SAT with variables x 1 , x 2 , . . . , x n and clauses In this section, we show that the picture is more complicated for Π D than for Π D . We show some oriented graphs D for which Π D is polynomial-time solvable. For all these oriented graphs, Π D is NP-complete by Corollary 13.

C 1 ,C 2 , . . . ,C m . We first create a variable gadget V 3 i for each variable x i , i = 1,

Induced subdivision of cherries in oriented graphs

Let s, u, v be three vertices such that s = v and u = v (so s = u is possible). A cherry on (s, u, v) is any oriented graph made of three induced directed paths P, Q, R such that:

• P is directed from s to u (so when s = u it has length 0);

• Q and R are both directed from u to v (so they both have length at least 1 and since we do not allow parallel edges, at least one of them has length at least 2);

• u, v are the only vertices in more than one of P, Q, R;

• there are no other arcs than those from P, Q, R.

The cherry is rooted at s.

An induced cherry contains an induced T T 3 -subdivision (made of Q and R) and a T T 3 -subdivision is a cherry (with u = s). Hence detecting an induced cherry is equivalent to detecting an induced T T 3subdivision.

In order to give an algorithm that detects a cherry rooted at a given vertex, we use a modification of the well-known Breadth First Search algorithm (BFS), see e.g. [START_REF] Bang-Jensen | Digraphs: Theory, Algorithms and Applications[END_REF]Section 3.3]. Given an oriented graph G and a vertex s ∈ V (D), BFS returns an out-tree rooted at s and spanning all the vertices reachable from s. It proceeds as follows:

BFS(G, s) Create a queue Q consiting of s; Intialize T = ({s}, / 0) while Q is not empty do Consider the head u of Q and visit u, that is foreach out-neighbour v of u in D do if v / ∈ V (T ) then V (T ) := V (T ) ∪ {v} and A(T ) := A(T ) ∪ {uv} Put v to the end of Q Delete u from Q
Note that the arc-set of the out-branching produced by BFS depends on the order in which the vertices are visited, but the vertex-set is always the same: it is the set of the vertices reachable from s. See [START_REF] Bang-Jensen | Digraphs: Theory, Algorithms and Applications[END_REF] p. 92 for more details on BFS. We need the following variant:

IBFS(G, s) Create a queue Q consisting of s; Intialize T = ({s}, / 0) while Q is not empty do Consider the head u of Q and visit u, that is foreach out-neighbour v of u in G do if N G (v) ∩V (T ) = {u} then V (T ) := V (T ) ∪ {v} and A(T ) := A(T ) ∪ {uv} Put v to the end of Q Delete u from Q
Observe that IBFS (which we also call induced-BFS) is the same as BFS except that we add the out-neighbour v of u to T only if it has no other neighbour already in T , hence ensuring that the resulting out-tree is an induced subdigraph of G. Contrary to BFS, the vertex-set of a tree obtained after IBFS may depend on the order in which the vertices are visited.

IBFS can easily be implemented to run in time O(n 2 ). When T is an oriented tree, we denote by T [x, y] the unique oriented path from x to y in T .

Theorem 17. Let G be an oriented graph, s a vertex and T a tree obtained after running IBFS(G, s).

Then exactly one of the following outcomes is true: (i) D contains an induced subdigraph that is a cherry rooted at s;

(ii) for every vertex x of T , any out-neighbour of x not in T has an out-neighbour that is an ancestor of x in T . This is algorithmic in the sense that there is an O(n 2 ) algorithm that either outputs the cherry of (i) or checks that (ii) holds.

Proof. Suppose that T does not satisify (ii). Then some vertex x of T has an out-neighbour y not in T and no out-neighbour of y is an ancestor of x. Without loss of generality, we assume that x is the first vertex added to T when running IBFS with such a property. In particular, T [s, x]y is an induced directed path because a chord would contradict (ii) or the choice of x. Let v be the neighbour of y in T , different from x, that was first added to T when running IBFS. Note that v exists for otherwise y would have been added to T when visiting x. If x is the parent of v in T then T [s, x]y together with v form a cherry rooted at s (whatever the orientation of the arc between y and v). So we may assume that x is not the parent of v. When visiting x, vertex y was not added to T , hence v was already visited (because x is not the parent of v). In addition, when v was visited, it was the unique neighbour of y in the current out-tree, so y is an in-neighbour of v, for otherwise it would have been added to T . Let u be the common ancestor of x and v in T , chosen closest to x. Since T does not satisfy (ii) by the choice of x and y, u = v. Now the directed paths sTu, T [u, x]yv and T [u, v] form an induced cherry rooted at s. Indeed since T is an induced out-tree, it suffices to prove that y has no neighbour in these three paths except x and v. By definition of v, there is no neighbour of y in T [s, u] and T [u, v] except v. Moreover, y has no out-neighbour in T [u, x] by the assumption that (ii) does not hold for y and x and it has no in-neighbour in T [u, x] except x by the choice of x.

Conversely, let us assume that T satisfies (ii) and suppose by contradiction that G contains an induced cherry C rooted at s. Since T is an induced out-branching, some vertices of C are not in T .

So, let y be a vertex of V (C) \V (T ) as close to s as possible in the cherry. Let x be an in-neighbour of y in C ∪ T . From the choice of y, x and all its ancestors along the cherry are in T . Since T is induced, the ancestors of x along the cherry are in fact the ancestors of x along T . Hence, x is a vertex of T with an out-neighbour y not in T having no out-neighbour among the ancestors of x along T . This contradicts T satisifying (ii).

All this may be turned in an O(n 2 )-algorithm that finds a cherry rooted at s if it exists or answer no otherwise. Indeed we first run IBFS and then check in time O(n 2 ) if the obtained tree T satisfies (ii).

If not, then we can find the cherry following the first paragraph of the proof.

Remark 18. Since a digraph contains an induced T T 3 -subdivision if and only if it contains an induced cherry, Theorem 17 implies directly that Π T T 3 is solvable in time O(n 3 ) (because we need to enumerate all potential roots).

We can slightly extend our result. A tiny cherry is a cherry such that the path Q and R as in the definition form a T T 3 .

Corollary 19. For any tiny cherry D, the problem Π D is solvable in time O(n |V (D)| ).

Proof. Let P be the path of D as in the definition of cherry. Let G be the input oriented graph. Enumerate by brute force all induced directed paths of order |P| by checking all the possible subdigraphs of order |P|. For each such path P with terminus x, look for a cherry rooted at x in the graph G obtained by deleting all the vertices of Px and their neighbourhoods except x. If there is such a cherry C then the union of P and C is an induced D-subdivision.

Similarly to Propositions 4 and 5, we have the following.

Corollary 20. If D is the disjoint union of spiders and a tiny cherry then Π D is polynomial-time solvable.

Induced subdivision of oriented paths with few blocks in oriented graphs.

By Proposition 1, for any oriented path P with at most two blocks Π P and thus Π P are polynomialtime solvable. In this section, we shall prove that Π P is polynomial-time solvable for some oriented paths with three or four blocks. In contrast, Π P is NP-complete for every oriented path with at least three blocks as shown in Corollary 13.

Oriented path with three blocks

Theorem 21. There exists an algorithm of complexity O(m 2 ) that given a connected oriented graph on n vertices and m arcs with a specified vertex s returns an induced A + 2 -subdivision with origin s if one exists, and answer 'no' if not.

Proof. Observe that any induced A + 2 -subdivision with origin s contains an induced A + 2 -subdivision with origin s such that the directed path corresponding to the arc s 3 s 2 is some arc f . Such a subdivision is called f -leaded.

Given an oriented graph G, we enumerate all arcs f = s 3 s 2 . For each arc in turn we either show that there is no f -leaded induced A + 2 -subdivision with origin s or give an induced subdivision of A + 2 with origin s, (but not necessarily f -leaded). This will detect the A + 2 -subdivision since if some exists, it is f -leaded for some f .

We do this as follows. We delete all in-neighbours of s and all neighbours of s 3 except s From this theorem, one can show that finding an induced A - 3 -subdivision is polynomial-time solvable. It is enough to enumerate all arcs s 2 s 1 , to delete s 1 and its neighbours except s 2 , and to decide whether there exists in what remains an A + 2 -subdivision with origin s 2 . One can also derive polynomial-time algorithms for finding induced subdivisions of other oriented paths with three blocks.

Corollary 22. Let P be a path with three blocks such that the last one has length 1. One can check in time O(n |P|-2 m 2 ) whether a given oriented graph contains an induced P-subdivision.

Proof. By directional duality, we may assume that P is an A - 3 -subdivision. Let Q be the subdigraph of P formed by the first block of P and the second block of P minus the last arc. Let s be the terminus of Q. For each induced oriented path Q in the instance graph, isomorphic to Q (there are at most O(n |P|-2 ) of them), we delete Qs and all vertices that have neighbours in Qs except s. We then detect an A + 2 -subdivision rooted at s in the resulting graph. This will detect a P-subdivision if there is one.

Induced subdivision of A - 4 in an oriented graph

We show how to check the presence of an induced copy of A - 4 by using flows (for definitions and algorithms for flows see e.g. [START_REF] Bang-Jensen | Digraphs: Theory, Algorithms and Applications[END_REF]Chapter 4]).

Theorem 23. There exists an algorithm of complexity O(nm 2 ) that given an oriented graph on n vertices and m arcs with a specified vertex s returns an induced A + 3 -subdivision rooted at s, if one exists, and answer 'no' if not.

Proof. The general idea is close to the one of the proof of Theorem 21. Observe that any induced A + 3 -subdivision with origin s = a 1 contains an induced subdivision of A + 3 with origin s = a 1 such that the directed path corresponding to the arc s 3 s 4 is some arc f . If, in addition, the vertex corresponding

to s 2 is v, such a subdivision is called (v, f )-leaded.
Given an oriented graph G, we enumerate all pairs (a 2 , a 3 a 4 ) such that a 2 , a 3 , a 4 are distinct vertices and a 3 a 4 ∈ E(G). For each such pair in turn we either show that there is no (a 2 , a 3 a 4 )-leaded induced A + 3 -subdivision with origin a 1 or give an induced subdivision of A + 3 with origin a 1 (but not necessarily (a 2 , a 3 a 4 )-leaded).

We do this as follows. We first delete all the neighbours of a 4 except a 3 , all in-neighbours of a 1 and a 3 and finally all out-neighbours of a 2 . If this results in one or more of the vertices a 1 , . . . , a 4 to be deleted, then there cannot be any (a 2 , a 4 a 3 )-leaded induced A + 3 -subdivision with origin a 1 because there is an arc in G {a 1 , . . . , a 4 } which is not in {a 1 a 2 , a 3 a 2 , a 3 a 4 }. So we skip this pair and proceed to the next one. Otherwise we delete a 4 and we use a flow algorithm to check in the resulting digraph G the existence of two internally-disjoint directed paths P, Q such that the origin of P and Q are a 1 and a 3 respectively and such that a 2 is the terminus of both P and Q. Moreover, we suppose that these two paths have no forward chord (this can easily be ensured by running BFS on the graphs induced by each of them). If no such paths exist , then we proceed to the next pair because there is no (a 2 , a 3 a 4 )-leaded induced A + 3 -subdivision. If we find such a pair of directed paths P, Q, then we shall provide an induced subdivision of A + 3 with origin a 1 . If P and Q are induced and have no arcs between them, then these paths together with the arc a 3 a 4 form the desired induced subdivision of

A + 3 .
Suppose that P is not induced. As P has no forward chord, there is an arc uv in G V (P) such that From here on, we suppose that P is induced.

u
Suppose now that there is an arc e with an end x ∈ V (P) and the other y ∈ V (Q). Choose such an arc so that the sum of the lengths of P[a 1 , x] and Q[a 3 , y] is as small as possible. If e is from x to y we have y = a 3 because we removed all the in-neighbours of a 3 , else e is from y to x and we have x = a 1 because we removed all the in-neighbours of a 1 . In all cases, we get an induced subdivision of A + 3 by taking the paths P[a 1 , x] and Q[a 3 , y] and the arcs a 3 a 4 , e. From here on, we suppose that there are no arcs with an end in V (P) and the other in V (Q).

The last case is when Q is not induced. Since Q has no forward chord, there is an arc uv in There are O(nm) pairs (a 2 , a 3 a 4 ) and for each of them, we run an O(m) flow algorithm (we just need to find a flow of value 2, say, by the Ford-Fulkerson method [1, Section 4.5.1]) and do some linear-time operations. Hence the complexity of the algorithm is O(nm 2 ).

G V (Q) such
One can check in polynomial time if there is an induced A - 4 -subdivision: it is enough to enumerate all arcs t 2 t 1 , to delete t 1 and its neighbours except t 2 , and to decide whether there exists in what remains an A + 3 subdivision with origin t 2 . One can also derive polynomial-time algorithm for finding induced subdivision of other oriented paths with four blocks.

Corollary 24. Let P be an oriented path that can be obtained from A - 4 by subdividing the first arc and the second arc. One can check in time O(n |P|-1 m 2 ) whether a given oriented graph contains an induced subdivision of P.

Proof. Let R be the subdigraph of P formed by the first block of P and its second block minus the last arc. Let s be the last vertex of R. For each induced oriented path Q in the instance graph, isomorphic to R (there are O(n |P|-3 ) of them), we delete Qs, all vertices that have neighbours in Qs except s and detect an A - 3 -subdivision with origin s. This will detect a P-subdivision if there is one. 6 Induced subdivisions of tournaments in oriented graphs

Induced subdivision of transitive tournaments

The transitive tournament on k vertices is denoted T T k . We saw in Section 5.1 that Π T T 3 is polynomial.

The next result shows that Π T T k is NP-complete for all k ≥ 4.

Theorem 25. For all k ≥ 4, Π T T k is NP-complete Proof. For a given instance I of 3-SAT, let G 4 (I ) be the digraph we obtain from G 1 (I ) by replacing each clause gadget C 1 j by the modified one C 4 j from Figure 6. Also for each variable, modify the gadget V 1 i as follows: replace the path a i x i v i b i by a path a i x 1 i v 1 i x 2 i v 2 i . . . x m i v m i b i , and similarly the path

a i xi vi b i by a path a i x1 i v1 i x2 i v2 i . . . xm i vm i b i .
Then in G 4 (I) the links representing a variable x i and a clause C j that uses this variable are represented by arcs between vertices from the variable gadget with superscript j (as in Figure 2).

Recall that G 1 (I ) has an induced directed (a, b)-path if and only if I is satisfiable. It is easy to see that the same holds for G 4 (I ). Note that in G 4 (I ) no vertex has in-or out-degree larger than 2.

Given an instance I of 3-SAT we form the digraph G k 4 (I ) from G 4 (I ) and a copy of T T k (with vertices v 1 , v 2 , . . . , v k and arcs v i v j , 1 ≤ i < j ≤ k) by deleting the arc v 1 v k and adding the arcs v 1 a, bv k .

We claim that G k 4 (I ) contains an induced subdivision of T T k if and only if G 4 (I ) has an induced directed (a, b)-path which is if and only if I is satisfiable.

Clearly, if I is satisfiable, we may use the concatenation of an induced directed (a, b)-path in

G 4 (I ) with v 1 a and bv k in place of v 1 v k to obtain an induced T T 4 -subdivision in G k 4 (I ).
Conversely, suppose that G k 4 (I ) contains an induced subdivision of T T k and let h(v i ),

1 ≤ i ≤ k, denote the image of v i in some fixed induced subdivision H of T T k . Then we must have h(v 1 ) = v 1 and h(v k ) = v k , because G 4 (I ) does not contain any vertex of out-degree k -1 or in-degree k -1 because k ≥ 4. For all i, 1 < i < k, the vertex h(v i ) could not be in V (G 4 (I )) since otherwise there must be either two disjoint directed (v i , v k )-paths to v k or two disjoint directed (v 1 , v i )-paths. This is impossible because there is no directed (v i , v k )-path in G k 4 (I ) \ bv k and no directed (v 1 , v i )-path in G k 4 (I ) \ v 1 a. Hence h(v i ) = v i
for all 1 ≤ i ≤ k and so it is clear that we have an induced directed (a, b)-path in G 4 (I ), implying that I is satisfiable.

In the proof above we used that the two vertices v 1 , v k cannot be mapped to vertices of G 4 (I ),

the fact that the connectivity between these and the other vertices is too high to allow any of these to be mapped to vertices of G 4 (I ) and finally we could appeal to the fact that G 4 (I ) has an induced directed (a, b)-path if and only if I is satisfiable. Refining this argument it is not difficult to see that the following holds where a (z, X)-path is a path whose initial vertex is z and whose last vertex belongs to X.

Theorem 26. Let D = (V, A) be a digraph and let X (resp. Y ) be the subset of vertices with outdegree (resp. in-degree) at least 3 and let Z = V \ (X ∪ Y ) (note that X ∩ Y = / 0 is possible and also Z = / 0 is possible). Suppose that for every z ∈ Z the digraph D contains either two internally disjoint implying that I is satisfiable.

Induced subdivision of the strong tournament on 4 vertices

Let ST 4 be the unique strong tournament of order 4. It can be seen has a directed cycle αγβδα together with two chords αβ and γδ. The aim of this section is to show that Π ST 4 is NP-complete.

An (x, y 1 , y 2 )-switch is the digraph with vertex set {x, z, y 1 , y 2 } and edge set {xz, xy 1 , zy 1 , zy 2 , y 2 y 1 }.

See Figure 7. Proof. Suppose for a contradiction, that y 2 y 1 ∈ E(S). Then S must contain the unique in-neighbour z of y 2 and the unique in-neighbour x of z. Hence y 1 has in-degree 3 in S, a contradiction.

Suppose for a contradiction, that zy 1 ∈ E(S). Then S must contain x the unique in-neighbour of z.

Hence xy 1 is a chord of S and so z must have degree 3 in S. Thus y 2 ∈ V (S) and y 1 has in-degree 3 in S, a contradiction.

Theorem 28. Π ST 4 is NP-complete.

Proof. Reduction from 3-SAT. Let I be an instance of 3-SAT with variables x 1 , x 2 , . . . , x n and clauses For each clause C, we connect the three literal vertices of the gadget for C to the variable gadgets for variables occuring as literals in C in the way indicated in Figure 9. We denote by X i the path a i a i x 0

x 4 i d j q 3 j q 2 j q 1 j q 0 j p 0 j p 2 j p 1 j p 3 j p j q j c j q j r 0 j r 1 j r 2 j r 3 j a i x 0 i a i x0 i x1 i x2 i b i b i x3 i x4 i x 1 i x 3 i x 2 i
i x 1 i x 2 i x 3 i x 4 i b i , by Xi the path a i x0 i x1 i x2 i x3 i x4 i b i b i
, by P j the path c j p j p 0 j p 1 j p 2 j p 3 j d j , by Q j the path c j q j q j q 0 j q 1 j q 2 j q 3 j d j , and by R j the path c j q j r 0 j r 1 j r 2 j r 3 j d j .

Similarly to the proof of Lemma 7, one can check that I is satisfiable if and only if there are two The union of these paths and the directed cycle acbd is an induced ST 4 -subdivision in G * 5 (I ).

Conversely, assume that G * 5 (I ) contains an induced subdivision S of ST 4 . For sake of simplicity (and with a slight abuse of notation), we will denote the vertices of S corresponding to α, β, γ and δ by the same names. Let T 1 and T 2 be the paths corresponding to the chord αβ and γδ respectively in S and let C be the directed cycle corresponding to αγβδα. Observe that the ends of T 1 and T 2 must alternate on C.

Notice that the subdigraphs induced by the sets {a i , a i , x 0 i , x0 i }, 1 ≤ i ≤ n, {c j , p j , p 0 j , q j } and {q j , q j , q 0 j , r 0 j } are good switches. In addition, the subdigraphs induced by the sets {b i , b i ,

x 4 i , x4 i },
1 ≤ i ≤ n, are the converse of good switches. Hence Lemma 27 (and its converse) imply the following proposition.

Claim 28.1.

(i) For 1 ≤ i ≤ n, if a i ∈ V (S)
, then exactly one of the two paths (a i , a i ,

x 0 i ) and (a i , x0 i ) is in S. (ii) For 1 ≤ i ≤ n, if b i ∈ V (S), then exactly one of the two paths ( x4 i , b i , b i ) and (x 4 i , b i ) is in S. (iii) For 1 ≤ j ≤ m, if c j ∈ V (S)
, then exactly one of the three paths (c j , p j , p 0 j ), (c j , q j , q j , q 0 j ) and (c j , q j , r 0 j ) is in S.

Since G * 5 (I ) \ da is acyclic, C must contain the arc da. Moreover since there is no arc with tail in some clause gadget and head in some variable gadget, C contains at most one arc with tail in some variable gadget and head in some clause gadget.

Claim 28.2. For any 1 ≤ i ≤ n and any 1 ≤ j ≤ m, the cycle C contains no arc with tail in {x 3 i , x3 i } and head in {p 1 j , q 1 j , r 1 j }.

Proof. Assume for a contradiction that C contains such an arc y 3 i l 1 j . Then since l 1 j and l 2 j have outdegree 1 then C must also contain l 2 j and l 3 j . Thus, in S, y 3 i has out-degree 3 in S, a contradiction.

Claim 28.3. For any 1 ≤ i ≤ n and any 1 ≤ j ≤ m the cycle C contains no arc with tail in {x 3 i , x3 i } and head in {p 3 j , q 3 j , r 3 j }.

Proof. Assume for a contradiction that C contains such an arc y 3 i l 3 j . Then since y 3 i and y 2 i have indegree 1 then C must also contain y 2 i and y 1 i . Thus, in S, l 3 j has in-degree 3 in S, a contradiction.

Claim 28.4. For any 1 ≤ i ≤ n and any 1 ≤ j ≤ m then C contains no arc with tail in {x 3 i , x3 i } and head in {p 2 j , q 2 j , r 2 j }.

Proof. Assume for a contradiction that C contains such an arc y 3 i l 2 j . The vertex l 2 j has a unique outneighbour l 3 j which must be in C. It follows that y 3 i l 3 j corresponds to one of the chords αβ or γδ.

Thus l 2 j must have degree 3 in S. It follows that l 1 j is in V (S) and so y 3 i has out-degree 3 in S, a contradiction.

Claim 28.5. For any 1 ≤ i ≤ n and any 1 ≤ j ≤ m the cycle C contains no arc with tail in {x 2 i , x2 i } and head in {p 3 j , q 3 j , r 3 j }.

Proof. Assume for a contradiction that C contains such an arc y 2 i l 3 j . The vertex y 2 i has a unique inneighbour y 1 i which must be in C. It follows that y 1 i l 3 j corresponds to one of the chords αβ or γδ.

Thus y 2 i must have degree 3 in S. It follows that y 3 i is in V (S) and so l 3 j has in-degree 3 in S, a contradiction.

Claim 28.6. For any 1 ≤ i ≤ n and any 1 ≤ j ≤ m the cycle C contains no arc with tail in {x 1 i , x1 i } and head in {p 3 j , q 3 j , r 3 j }.

Proof. Assume for a contradiction that C contains such an arc y 1 i l 3 j . Without loss of generality y

1 i = x 1 i .
By the remark after Claim 28.1 this is the only arc from a variable gadget to a clause gadget.

Furthermore, we have that b is not on C.

Thus, by Claim 28.1, for every 1 ≤ k < i, the intersection of C and V 4 k is either X k or Xk , and for every j < l ≤ m, the intersection of C and C 5 j is either P j , Q j or R j .

Consider y ∈ {α, β}. It is on C and has outdegree 2. On the other hand, applying Claim 28.1 we see that the following must hold as none of these vertices can belong to S and at the same time have two of their out-neighbours in S:

• y ∈ ∪ 1≤ j≤m {c j , p j , q j , q j , q 0 j },

• y ∈ ∪ k =i {a k , a k , x 0 k , x 4 k } and

• y ∈ {a i , a i , x 0 i , x 4 i }.

By Claims 28.2-28.5, we have y ∈ {x 2 i , x 3 i } and since b is not on C we also have y = b. If y = x 1 i , then using that yl 3 j is and arc of C we get a contradiction because x 2 i l 3 j is an arc (so we cannot obtain an induced copy of S using both arcs yl 3 j , x 2 i l 3 j ). Hence (as y was any of α, β) we have a = α = β, a contradiction.

Claim 28.7. C = acbda.

Proof. Suppose not. Then by the above claims, C either does not intersect the clause gadget and intersect all the variable ones or does not intersect the variable gadget and intersect all the gadget ones.

In both cases, similarly to the proof of Claim 28.5, one shows that a = α = β, a contradiction.

Since C = acbda and by construction of G * 5 (I ), T 1 and T 2 are two induced disjoint path in G 5 (I )

and so I is satisfiable. We were able to settle the complexity of Π D when D is a directed cycle, a directed path, or some paths with at most four blocks. The following problems are perhaps the natural next steps.

Remarks and open problems

Problem 30. What is the complexity of Π D when D is an oriented cycle which is not directed?

Problem 31. What is the complexity of Π D when D is an oriented path which is not directed? one can check in polynomial time (using flows) whether a digraph contains internally disjoint (x, z)-, (y, z)-paths for prescribed distinct vertices x, y, z. If we want to apply a similar approach for A - 5 , then for prescribed vertices x, y, z, w we need to be able to check the existence of internally disjoint paths P, Q, R such that P is an (x, y)-path, Q is a (z, y)-path and R is a (z, w)-path such that these paths are induced and have no arcs between them. However, the problem of deciding just the existence of internally disjoint paths P, Q, R with these prescribed ends is NP-complete by the result of Fortune et al. [START_REF] Fortune | The directed subgraph homeomorphism problem[END_REF]. Thus we need another approach to obtain a polynomial-time algorithm (if one exists). The following shows that the problem above can be NP-complete.

Theorem 33. Let H be the digraph in Figure 10. It is NP-complete to decide whether a given digraph G contains an H-subdivision.

Proof. By the classical result of Fortune, Hopcroft and Wyllie [START_REF] Fortune | The directed subgraph homeomorphism problem[END_REF], the so-called 2-linkage problem (given a digraph and four distinct vertices u, v, x, y; does G contain a pair of vertex-disjoint paths P, Q so that P is a directed (u, v)-path and Q is a directed (x, y)-path?) is NP-complete. By inspecting the proof (see [1, Section 10.2]) it can be seen that the problem is NP-complete even when G has maximum in-and out-degree at most 3. Given an instance G of the 2-linkage problem with maximum in-and out-degree at most 3 and a copy of Finally, we would like to point out that in all detection problems about induced digraphs, backward arcs of paths play an important role, especially in NP-completeness proofs. Also, these backward arcs make all "connectivity-flavoured" arguments fail: when two vertices x, y are given, it is not

H

Proposition 4 .Proposition 5 .

 45 If D is the disjoint union of spiders and a C 2 then Π D is polynomial-time solvable.Proof. D = D -C 2 is a collection of spiders. Let p be its order. For each set A of p vertices, wecheck if the digraph G A induced by A is D and if yes we check if G -(A ∪ N(A)) has a directed cycle.Similarly, If D is the disjoint union of spiders and a C 3 then Π D is polynomial-time solvable.

Lemma 7 .

 7 It is NP-complete to decide whether an oriented graph contains an induced (a, b)-path for prescribed vertices a and b. Proof. Given an instance I of 3-SAT with variables x 1 , x 2 , . . . , x n and clauses C 1 ,C 2 , . . . ,C m we first create a variable gadget V 1 i for each variable x i , i = 1, 2, . . . , n and a clause gadget C 1 j for each clause C j , j = 1, 2, . . . , m as shown in Figure 1. Then we form the digraph G 1 (I ) as follows (see Figure 2): Form a chain U of variable gadgets by adding the arcs b i a i+1 for i = 1, 2, . . . , n -1 and a chain W of clause gadgets by adding the arcs d j c j+1 , j = 1, 2, . . . , m -1. Add the arcs aa 1 , b n c 1 , c m b to get a chain from a to b. For each clause C, we connect the three literal vertices of the gadget for C to the variable gadgets for variables occuring as literals in C in the way indicated in the figure.

2 jFigure 1 :

 21 Figure 1: The variable gadget V 1 i (left) and the clause gadget C 1 j (right).

  b

Figure 2 :

 2 Figure 2: The digraph G 1 (I ) when I has variables x 1 , x 2 , x 3 and three clauses C 1 ,C 2 ,C 3 where C 1 = ( x1 ∨ x 2 ∨ x3 ) and C 3 = (x 1 ∨ x2 ∨ x 3 ) (for clarity we do not show the arcs corresponding to C 2 )

Theorem 8 .

 8 It is NP-complete to decide whether an oriented graph contains an induced subdivision of a fixed directed cycle of length at least 4. Proof. Given an instance I of 3-SAT with variables x 1 , x 2 , . . . , x n and clauses C 1 ,C 2 , . . . ,C m we form the digraph G * 1 (I ) from G 1 (I ) which we defined above by adding the arc ba. Let C be an induced cycle of G * 1 (I ). Since the variable chain U and the clause chain W are both acyclic, C must contain an arc with tail l in W and head y in U. If ly = ba, then there exists i such that y ∈ {x i , xi } and so C = lx i v i l or C = l xi vi l by construction of G * 1 (I ). Hence every induced directed cycle of length at least 4 contains the arc ba. Thus G * 1 (I ) has an induced cycle of length at least 4 if and only if G 1 (I ) has an induced directed (a, b)-path. As shown in the proof of Lemma 7 this is if and only if I is satisfiable. Theorem 9. Let D be an oriented graph containing an induced directed cycle of length at least 4 with a vertex of degree 2 2. It is NP-complete to decide whether a given oriented graph contains an induced subdivision of D. Proof. Let D be given and let I be an arbitrary instance of 3-SAT. Fix an induced directed cycle C of length at least 4 in D and fix an arc uv on C such that u is of degree 2. Let G 1 (I ) be the oriented graph that we obtain by replacing the arc uv by a copy of G 1 (I ) and the arcs ua, bv. We claim that G 1 (I ) contains an induced subdivision of D if and only if I is satisfiable (which is if and only if G 1 (I ) contains an induced directed (a, b)-path). Clearly, if G 1 (I ) has an induced directed (a, b)-path, then we may use the concatention of this path with ua and bv instead of the deleted arc uv to obtain an induced D-subdivision in G 1 (I ) (the only subdivided arc will be uv). Conversely, suppose that G 1 (I ) contains an induced subdivision D of D. Clearly D has at least as many vertices as D and thus must contain at least one vertex z of V (G 1 (I )). Since u is of degree 2, the digraph D \ uv has fewer induced directed cycles of length at least 4 than D. (Note that the fact that u is of degree 2 is important: if u has degree more than 2, deleting uv could create new induced directed cycles. ) Thus z must be on a cycle of length at least 4 in D . But this and the fact that G 1 (I ) has no induced directed cycle of length at least 4 implies that G 1 (I ) contains an induced directed (a, b)-path (which passes through z).

Figure 3 :

 3 Figure 3: The variable gadget V 2 i (left) and the clause gadget C 2 j (right). Unoriented bold edges represent 2-cycles.

Figure 4 :

 4 Figure 4: The digraph G 2 (I ) when I has variables x 1 , x 2 , x 3 and three clauses C 1 ,C 2 ,C 3 where C 1 = ( x1 ∨ x 2 ∨ x3 ) and C 3 = (x 1 ∨ x2 ∨ x 3 ) (for clarity we do not show the arcs corresponding to C 2 ) Similarly to the proof of Lemma 7, one can show that there is an induced directed (a, b)-path in G 2 (I ) if and only if I is satisfiable. Let G k 2 (I ) be the digraph obtained from C k by replacing one arc ab by G 2 (I ). It is easy to check that G 2 (I ) has no induced cycle of length at least 3. Hence G k 2 (I ) has an induced directed cycle of length k if and only if G 2 (I ) has an induced directed (a, b)-path. Hence by Lemma 7, G k 2 (I ) has an induced D-subdivision if and only if I is satisfiable. A branch is a directed walk such that all the vertices are distinct except possibly its ends, its ends are nodes or leaves and all its internal vertices are continuities. A branch is central if its two ends are nodes. The skeleton of a multidigraph D is the digraph whose vertices are the nodes and leaves in D and in which ab is an arc if and only if there is a directed (a, b)-branch in D. Observe that a skeleton may have loops and multiple arcs. Clearly, any subdivision of D has the same skeleton as D. Theorem 12. Let D be an oriented graph. If D contains a central branch, then Π D is NP-complete.

  2, . . . , n and a clause gadget C 3 j for each clause C j , j = 1, 2, . . . , m as shown in Figure 5. Then we form the digraph G 3 (I ) as follows: Form a chain U of variable gadgets by adding the arcs b i a i+1 for i = 1, 2, . . . , n -1 and a chain W of clause gadgets by adding the arcs d j c j+1 , j = 1, 2, . . . , m -1. Add the arcs aa 1 , b n c 1 , c m b to get a chain from a to b. For each clause C, we connect the three literal vertices of the gadget for C to the variable gadgets for variables occuring as literals in C in the way indicated in the figure. Similarly to the proof of Lemma 7, one can check that there is an induced directed (a, b)-path in G 3 (I ) if and only if I is satisfiable. The digraph G L 3 (I ) is obtained from L and G 3 (I ) by deleting the arc yz and adding the arcs ya and bz. It is easy to see that G 3 (I ) has no induced directed cycle of length 3 and that no 2-cycle is contained in an induced lollipop. Hence if G L 3 (I ) contains an L-subdivision, the induced directed cycle in it is the concatenation of the path bzya and a induced directed (a, b)-path in G 3 (I ). Thus I is satisfiable. The other direction is (as usual) clear.

Figure 5 :

 5 Figure 5: The variable gadget V 3i , (top left), the clause gadget C 3 i (bottom left) and the way to connect them in G 3 (I ) (right). Bold unoriented edges represent 2-cycles. Only the connection for one variable gadget and one clause gadget is shown and the general strategy for connecting variable and clause gadgets is the same as in G 1 (I) (Figure2).

  2 . Let us denote by G the resulting graph. Then we compute by BFS a shortest directed path P from s to s 2 . If it is induced, together with s 3 s 2 , it forms the desired A + 2 subdivision. So, as P has no forward chord (since it is a shortest path), there is an arc uv in G V (P) such that u occurs after v on P. Take such an arc b 3 b 2 such that b 2 is as close as possible to s (in P). Observe that since we deleted all in-neighbours of s we have b 2 = s. Now, P[s 1 , b 2 ] together with b 3 b 2 forms the desired A + 2 -subdivision. There are O(m) arcs and for each of them we must find a shortest path in G which can be done in O(m). Hence the complexity of the algorithm is O(m 2 ).

  occurs after v on P. Take such an arc b 3 b 2 such that b 2 is as close as possible to a 1 (in P), and subject to this, such that b 3 is as close as possible to a 2 . Observe that since we deleted all in-neighbours of a 1 and all out-neighbours of a 2 before, we must have b 2 = a 1 and b 3 = a 2 . Let b 4 be the successor of b 3 on P. Now P[a 1 , b 2 ] and the arcs b 3 b 2 , b 3 b 4 form the desired induced subdivision of A + 3 .

  that u occurs after v on Q. Take such an arc b 3 b 4 such that b 3 is as close as possible to a 2 (in Q). Observe that since we deleted all out-neighbours of a 2 before, we must have b 3 = a 2 . Now P, Q[b 3 , a 2 ] and the arc b 3 b 4 form the desired induced subdivision of A + 3 .

1 jFigure 6 :

 16 Figure 6: Left: clause gadget of G 1 (I ). Right: clause gadget of G 4 (I ).

(

  X, z)-paths or two internally disjoint (z,Y )-paths. Then Π D is NP-complete. Proof. (Sketch) For a given instance I of 3-SAT we form the digraph G 4 (I ) from D by replacing one arc uv with at least one of its endvertices in X ∪ Y by G 4 (I ) and the arcs ua, bv. Again it is clear how to obtain an induced subdivision of D in G 4 (I ) when I is satisfiable. Let us now assume that G 4 (I ) contains an induced subdivision D of D. Let {h(v)|v ∈ V } be the vertices corresponding to the vertices of V in the subdivision. For degree reasons, none of the vertices in X ∪ Y can have h(v) ∈ V (G 4 (I )) and because of connectivity, none of the vertices of Z can have h(z) ∈ V (G 4 (I ))because there is only one arc entering and leaving V (G 4 (I )) in G 4 (I ). Thus {h(v)|v ∈ V } = V (possibly with h(v) = v for several vertices). However, since we deleted the arc uv and replaced it by G 4 (I ) and the arcs ua, bv, it follows that G 4 (I ) and so G 4 (I ) contains an induced directed (a, b)-path,

2 Figure 7 :

 27 Figure 7: An (x, y 1 , y 2 )-switch. A good (x, y 1 , y 2 )-switch in a digraph D is an induced switch Y such that all the arcs entering Y have head x and all arcs leaving Y have tail in {y 1 , y 2 }.Lemma 27. Let Y be a good (x, y 1 , y 2 )-switch in a digraph D. Then every induced subdivision S of ST 4 in D intersects Y on either the path (x, y 1 ), the path (x, z, y 2 ), or the empty set.

C 1 ,

 1 C 2 , . . . ,C m . We first create a variable gadget V 5 i for each variable x i , i = 1, 2, . . . , n and a clause gadget C 5 j for each clause C j , j = 1, 2, . . . , m as shown in Figure8. Then we form the digraph G 5 (I ) as follows: Form a chain U of variable gadgets by adding the arcs b i a i+1 for i = 1, 2, . . . , n-1 and a chain W of clause gadgets by adding the arcs d j c j+1 , j = 1, 2, . . . , m -1. Add the arcs aa 1 , b n b, cc 1 ,t m d.

Figure 8 :

 8 Figure 8: The variable gadget V 5 i (left) and the clause gadget C 5 j (right).

Figure 9 :

 9 Figure 9: Connections between a clause gadget and a variable gadget in G 5 (I ). Only the connection for one variable gadget and one clause gadget is shown and the general strategy for connecting variable and clause gadgets is the same as in G 1 (I) (Figure2).

  induced disjoint directed (a, b)and (c, d)-paths in G 5 (I ).Let G * 5 (I ) be the digraph obtained from G 5 (I ) by adding the edges ac, cb, bd and da. Observe that G * 5 (I ) \ da is acyclic. Let us prove that G * If I is satisfiable, then in G 5 (I ) there are two induced disjoint directed (a, b)and (c, d)-paths.

  It would be nice to have results proving a full dichotomy between the digraphs D for which Π D (resp. Π D ) is NP-complete and the ones for which it is polynomial-time solvable. Regarding Π D , Conjecture 14 gives us what the dichotomy should be. But for Π D we do not know yet. A useful tool to prove such a dichotomy would be the following conjecture. Conjecture 29. If D is a digraph such that Π D (resp. Π D ) is NP-complete, then for any digraph D that contains D as an induced subdigraph, Π D (resp. Π D ) is NP-complete.

Figure 10 :

 10 Figure 10: The digraph H with specified vertices u H , v H , x H , y H .

  denote by A - k the path on vertices s 1 , s 2 , . . . , s k , s k+1 and arcs s 2 s 1 , s 2 s 3 , s 4 s 3 , s 4 s 5 , . . . and A + k the path on vertices s 1 , s 2 , . . . , s k , s k+1 and arcs s 1 s 2 , s 3 s 2 , s 3 s 4 , s 5 s 4 , . . .. These two paths are the antidirected paths of length k -1. Observe that A - k is the converse of A + k (i.e. it is obtained from A + k by reversing all the arcs); if k is odd they are isomorphic but the origin and terminus are exchanged. Clearly, an oriented path with k-blocks can be seen as a subdivision of A - k or A + k . In particular, paths with one block are the directed paths. We show that if P is an oriented path with three blocks such that the last one has length one then Π P is polynomial-time solvable. We also use classical flow algorithms to prove that Π A - If D is any of the two tournaments on 3 vertices, namely the directed 3-cycle C 3 and the transitive tournament T T 3 , then Π D is polynomial time solvable. Hence it is natural to study the complexity of larger tournaments. In Section 6, it is shown that if D is a transitive tournament on more than 3 vertices or the strong tournament on 4 vertices, then Π D is NP-complete. Finally, in Section 7, we point out several open questions.

	is polynomial-time solvable.
	4

  we form a new digraph G H by identifying the vertices {u, v, x, y} with {u H , v H , x H , y H } in that order. Clearly, if G has disjoint directed (u, v), (x, y)-paths, then we can use these to realize the needed paths from u H to v H and from x H to y H (and all other paths are the original arcs of H). Conversely, suppose there is a subdivisionH * of H in G H . For every v ∈ {u H , v H , x H , y H }, let us denote by v * the vertex corresponding to v in H * . Since d -(u H ) = 4, d + (v H ) = 5, d -(x H ) = 5, d + (y H ) = 4 in G H , we have u * H = u H ,v * H = v H , x * H =x H , and y * H = y H .

Thus the two disjoint directed (u * H , v * H )x * H , y * H )-paths in H * are disjoint directed (u, v), (x, y)-paths in G implying that G is a 'yes'-instance.

A connected component of a digraph H is a connected component in the underlying undirected graph of H.

The degree of a vertex v in a digraph is the number of arcs with one end in v, that is, the sum of the in-and out-degree of v.

(I ) contains an induced ST 4 -subdivision if and only if I is satisfiable.

Acknowledgement

The authors would like to thank Joseph Yu for stimulating discussions.

* This work was done while the first author was on sabbatical at Team Mascotte, INRIA, Sophia Antipolis France whose hospitality is gratefully acknowledged. Financial support from the Danish National Science research council (FNU) (under grant no. 09-066741) is gratefully acknowledged. Partly supported by ANR Blanc AGAPE ANR-09-BLAN-0159Partially supported by the French Agence Nationale de la Recherche under reference

possible to decide whether x can be linked to y. So, maybe another notion of induced subdigraph containment would make sense: chords should be kept forbidden between the different directed paths that arise from subdividing arcs, but backward arcs inside the paths should be allowed.


S Bessy

F Havet

Enumerating the edge-colourings and total colourings of a regular graph *

. We also show that the number of 4-total-colourings of a connected cubic graph is at most 3 • 2 3n/2 . Again, our proof yields a branching algorithm to enumerate all the 4-total-colourings of a connected cubic graph.

Introduction

We refer to [START_REF] Bondy | Graph theory[END_REF] for standard notation and concepts for graphs. In this paper, all the considered graphs are loopless, but may have parallel edges. A graph with no parallel edges is said to be simple. Let G be a graph. We denote by n(G) the number of vertices of G, and for each integer k, we denote by n k (G) the number of degree k vertices of G. Often, when the graph G is clearly understood, we abbreviate n(G) to n and n k (G) to n k . Throughout the paper, we are concerned with connected graphs.

Graph colouring is one of the classical subjects in graph theory. See for example the book of Jensen and Toft [START_REF] Jensen | Graph coloring problems[END_REF]. From an algorithmic point of view, for many colouring type problems, like vertex colouring, edge colouring and total colouring, the existence problem asking whether an input graph has a colouring with an input number of colours is NP-complete. Even more, these colouring problems remain NP-complete when the question is whether there is a colouring of the input graph with a fixed (and greater than 2) number of colours [START_REF] Garey | Computers and intractability. A guide to the theory of NPcompleteness[END_REF][START_REF] Holyer | The NP-completeness of edge-colouring[END_REF][START_REF] Sánchez-Arroyo | Determining the total colouring number is NP-hard[END_REF].

Exact algorithms to solve NP-hard problems are a challenging research subject in graph algorithms. Many papers on exact exponential time algorithms have been published in the last decade. One of the major results is the O * (2 n )-time inclusion-exclusion algorithm to compute the chromatic 1 number of a graph found independently by Björklund, Husfeldt [START_REF] Björklund | Inclusion-exclusion algorithms for counting set partitions[END_REF] and Koivisto [START_REF] Koivisto | An O(2 n ) algorithm for graph coloring and other partitioning problems via inclusion-exclusion[END_REF], see [START_REF] Björklund | Set partitioning via Inclusion-Exclusion[END_REF]. This approach may also be used to establish a O * (2 n )-time algorithm to count the k-colourings and to compute the chromatic polynomial of a graph. It also implies a O * (2 m )-time algorithm to count the k-edge-colourings and a O * (2 n+m )-time algorithm to count the k-total-colourings of a given graph.

Since edge colouring and total colouring are particular cases of vertex colouring, a natural question is to ask if faster algorithms than the general one may be designed in these cases. For instance, very recently Björklund et al. [START_REF] Björklund | Narrow sieves for parameterized paths and packings[END_REF] showed how to detect whether a k-regular graph admits a k-edge-colouring in time O * (2 (k-1)n/2 ).

The existence problem asking whether a graph has a colouring with a fixed and small number k of colours also attracted a lot of attention. For vertex colourability the fastest algorithm for k = 3 has running time O * (1.3289 n ) and was proposed by Beigel and Eppstein [START_REF] Beigel | 3-coloring in time O(1.3289 n )[END_REF], and the fastest algorithm for k = 4 has running time O * (1.7272 n ) and was given by Fomin et al. [START_REF] Fomin | Improved exact algorithms for counting 3-and 4-colorings[END_REF]. They also established algorithms for counting k-vertex-colourings for k = 3 and 4. The existence problem for a 3-edge-colouring is considered in [START_REF] Beigel | 3-coloring in time O(1.3289 n )[END_REF][START_REF] Kowalik | Improved edge-coloring with three colors[END_REF][START_REF] Golovach | Colorings with few colors: counting, enumeration and combinatorial bounds[END_REF]. Kowalik [START_REF] Kowalik | Improved edge-coloring with three colors[END_REF] gave an algorithm deciding if a graph is 3-edge-colourable in time O * (1.344 n ) and polynomial space and Golovach et al. [START_REF] Golovach | Colorings with few colors: counting, enumeration and combinatorial bounds[END_REF] presented an algorithm counting the number of 3-edge-colourings of a graph in time O * (3 n/6 ) = O * (1.201 n ) and exponential space. Golovach et al. [START_REF] Golovach | Colorings with few colors: counting, enumeration and combinatorial bounds[END_REF] also showed a branching algorithm to enumerate all the 3edge-colourings of a connected cubic graph in time O * (25 n/8 ) = O * (1.5423 n ) and polynomial space. In particular, this implies that every connected cubic graph of order n has at most O(1.5423 n ) 3edge-colourings. They give an example of a connected cubic graph of order n having Ω(1.2820 n ) 3-edge-colourings. In Section 2, we prove that a connected cubic graph of order n has at most 3 • 2 n/2 3-edge-colourings and give an example reaching this bound. Our proof can be translated into a branching algorithm to enumerate all the 3-edge-colourings of a connected cubic graph in time O * (2 n/2 ) = O * (1.4143 n ) and polynomial space. Furthermore, we extend our result proving that every k-regular connected graph of order n admits at most k • ((k -1)!) n/2 k-edge-colourings. This improves the bound derived from the maximal number of perfect matchings of a graph with a given degree sequence given by Alon and Friedland [START_REF] Alon | The maximum number of perfect matchings in graphs with a given degree sequence[END_REF]. Also, similarly 3-edge-colourings, we derive a branching algorithm to enumerate all the k-edge-colourings of a connected k-regular graph in time O * (((k -1)!) n/2 ) and polynomial space.

Regarding total colouring, very little has been done. Golovach et al. [START_REF] Golovach | Colorings with few colors: counting, enumeration and combinatorial bounds[END_REF] showed a branching algorithm to enumerate the 4-total-colourings of a connected cubic graph in time O * (2 13n/8 ) = O * (3.0845 n ), implying that the maximum number of 4-total-colourings in a connected cubic graph of order n is at most O * (2 13n/8 ) = O * (3.0845 n ). In Section 3, we lower this bound to 3 • 2 3n/2 = O(2.8285 n ). Again, our proof yields a branching algorithm to enumerate all the 4-total-colourings of a connected cubic graph in time O * (2.8285 n ) and polynomial space.

Edge colouring

A (proper) edge colouring of a graph is a colouring of its edges such that two adjacent edges receive different colours. An edge colouring with k colours is a k-edge-colouring. We denote by c k (G) the number of k-edge-colourings of a graph G.

General bounds for k-regular graphs

In this section, we are interested in computing the number of k-edge-colourings of k-regular connected graphs. We start by computing exactly the number of 3-edge-colourings of the cycles.

Proposition 1. Let C n be the cycle of length n. c 3 (C n ) = 2 n + 2, if n is even, 2 n -2, if n is odd. Proof. By induction on n. It is easy to check that c 3 (C 2 ) = c 3 (C 3 ) = 6. Let C n = (v 1 , v 2 , . . . , v n , v 1 ). Let A be the set of 3-edge-colourings of C n such that c(v n-1 v n ) = c(v 1 v 2 ) and B the set of 3-edge-colourings of C n such that c(v n-1 v n ) = c(v 1 v 2 )
. The 3-edgecolourings of A are in one-to-one correspondence with those of C n-1 and the pair of colourings of B agreeing everywhere except on v n v 1 are in one-to-one correspondence with the 3-edge-colourings

of C n-2 . Thus c 3 (C n ) = c 3 (C n-1 ) + 2c 3 (C n-2 ). Hence, if n is even, then c 3 (C n ) = 2 n-1 -2 + 2(2 n-2 + 2) = 2 n + 2, and if n is odd, then c 3 (C n ) = 2 n-1 + 2 + 2(2 n-2 -2) = 2 n -2.
Let us now present our method which is based on a classical tool: (s, t)-ordering.

Definition 2. Let G be a graph and s and t be two distinct vertices of G. An (s, t)-ordering of G is an ordering of its vertices v 1 , . . . , v n such that s = v 1 and t = v n , and for all 1 < i < n, v i has a neighbour in {v 1 , . . . , v i-1 } and a neighbour in {v i+1 , . . . , v n }.

Lemma 3 (Lempel et al. [START_REF] Lempel | An algorithm for planarity testing of graphs[END_REF]). A graph G is a 2-connected graph if, and only if, for every pair (s, t) of vertices, it admits an (s, t)-ordering.

In fact, Lempel et al. established Lemma 3 only for simple graphs but it can be trivially extended to graphs since replacing all the parallel edges between two vertices by a unique edge does not change the connectivity.

Theorem 4. Let G be a 2-connected subcubic graph. Then c 3 (G) ≤ 3 • 2 n-n 3 2 .
Proof. If G is a cycle, then the result follows from Proposition 1. Hence we may assume that G is not a cycle and thus has at least two vertices of degree 3, say s and t. By Lemma 3, there exists an (s, t)-ordering v 1 , v 2 , . . . , v n of G. Orient each edge of G according to this order, that is from the lower-indexed end-vertex towards its higher-indexed one. Let us denote by D the obtained digraph. Observe that

d + (v 1 ) = 3 = d -(v n ) and d -(v 1 ) = 0 = d + (v n ). Let A + (resp.
A -) be the set of vertices with outdegree 2 (resp. indegree 2) in D and A 2 be the set of vertices with degree 2 in G (and thus with indegree 1 and outdegree 1 in

D). Clearly, (A 2 , A -, A + ) is a partition of V (D) \ {v 1 , v n }. Observe that |A 2 | = n -n 3 . Since v∈V (D) d + (v) = v∈V (D) d -(v), we have |A + | = |A -|, and so |A + | = (n 3 -2)/2.
Now for i = 1 to n -1, we enumerate the p i partial 3-edge-colourings of the arcs whose tail is in {v 1 , . . . , v i }. For i = 1, there are 6 such colourings, since d + (v 1 ) = 3. Now, for each i, when we want to extend the partial colourings, two cases may arise.

• If d - D (v i ) = 1
, then we need to colour one or two arcs, and one colour (the one of the arc entering v i ) is forbidden, so there are at most 2 possibilities. Hence p i ≤ 2p i-1 .

• If d - D (v i ) = 2
, then we need to colour one arc, and at least two colours (the ones of the arcs entering v i ) are forbidden, so there is at most one possibility. Hence p i ≤ p i-1 .

At the end, all the edges of G are coloured, and a simple induction shows that c 3

(G) = p n-1 ≤ 6 • 2 |A 2 |+|A + | = 3 • 2 n-n 3 2 .
In particular, for a connected cubic graph G, we obtain c 3 (G) ≤ 3 • 2 n/2 . We now extend this result to k-regular graphs.

First, remark that every k-edge-colouring of a k-regular graph G is precisely the union of k (pairwise disjoint) perfect matchings of G. So, a bound on the number of perfect matchings in a k-regular graph yields to a bound on the number of k-edge-colourings of this graph. Computing the maximal number of perfect matchings in a graph is a classical problem in Graph Theory [START_REF] Bregman | Some properties of nonnegative matrices and their permanents[END_REF]. The best bound on graphs with degree constraints is due to Alon and Friedland [START_REF] Alon | The maximum number of perfect matchings in graphs with a given degree sequence[END_REF]. They proved that a k-regular graph admits at most (k!) n 2k distinct perfect matchings. So, as a k-edge-colouring is made of k perfect matchings, a k-regular graph admits at most (k!) n 2 k-edge-colourings. Under the assumption that the graph is connected, we improve this bound.

Theorem 5. Let G be a connected k-regular graph, with k ≥ 3. Then c k (G) ≤ k • ((k -1)!) n/2 .
Proof. First, observe that if a connected k-regular graph G admits a k-edge-colouring, then every colour induces a perfect matching of G, and then n is even. Furthermore, observe that G is 2connected. Indeed, assume that G has a cutvertex x and admits a k-edge-colouring c. As G has an even number of vertices, one of the connected components, say C, of G -x has odd cardinality. A colour appearing on an edge between x and a connected component of G -x different from C must form a perfect matching on C which is impossible. So, G is 2-connected.

Hence we can use the method of the proof of Theorem 4 and consider an (s, t)-ordering v 1 , . . . , v n of G and D the orientation of G obtained from this ordering (i.e. v i v j ∈ A(D) if and only if v i v j ∈ E(G) and i < j). The analysis made in the proof of Theorem 4 yields

c k (G) ≤ x∈V (G) (d + (x)!). For i = 1, . . . , k -1, we define A i = {x ∈ V (G)\{v 1 , v n } : d + (x) = i}. It is clear that (A i ) 1≤i≤k-1 form a partition of V (G) \ {v 1 , v n }. If we denote |A i | by a i , then c k (G) ≤ P := k! k-1 i=1 (i!) a i . Moreover S 1 := k-1
i=1 a i = n -2 (by counting the number of vertices of G) and S 2 := k-1 i=1 i • a i = k(n -2)/2 (by counting the number of arcs of D -v 1 ).

Let us now find the maximum value of P under the conditions S 1 = n -2 and S 2 = k(n -2)/2. If we can find 1 < p ≤ q < k -1 with a p = 0 and a q = 0 (or a p ≥ 2 if p = q), then we decrease a p and a q by one and increase a p-1 and a q+1 by one. Doing this, S 1 and S 2 are unchanged and P is multiplied by q+1 p > 1. We repeat this operation as many times as possible and stop when (a) for every i = 2, . . . , k -2, a i = 0 or (b) there exists j ∈ {2, . . . , k -2} such that for every i = 2, . . . , k -2 and i = j, a i = 0 and a j = 1. In case (b), S 1 gives a

1 + 1 + a k-1 = n -2 and S 2 is a 1 + j + (k -1)a k-1 = k(n -2)/2. Combining S 1 and S 2 , we obtain 2(k -2)a k-1 + 2(j -1) = (k -2)(n -2)
and we conclude that k -2 divides 2(j -1) and so that j = k/2. Solving S 1 and S 2 we have in particular that a 1 = a k-1 and 2a 1 = n -3 which is impossible, as n is even. Hence, we are in case (a), and solving S 1 and S 2 yields to a 1 = a k = (n -2)/2. We conclude that

P ≤ k!((k -1)!) n/2-1 .
We turn now the proof of Theorem 5 into an algorithm to enumerate all the k-edge-colourings of a connected k-regular graph. Corollary 6. There is an algorithm to enumerate all the k-edge-colourings of a connected k-regular graph on n vertices in time O * (((k -1)!) n/2 ) and polynomial space.

Proof. Let G be a connected k-regular graph. We first check the 2-connectivity of G. If it is not 2-connected, then we return 'The graph is not k-edge-colourable'.

If it is 2-connected, then we proceed as follows. We compute an (s, t)-ordering v 1 , . . . , v n of G, which can be done in polynomial time (see [START_REF] Even | Computing an st-numbering[END_REF] and [START_REF] Even | Corrigendum: Computing an st-numbering[END_REF] for instance), and orient G accordingly to this ordering. Now, it is classical to enumerate all the permutations of a set of size p in time O(p!) and linear space, in such way that, being given a permutation we compute in average constant time the next permutation in the enumeration (with the Steinhaus-Johnson-Trotter algorithm for instance, see [START_REF] Knuth | The art of Computer Programming, volume 4A: Combinatorial Algorithms[END_REF]).

Using this and the odometer principle, it is now easy to enumerate all the edge colourings we want. In the enumeration of all the permutations of {1, . . . , k}, we take the first one and assign the corresponding colours to the arc with tail x 1 . For any index i with 2 ≤ i ≤ k, we assign to the arcs with tail x i the first permutation in the enumeration of the permutations of the possible colours for these arcs (i.e. all the colours of {1, . . . , k} minus the one of the arcs entering in x i ). Then, we have the first colouring, and we check if it is a proper edge colouring of G (in polynomial time). To obtain the next colouring, we take the next permutation on the colours possible on the arcs with tail x n-1 , and so on. Once all the possible permutations have been enumerated for these arcs, we take the next permutation on the colours possible on the arcs with tail x n-2 and re-enumerate the permutation of possible colours for the arcs with tail x n-1 , and so on, following the odometer principle.

The bound given by Theorem 5 is optimal on the class of connected k-regular graphs. For all k ≥ 3, and n ≥ 2, n = 2p even, the k-noodle necklace N k n is the k-regular graph obtained from a cycle on 2p vertices (v 1 , v 2 , . . . , v 2p , v 1 ) by replacing all the edges v 2i-1 v 2i , 1 ≤ i ≤ p by k -1 parallel edges.

c k (N k n ) = k • ((k -1)!) n/2 .
Proof. Observe that in every k-edge-colouring of N k n the edges which are not multiplied (i.e. v 2i v 2i+1 ) are coloured the same. There are k choices for such a colour. Once this colour is fixed, there are (k -1)! choices for each set of k -1 parallel edges. Hence

c k (N k n ) = k • ((k -1)!) n/2 .

A more precise bound for cubic graphs

For simple cubic graphs, we lower the bound on the number of 3-edge-colourings from 3

• 2 n/2 to 9 4 • 2 n/2 . Lemma 8. If G is a connected cubic simple graph, then c 3 (G) ≤ 9 4 • 2 n/2 .
Proof. As in Theorem 4, let us consider an (s, t)-ordering v 1 , v 2 , . . . , v n of the vertices and the acyclic digraph D obtained by orienting all the edges of G according to this ordering. Let i be the smallest integer such that d -(v i ) = 2. Since every vertex (except v 1 ) has an inneighbour, there exists j such that there are two internally-disjoint directed paths from v j to v i in D. In G, the union of these two paths forms a cycle C. By definition of i, all vertices of C but v i have outdegree 2. So, if there is k such that j < k < i and v k / ∈ V (C), then v k has no outneighbour in C and the ordering v 1 , . . . , v k-1 , v k+1 , . . . v i , v k , v i+1 , . . . , v n is also an (s, t)-odering. Repeating this operation as many times as necessary, we may obtain that all the vertices of C are consecutive in the ordering, that is C = (v j , v j+1 , . . . , v i , v j ).

We enumerate the 3-edge-colourings of G in a similar way to the proof of Theorem 4, except that instead of examining the colour of arcs with tail in {v j , . . . , v i } one after another, we look at C globally. If j = 1, then there are exactly c 3 (C) 3-edge-colourings of C, because no arcs has head in C. If j > 1, then there are c 3 (C)/3 3-edge-colourings of C, because one arc has head v j and we need the colours of the two arcs with tail v j to have a colour distinct from it.

Recall that in D, v 1 has indegree 0, v p has indegree 3, n-2 2 vertices have indegree 2 and n-2 2 vertices have indegree 1. If j > 1 (resp. j = 1), then there are i -j (resp. i -2) vertices of indegree 1 in C, so there are n-2i+2j-2

2

(resp. n-2i+2

2

) vertices of indegree 1 in V (G) \ V (C). If j = 1, then we start by colouring C and then extend the colouring to G. Once C is coloured, there is at most one possibility to colour each arc with tail in C, so c

3 (G) ≤ c 3 (C) • 2 n-2i+2 2 = (c 3 (C)/2 i-1 ) • 2 n/2 . If j > 1,
we colour the arcs with tail in {v 1 , . . . , v j-1 } as usual. Remark that, by the choice of C, there is exactly one of these arcs, denoted by e, which has head in C and more precisely e has tail v j . Then, we consider all the 3-edge-colourings of C that agree with the colour of e (i.e. c(v j v j+1 ) = c(e) and c(v j v i ) = c(e)). There are exactly c 3 (C)/3 such colourings. Finally, we extend the edge colourings in all possible ways to G using the usual method. So, in this case, we obtain c

3 (G) ≤ 6 • c 3 (C)/3 • 2 n-2i+2j-2 2 = (c 3 (C)/2 i-j ) • 2 n/2
. In all cases, we have to bound the value c 3 (C) 2 i-j for 1 ≤ i < j. Since G has no 2-cycles, C has length at least 3, and so i -j ≥ 2. By Proposition 1, c 3 (G) = 2 i-j+1 + 2 if i -j is odd, and c 3 (G) = 2 i-j+1 -2 if i -j is even. Easily one sees that the value c 3 (C) 2 i-j is maximized when i -j = 3 (i.e. C has length four), and so c 3 (C) 2 i-j ≤ 18 8 = 9 4 . Thus c 3 (G) ≤ 9 4 • 2 n/2 .

Theorem 5 for k = 3 states that a connected cubic graph G has at most 3•2 n/2 3-edge-colourings. We shall now describe all connected cubic graphs attaining this bound.

Let G be a cubic graph and C = uvu be a 2-cycle in G. Then G/C is the graph obtained from G -{u, v} by adding an edge between the neighbour of u distinct from v and the neighbour of v distinct from u.

Let Θ be the graph with two vertices joined by three edges. And let L be the family of graphs defined recursively as follows:

• Θ ∈ L.

• if G has a 2-cycle C such that G/C is in L, then G is in L.

Remark that the 3-noodle necklaces N 3 n (with n even) belongs to the family L.

Proposition 7 .

 7 Let k ≥ 3 and n ≥ 2,

Theorem 9 .

 9 Let G be a connected cubic graph. If G ∈ L, then c 3 (G) = 3 • 2 n/2 . Otherwise c 3 (G) ≤ 9 4 • 2 n/2 .Proof. By induction on n, the result holding for simple graphs by Lemma 8 and for Θ because c 3 (Θ) = 6. Assume that n ≥ 4 and that G has a 2-cycle C = uvu. In any 3-edge-colouring of G, the edges not in C incident to u and v are coloured the same. Hence to each 3-edge-colouring c of G/C corresponds the two 3-edge-colourings of G that agrees with c on G -{u, v}. Hence c 3 (G) = 2c 3 (G/C).

Acknowledgement

The authors would like to thank their children for suggesting them some graph names.

* This work is supported by the French Agence Nationale de la Recherche under reference AGAPE ANR-09-BLAN-0159.

If G/C is in L, then G is also in L. Moreover, by the induction hypothesis,

If G/C is not in L, then G is not in L. Moreover, by the induction hypothesis, c 3 (G/C) ≤ 9 [START_REF] Björklund | Narrow sieves for parameterized paths and packings[END_REF] • 2 (n-2)/2 . So c 3 (G) ≤ 9 4 • 2 n/2 .

We have no example of cubic simple graphs admitting exactly 9 4 • 2 n/2 3-edge-colourings, and we believe that 9 4 could be replaced by a lower constant in the statement of Theorem 9. In fact, we conjecture that the maximum number of 3-edge-colourings of cubic simple graphs of order n is attained by some special graphs that we now describe.

For all n ≥ 2, n = 2p even, the hamster wheel H n is the cubic graph obtained from two cycles on p vertices C v = (v 1 , v 2 , . . . , v p , v 1 ) and C w = (w 1 , w 2 , . . . , w p , w 1 ) by adding the matching M = {v i w i : 1 ≤ i ≤ p}. This construction for a lower bound was proposed by Pyatkin as it is mentioned in [START_REF] Golovach | Colorings with few colors: counting, enumeration and combinatorial bounds[END_REF]. Proposition 10.

If the three colours appear on C v , then there is a unique 3-edge-colouring of H n extending φ. Indeed, to extend φ, the colours of the edges of M are forced. Since the three colours appear on C v , there are two edges of M which are coloured differently. Without loss of generality, we may assume that these two edges are consecutive, that is there exists i such that they are v j w j and v j+1 w j+1 . But then the colour of w j w j+1 must be equal to the one of v j v j+1 . Then, from edge to edge along the cycle, one shows that for all i, the colour of w i w i+1 is the one of v i v i+1 .

If only two colours appear on C v , then there are two 3-edge-colourings of H n extending φ. Indeed in this case, n is even and all the edges of M must be coloured by the colour not appearing on C v . So, there are two possible 3-edge-colourings of C w with the colours appearing on C v .

Hence the number of 3-edge-colourings of G is equal to the number of 3-edge-colourings of C v plus the number of 3-edge-colourings of C v in which two colours appear. If n/2 is odd, this last number is 0, and if n/2 is even, this number is 6. So, by Proposition 1,

For all n ≥ 2, n = 2p even, the Moebius ladder M n is the cubic graph obtained from a cycle on n vertices C = (v 1 , v 2 , . . . v n , v 1 ) by adding the matching M = {v i v i+p : 1 ≤ i ≤ p} (indices are modulo n).

Two edges e and f of the cycle C are said to be antipodal, if there exists 1

is said to be antipodal if c(e) = c(f ) for every pair (e, f ) of antipodal edges. Proposition 11. Let c be a 3-edge-colouring of M n . If c is not antipodal, then n/2 is odd and all the arcs v i v i+n/2+1 are coloured the same.

Proof. Suppose that two antipodal edges are not coloured the same. Without loss of generality, c(v n v 1 ) = 2 and c(v p v p+1 ) = 3, where n = 2p. Hence, we have c(v

And so on by induction, for all 1

Hence, the edges of C are coloured alternately with 2 and 3, Since c(v 2p v 1 ) = 2 and c(v p v p+1 ) = 3, p must be odd.

Proof. Clearly, there is a one-to-one mapping between the antipodal 3-edge-colourings of M n and the 3-edge-colourings of C n/2 . Hence, by Proposition 11, if n/2 is even, then

If n/2 is odd, non-antipodal 3-edge-colourings are those such that all arcs v i v i+n/2+1 are coloured the same, by Proposition 11. There are 6 such edge colourings (three choices for the colour of the edges v i v i+n/2+1 and for each of these choices, two possible edge colourings of C). Hence

We think that H n and M n are the connected cubic graphs which admit the maximum number of 3-edge-colourings. Precisely, we raise the following conjecture.

Conjecture 13. Let G be a connected cubic simple graph on n vertices. If n/2 is even, then

Total colouring

A total colouring of a graph G into k colours is a colouring of its vertices and edges such that two adjacent vertices receive different colours, two adjacent edges receive different colours and a vertex and an edge incident to it receive different colours. A total colouring with k colours is a k-total-colouring. For every graph G, let c T k (G) be the number of k-total-colourings of G. For each 4-edge-colouring c of a cubic graph G, there is at most one 4-total-colouring of G whose restriction to E(G) equals c. Indeed, the colours of the three edges incident to a vertex force the colour of this vertex. Hence if G is cubic, we have that c T 4 (G) ≤ c 4 (G). By the method described in the previous section, one can show that if G is 2-connected, then c 4 (G) = O(2 n/2 • 6 n/2 ), and so c T 4 (G) = O(2 n/2 • 6 n/2 ). We now obtain better upper bounds for c T 4 .

Theorem 14. Let G be a 2-connected subcubic graph. Then

Proof. Assume first that G is a cycle (v 1 , . . . , v n , v 1 ). Let us totally colour it greedily starting from v 1 . There are 4 possible colours for v 1 , and then 3 possible colours for v 1 v 2 . Afterwards for every i ≥ 2, there at most two possible colours for v i (the ones distinct from the colours of v i-1 and v i-1 v i ) and then at most two possible colours for v i v i+1 (the ones distinct from the colours of v i-1 v i and

. Assume now that G is not a cycle. Let s and t be two distinct vertices of degree 3. Consider an (s, t)-ordering v 1 , v 2 , . . . , v n of V (G), which exists by Lemma 3, and the orientation D of G according to this ordering. Then

A -) be the set of vertices of outdegree 2 (resp. indegree 2) in D and A 2 be the set of vertices of degree 2 in G. As in the proof of Theorem 4, we have |A 2 | = n -n 3 , and

Now for i = 1 to n -1, we enumerate the p i partial 4-total-colourings of vertices in {v 1 , . . . , v i } and arcs with tail in {v 1 , . . . , v i }. For i = 1, there are 4! = 24 such colourings, since v 1 and its three incident arcs must receive different colours.

For each 1 < i < n, when we extend the partial total colourings. Two cases may arise.

• If d - D (v i ) = 1, then there are two choices to colour v i and then two other choices to colour the (at most two) arcs leaving v i . Hence p i ≤ 4p i-1 .

• If d - D (v i ) = 2, then there are at most two choices to colour v i and then the colour of the arc leaving v i is forced since three colours are forbidden by v i and its two entering arcs. Hence

Finally, we need to colour v n . Since its three entering arcs are coloured its colour is forced (or it is impossible to extend the colouring).

Hence an easy induction shows that c

A leaf of a tree is a degree one vertex. A vertex of a tree which is not a leaf is called a node. A tree is binary if all its nodes have degree 3.

Proof. By induction on n, the results holding easily when n = 2, that is when T = K 2 . Suppose now that T has more than two vertices. There is a node x which is adjacent to two leaves y 1 and y 2 . Consider the tree T = T -{y 1 , y 2 }. By the induction hypothesis, c T 4 (T ) = 3 • 2 3(n-2)/2 . Now each 4-total-colouring of T may be extended into exactly eight 4-total-colourings of T . Indeed the two colours of x and its incident edge in T are forbidden for xy 1 and xy 2 , so there are two possibilities to extend the colouring to these edges, and then for each y i , there are two possible colours available. Hence

Proof. Let F be the subgraph induced by the cutedges of G. Then F is a forest. Consider a tree of F . It is binary, its leaves are in different non-trivial 2-connected components of G, and every node is a trivial 2-connected component of G.

A subgraph H of G is full if it is induced on G, connected and such that for every non-trivial 2-connected component C, H ∩ C is empty or is C itself and for every tree T of F , H ∩ T is empty, or is just one leaf of T or is T itself. Observe that a full subgraph has minimum degree at least 2.

We shall prove that for every full subgraph H, c T 4 (H) ≤ 3 • 2 2n(H)-n 3 (H)/2 . We proceed by induction on the number of 2-connected components of H. If H is 2-connected, then the result holds by Theorem 14.

Suppose now that H is not 2-connected. Then H contains a tree T of F . Let v 1 , . . . , v p be the leaves of T , e i , 1 ≤ i ≤ p the edge incident to v i in T and N the set of nodes of T . Then

Let c be a 4-total-colouring of T . It can be extended to H i by any 4-total-colouring of H i such that v i is coloured c(v i ) and the two edges incident to v i in H i are coloured in {1, 2, 3, 4} \ {c(v i ), c(e i )}. There are 1 12 c T 4 (H i ) such colourings because each of them correspond to exactly twelve 4-total colourings of H i obtained by permuting the colour of v i (there are 4 possibilities) and then the colour of e i (there are 3 possibilities). Hence each 4-total-colouring of T can be extended into p i=1 1 12 c T 4 (H i ) 4-total-colourings of H and so

Now by Proposition 15, T has 3 • 2 3n(T )/2 4-total-colourings, and since

As previously for the edge colourings of graphs, we derive from Theorem 16 an algorithm to enumerate all the 4-total-colourings of a cubic graph. The proof is similar to the one of Corollary 6.

Corollary 17. There is an algorithm to enumerate all the 4-total-colourings of a connected cubic graph on n vertices in time O * (2 3n/2 ) and polynomial space.

The bound of Theorem 16 is seemingly not tight. Indeed, in Theorem 14, the equation p i ≤ 2p i-1 when d - D (v i ) often overestimates p i , because there are two choices to colour v i only if the two colours appearing on its two entering arcs are the same two as the ones assigned to the tails of these arcs.

If not the colour of v i is forced or v i cannot be coloured.

Problem 18. What is c T 4 (n), the maximum of c T 4 (G) over all connected graphs of order n?

We shall now give a lower bound on c T 4 (n). A binary tree is nice if its set of leaves may be partitionned into pairs of twins, i.e. leaves at distance 2. Clearly, every nice binary tree T has an even number of leaves and thus n(T ) ≡ 2 mod 4. Moreover if n(T ) = 4p + 2, then T has 2p nodes and p + 1 pairs of twins. A noodle tree is a cubic graph obtained from a nice binary tree by adding two parallel edges between each pair of twins. Proof. Let X 1 , . . . , X p+1 be the pairs of twins of G, and let T be the binary tree G -p+1 i=1 X i . Let us label the leaves of T , y 1 , . . . , y p+1 such that for all 1 ≤ i ≤ p + 1, y i is adjacent to the two vertices of X i in G.

Every 4-total-colouring of T , may extended in exactly 4 ways to each pair of twins X i = {x i , x i } and their incident edges. Indeed, without loss of generality we may assume that y i is coloured 1 and its incident edge in T is coloured 2. Then the edges y i x i and y i x i must be coloured in {3, 4}, which can be done in two possible ways. For each of these possibilities, the parallel edges between x i and x i must be coloured in {1, 2}, which again can be done in two possible ways. Finally, we must colour x i (resp. x i ) with the colour of y i x i (resp. y i x i ).

Hence c 4 (G) = 4 p+1 • c 4 (T ), and so by Proposition 15, c 4 (G) = 3 • 2 5p+2 .