Printer Friendly

On BMRN*-colouring of planar digraphs.

1 Introduction

The colouring concepts studied in this work are motivated by the following real-life problem. Suppose we have a network of entities communicating via radio waves. One particular of our entities, the center of command, continuously, through time, emits messages that must be propagated to all the entities of the network. Because all entities might not be in the range of the center of command, these transmissions are performed in a multi-hop fashion. That is, for each entity (different from the center of command), a preferred entity is defined, from which the messages are intended to be received. Entities and their respective preferred entity define a set of links, which is commonly referred to as the network's backbone, along which the messages of the center of command will be propagated.

In an ideal world, an entity receiving a message from its preferred entity via its link would just forward the message right away to some close entities. In practice, however, this is not feasible due to particular types of physical rules and limitations. For instance, since messages are forwarded via radio waves, an entity a will not only receive messages from its preferred entity, but also from any other entity that has a in its range. In other words, interferences might occur, resulting in unexpected and unwanted alterations of messages.

In the TDMA method, this issue is overcome by dividing time into several successive units of time, called time slots, during which only some of the backbone links become active. The goal is then to design a scheduling of the links which will be repeated through time, and prevent interferences during transmissions. A downside of this method, however, is that links now become active during only a short period of time, i.e., during the time slot they are active. The main objective is thus to find a scheduling that minimizes the number of time slots, so that the waiting time of the links is minimized.

The problem above can be studied under a graph colouring formalism. The network is modelled by a digraph D whose vertices are the entities, while the presence of an arc (u,v) indicates that v is in the emission range of u. The backbone is modelled by a subdigraph B of D being a spanning subdigraph in which all connected components are out-trees, i.e., oriented trees with all arcs oriented from a root r (modelling a local center of command) towards the leaves. We call the pair (D, B) a backboned digraph, the arcs of B being the backbone arcs and the arcs in A(D) \ A(B) being the interference arcs. In case B is connected, i.e., its underlying undirected graph und(B) has only one connected component, we call (D, B) a spanned digraph. Since, in the problem above, we are assuming that the center of command is unique, the notion of spanned digraph is the precise one modelling our network context; however, the notion of backboned digraph is more general and will be of great use in most of our investigations in this paper.

A scheduling of the backbone links is modelled by an arc-colouring of the arcs of B verifying certain properties. In [3], Bensmail, Blanc, Cohen, Havet and Rocha introduced the notion of BMRN-colourings of backboned digraphs, which are arc-colourings [phi] that avoid the following two configurations:

* Direct conflict: two "consecutive" backbone arcs (u, v), (v, w) with [phi]((u, v)) = [phi]((v, w)).

* Indirect conflict: an interference arc ([u.sub.1], [u.sub.2]) such that ([u.sub.1], [u.sub.2]), ([u.sub.2], [u.sub.2]) are two backbone arcs with

[u.sub.1] = [u.sub.2] and [phi](([u.sub.1], [u.sub.1])) = [phi](([u.sub.2], [v.sub.1])).

Direct conflicts model the fact that, regarding the TDMA scheduling problem above, an entity v should not both receive and emit messages during a same time slot. This is because entities can be assumed to be very simple devices, that are not able to perform the actions of transmitting and receiving at the same time. Indirect conflicts model interferences due to some entities being in the range of other emitting entities: during a given time slot, an entity [v.sub.2] should not receive a message from both its preferred entity [u.sub.1] and another entity [u.sub.1] also sending a message.

For a backboned digraph (D,B), the least number of colours in a BMRN-colouring is called the BMRN-index of (D, B), denoted by BMRN(D, B). The authors of [3] also considered the following slightly modified variation: a BMRN*-colouring of (D, B) is a BMRN-colouring where it holds that, for every vertex v of D with [d.sup.+.sub.B] (v) > 1, all backbone arcs of B out-going from v are assigned the same colour. The BMRN*-index of (D, B) is then the least number of colours (denoted BMRN*(D, B)) in a BMRN*-colouring of (D,B). In the concrete network problem above, finding a BMRN* -colouring would be equivalent to finding a link scheduling where all entities send their messages during a unique time slot.

Refer to Figure 1 for an illustration of these concepts; in particular, note that the colouring on picture (a) is not a BMRN*-colouring, as the white vertex does not have all of its incident out-going backbone arcs assigned a same colour.

In [3], the authors gave a number of general results on both the BMRN-index and the BMRN*-index of digraphs. Note that BMRN(D, B) [less than or equal to] BMRN*(D, B) always holds. Although the authors proved that the BMRN* -index of a given spanned digraph can be arbitrarily larger than its BMRN-index, they observed that, at least for particular classes of digraphs, considering BMRN*-colourings can be a way to deduce optimal BMRN-colourings, which is a reason why this modified notion is worth studying. They also considered algorithmic aspects related to the problem of determining the BMRN-index or the BMRN* -index of a given spanned digraph, which in general is NP-hard, even if one is allowed to construct the backbone from a given root. Also, they gave a number of more specific results for particular classes of digraphs, such as bounded-degree digraphs, outerplanar digraphs, and more generally planar digraphs.

An interesting aspect of BMRN*-colouring is its connection with the notion of distance-2 colourings of undirected graphs, which are vertex-colourings where no two vertices at distance at most 2 are assigned the same colour. For an undirected graph G, we denote by [x.sub.2](G) the least number of colours in a distance-2 colouring of G. It was noticed in [3] that, for any backboned digraph (D, B), a distance-2 colouring [phi] of und(D) yields a BMRN*-colouring of (D, B) (by assigning, for every vertex v, colour [phi](v) to all its incident out-going backbone arcs); this is because having no two adjacent vertices receiving the same colour by [phi] takes care of direct conflicts, while having no two vertices at distance 2 receiving the same colour takes care of indirect conflicts. Then, BMRN* (D, B) [less than or equal to] [x.sub.2] (und(D)). Although these two chromatic parameters seem related, there are actually cases where they differ a lot. A good illustration is the case of planar graphs: while x2(G) is bounded below by [DELTA](G) + 1 for every (planar) graph G, we have BMRN*(D, B) [less than or equal to] 8 for every planar backboned digraph (D, B) (see below). This phenomenon is quite intriguing, and it motivates one of our aims in this work, which is to further understand BMRN*-colourings.

The current paper is devoted to investigating further the case of planar digraphs, more precisely the behaviour of the BMRN*-index for these digraphs, as many questions raised in [3] remain open to date. Focusing further on this class of digraphs is motivated by the central role they play in colouring problems, and by the fact that, regarding the practical problem introduced earlier, planar digraphs stand as a rather realistic class to consider. Making use of the Four-Colour Theorem [1, 2], the authors of [3] proved that for every planar backboned digraph (D, B), we have BMRN*(D, B) [less than or equal to] 8. They also noticed that there exist planar spanned digraphs (D, T)(i) with BMRN* (D, T) = 7, such as that one depicted in Figure 2. An interesting property of this example is that its backbone is a directed path; on the one hand, this implies that even BMRN(D, T) = 7 holds, while, on the other hand, it illustrates the fact that, even in a planar backboned digraph, having a simple backbone topology does not prevent the BMRN-index and BMRN*-index from being relatively large. Yet, the authors left open the question of whether their upper bound is tight or not.

Question 1.1 ([3]). Do we have BMRN(D, T) [less than or equal to] 7 for every planar spanned digraph (D, T)? Similarly, do we always have BMRN* (D, T) [less than or equal to] 7?

As a first result in this paper, we answer negatively to Question 1.1 by exhibiting, in Section 2, a planar spanned digraph (D, T) verifying BMRN(D, T) = BMRN*(D, T) = 8. This shows that the upper bound above is tight.

We then consider algorithmic aspects in Section 3. In [3], the authors proved that deciding whether BMRN*(D, B) [less than or equal to] 3 (and similarly BMRN(D, B) [less than or equal to] 3) holds for a given planar backboned digraph (D,B) is NP-hard, even when restricted to planar spanned digraphs. As mentioned earlier, we know that the BMRN-index and BMRN*-index of a planar backboned digraph can be as large as 8. Thus, it makes sense investigating, for such a planar backboned digraph (D,B), the complexity of deciding whether BMRN*(D, B) [less than or equal to] k (and similarly BMRN(D, B) [less than or equal to] k) for k [member of] {4,.., 7}.

Question 1.2 ([3]). For every k [member of] {4, 5, 6,7}, what is the complexity of the Planar k-BMRN*-Colouring problem? What is that of the Planar k-BMRN-Colouring problem?

Towards Question 1.2, we prove that deciding whether BMRN* (D, B) < k holds for a given planar back-boned digraph (D, B) is NP-hard for every k [member of] {4,..., 6}, even when restricted to planar spanned digraphs.

For a planar backboned digraph, the BMRN*-index can be as large as 8. In all our extremal examples (such as those in Figure 2 and upcoming Figure 3) we note that small cycles are one of the main reasons why the number of needed colours is that high. Thus, it seems judicious to investigate the behaviour of the BMRN*-index of planar backboned digraphs when small cycles are excluded, which is a classical aspect in graph colouring theory. Consequently, Section 4 is devoted to investigating the effects of a large girth on the BMRN*-index of a planar backboned digraph.

Conclusions and perspectives are gathered in Section 5.

Definitions, notation and terminology

An undirected graph H is a minor of another undirected graph G if H can be obtained from G by deleting edges, deleting vertices, and contracting edges.

For a given digraph D, we denote by V(D) and A(D) its vertex and arc sets, respectively. The in-degree (resp. out-degree) [d.sup.-.sub.D](v) (resp. [d.sup.+.sub.D](v)) of a vertex v of D is the number of in-coming (resp. out-going) arcs incident to v. The subscript in this notation will be omitted whenever no ambiguity is possible. The minimum in-degree (resp. minimum out-degree) [delta]~(D) (resp. [delta]+(D)) of D is the minimum in-degree (resp. out-degree) over the vertices of D. Conversely, the maximum in-degree (resp. maximum out-degree) [DELTA]- (D) (resp. [DELTA]+ (D)) of D is the maximum in-degree (resp. out-degree) over the vertices of D.

Abusing notions and notations, we voluntarily employ some terms or notations usually defined for undirected graphs in the context of digraphs. Whenever we do so for a digraph D, it should be understood that we are referring to und(D), the undirected graph underlying D. In particular, we consider that D is connected as soon as und(D) is. The degree d(v) of a vertex v of D is its degree in und(D). The maximum degree [DELTA](D) of D is the maximum degree of und(D). We say Displanarifund(D) itself is planar. Given a planar embedding of D in the plane, we denote by F(D) the set of the faces of D. The degree d(f) of a face f is the length of a shortest walk enclosing f (in particular, if f is incident to a pendant arc, then that arc is counted twice). The girth g(D) of D is the girth of und(D), which is the length of its smallest cycles.

In turn, whenever referring to a digraph notion or notation for a backboned digraph (D, B), we implicitly refer to the corresponding notion or notation for D.

2 Planar spanned digraphs with BMRN-index 8

Answering Question 1.1 negatively, we point out that there exist planar spanned digraphs with BMRN-index (and BMRN*-index) 8. Thus, according to the upper bound exhibited in [3], the maximum value of BMRN(D, T) (and BMRN*(D, T)) over all planar spanned digraphs (D, T) is 8. Our result is built upon the following straight observation:

Observation 2.1. Let (D, B) be a backboned digraph. For every backboned surdigraph (D1, B') (i.e., V(D') = V(D) and A(D) [??] A(D')), we have BMRN(D, B) < BMRN(D', B') and BMRN* (D, B) < BMRN* (D1, B').

Observation 2.1 is obvious, as adding backbone arcs or interference arcs to a backboned digraph cannot make its BMRN-index and BMRN* -index decrease.

Now consider the planar backboned digraph depicted in Figure 3.

Observation 2.2. The backboned digraph depicted in Figure 3 is a planar backboned digraph with BMRN-index 8.

Proof: As shown via the embedding depicted in the figure, this backboned digraph (D,B) is indeed planar. The backbone B has exactly eight arcs, and it can be checked that no two of them can be assigned the same colour by a BMRN-colouring, either because they are incident to a same vertex or because of an interference arc. In particular, for every backbone arc (u, v), we have precisely [d.sup.-.sub.B](u) + [d.sup.+.sub.D-A(B)] (u) + [d.sup.+.sub.B](v) + [d.sup.-.sub.D-A(B)](v) = 7. Thus, BMRN(D, B) = 8.

Theorem 2.3. There exist planar spanned digraphs with BMRN-index 8.

Proof: Consider the planar backboned digraph in Figure 3 (which has BMRN-index 8 by Observation 2.2). It can easily be turned into a planar spanned digraph by adding, for instance, a backbone arc from [v.sub.2] to [v.sub.6], and a backbone arc from [v.sub.2] to [v.sub.9]. Since, in the depicted embedding, [v.sub.2] and [v.sub.6] belong to a common face, and similarly [v.sub.2] and [v.sub.9] belong to a common face, adding these two arcs does not break planarity. Then the backbone becomes an out-tree with root [v.sub.1]. By Observation 2.1 the resulting planar spanned digraph retains BMRN-index at least 8. The equality follows from the upper bound in [3].

3 On the complexity of Planar k-BMRN*-Colouring

Throughout this section, for any k [greater than or equal to] 1 the k-BMRN*-Colouring problem refers to the problem where, given a backboned digraph (D, B), the task is to determine whether BMRN*(D, B) [less than or equal to] k. The Planar k-BMRN*-Colouring problem is the restriction of k-BMRN*-Colouring to planar backboned digraphs.

In [3], the authors noticed that k-BMRN*-Colouring is equivalent to the usual k-Colouring problem (where one aims at deciding, for a given undirected graph G, whether x(G) [less than or equal to] k, i.e., whether G admits proper k-vertex-colourings), and is thus polynomial-time solvable for k = 1, 2, and NP-hard for every k [greater than or equal to] 3 even when restricted to spanned digraphs. Regarding Planar k-BMRN*-Colouring, they proved that Planar 3-BMRN*-Colouring is also NP-hard, even when restricted to planar spanned digraphs. As seen previously in Section 2, planar spanned digraphs can have BMRN*-index as large as 8, and it thus makes sense wondering about those digraphs with BMRN*-index exactly k for every k [member of] {4,..., 7} (recall Question 1.2).

3.1 Auxiliary tools, and main result

The complexity results above were established using the following construction (illustrated in Figure 4). Given an oriented graph G, let ([D.SUB.G], [M.sub.G]) be the backboned digraph obtained from G as follows:

* For every vertex a of G, add a backbone arc ([u.sub.a], [v.sub.a]) to [M.sub.G], where [u.sub.a], [v.sub.a] are two new vertices.

* For every arc (a, b) of G, add the interference arc ([u.sub.a], [v.sub.b]) to A([D.sub.G]) \ A([M.sub.G]).

We call the resulting backboned digraph ([D.sub.G], [M.sub.G]) the matched digraph associated to G. Every vertex of G corresponds to a backbone arc of ([D.SUB.G], [M.sub.G]), while every arc of G corresponds to an interference arc of ([D.SUB.G], [M.sub.G]). There is then a straight equivalence between finding a proper k-vertex-colouring of und(G) and a k-BMRN*-colouring of ([D.sub.G], [B.sub.G]).

Observation 3.1. For every oriented graph G, we have x(und(G)) = BMRN* ([D.sub.G], [M.sub.G]).

Note that ([D.SUB.G], [B.sub.G]) can be far from planar, in particular if G itself is far from planar. The other way around, the authors of [3] proved that, given that G is an oriented graph with orientation properties inherited from a particular planar drawing, also ([D.SUB.G], [B.sub.G] ) is planar. Because the Planar 3-Colouring problem is NP-hard [5], this implies that Planar 3-BMRN-Colouring is NP-hard. A simple connecting operation, to be described later, implies that this problem remains NP-hard for planar spanned digraphs as well.

Since all planar graphs are 4-colourable [1, 2], the same arguments cannot be used to prove that Planar k-BMRN*-Colouring is NP-hard for any k > 3, as it would require the corresponding Planar k-Colouring problem to be NP-hard. To overcome this point, we come up with an improved reduction scheme, which allows us to establish the NP-hardness of Planar k-BMRN*-Colouring for every k [member of] {3,4,5,6}, even when restricted to planar spanned digraphs. This is by means of an adaptation of the so-called crossover gadgets, which were, to the best of our knowledge, first used by Garey, Johnson and Stockmeyer to establish the NP-hardness of the Planar 3-Colouring problem [5]. Crossover gadgets are graphs with certain colouring properties that can be used to "replace" edge crossings in a non-planar embedding of a graph, while preserving the k-colourability of the whole graph.

Before defining what is a crossover gadget in our context, we first need to introduce a particular way to draw a matched digraph defined over an acyclic oriented graph. Let G be an acyclic orientation of an undirected graph G. This orientation defines an ordering [w.sub.1],..., [w.sub.n] of the vertices of G, such that all arcs are directed "to the right" (i.e., if ([w.sub.i], [w.sub.j]) is an arc, then i < j). We now consider the matched digraph ([D.SUB.G], [M.sub.G]) associated to G, which we here draw in the plane in a specific way (see Figure 5), which we call a good drawing. For every i [member of] {1,..., n}, let us assume ([u.sub.i], [v.sub.i]) denotes the backbone arc of ([d.sub.G], [M.sub.G]) associated to vertex wi of G. We first draw ([u.sub.1],[v.sub.1]) vertically, having some length l. We then draw ([u.sub.2], [v.sub.2]) vertically too, of length ;, but positioned at some horizontal distance x to the right of ([u.sub.1], [v.sub.1]) and at some vertical distance x above ([u.sub.1],[v.sub.1]). We draw all ([u.sub.i],[v.sub.i])'s this way, i.e., each ([u.sub.i],[v.sub.i]) is drawn vertically, of length l, positioned at horizontal distance x to the right of ([u.sub.i-1], [v.sub.i-1]) and at vertical distance x above ([u.sub.i-1],[v.sub.i-1]).

We now draw the interference arcs. By the orientation G, for every arc ([w.sub.i], [w.sub.j]) of G, we want to add to ([D.sub.G], [M.sub.G]) an interference arc ([u.sub.i], [v.sub.j]), where [v.sub.j] is located somewhere above and at the right of [u.sub.i]. We draw this interference arc ([u.sub.i], [v.sub.j]) in the following way: We make the arc leave [u.sub.i] from the right, then immediately go vertically until the altitude of [v.sub.j] is attained, and then going straight horizontally to [v.sub.j]. Note that this way we may have lots of arc crossings involving at least three arcs, and many pairs of interference arcs intersecting on more than just one point. However, we can make the interference arcs go to their destination in a clean way, as follows (see Figure 5). For every two interference arcs ([u.sub.i], [v.sub.j]) and ([u.sub.i], [v.sub.j].) out-going from [u.sub.i], we make them leave [u.sub.i] with different angles so that they do not intersect and there is some horizontal "delay" before they start going vertically, in a non-intersecting parallel way. This delay, to avoid any crossing involving these two arcs, is as follows: if j < k, i.e., the destination of ([u.sub.i], [v.sub.k]) is farther to the right than that of ([u.sub.i], [v.sub.j]), then we grant more horizontal delay to ([u.sub.i], [v.sub.j]), as this arc will stop its ascension and "turn" right first. Reversely, we do not make every two interference arcs ([u.sub.i], [v.sub.j],), ([u.sub.i], [v.sub.j],), both supposed to reach [u.sub.k]., attain [v.sub.k]. following a same horizontal line. Instead, assuming i < j, i.e., [u.sub.i] is somewhere on the left of [u.sub.j], we add some vertical delay to ([u.sub.i], [[u.sub.k]) to the moment it stops its ascension and turns right.

By this good drawing of ([D.sub.G], [M.sub.G]), all interference arcs are drawn following an "S" shape, and it is thus easy to see that all [u.sub.i]'s lie on the "outer face" (to be more formal, in the digraph obtained by replacing all arc crossings by dummy vertices). Also, all arc crossings are perpendicular, involve exactly two interference arcs originating from different vertices, and the intersection between any two interference arcs (if any) is a single point.

Let us now define what a crossover gadget is. In our context, a k-crossover gadget (for some k [greater than or equal to] 3) will be a backboned digraph (D,B) with the following properties:

1. B has four particular pending corner arcs e, e', f, f' (i.e., they are each incident to a degree-1 vertex), were e, e' (and similarly f, f') are said to be opposite.

2. D has planar embeddings such that all of e, e', f, f' have both their sides being incident to the outer face, and, as going along the outer face, no two opposite corner arcs appear consecutively (i.e., the sequence of appearance must be e, f, e', f', or reversely).

3. In every k-BMRN* -colouring [phi] of (D, B), we have [phi](e) = [phi](e') and [phi](f) = [phi](f').

4. There exist k-BMRN*-colourings [phi] of (D, B) where [phi](e) = [phi](e') = [phi](f) = [phi](f'). Also, there exist k-BMRN*-colourings [phi] of (D, B) where [phi](e) = [phi](e') = [phi](f) = [phi](f').

Such gadgets will be used in the following way (see Figure 6). Assume we have a non-planar matched digraph (D, M) that we want to k-BMRN*-colour. To ease the following explanations, let us consider a good drawing of (D, M) on the plane. As pointed out earlier, all arc crossings involve two interference arcs crossing perpendicularly, and originating from different vertices. Furthermore, no three arcs cross on a same point, and the intersection (if any) between any two arcs is a point. Let us now consider every interference arc ([u.sub.a], [v.sub.b]) in turn (as in the definition of matched digraphs, for convenience we here write all backbone arcs of (D, M) under the form ([u.sub.a], [v.sub.a])). Since ([u.sub.a], [v.sub.b]) is an interference arc, it means that ([u.sub.a], [v.sub.a]) and ([u.sub.b], [v.sub.b]) are backbone arcs, drawn vertically by assumption. Let us now go along ([u.sub.a], vb), from [u.sub.a] towards [v.sub.b]. Each time we encounter an arc crossing (involving ([u.sub.a], [v.sub.b])), let us add to the backboned digraph a copy of ([u.sub.a], [v.sub.a]), being a new backbone arc ([u'.sub.a], [v'.sub.a]) drawn vertically in such a way that [u'.sub.a] is located on ([u.sub.a], [v.sub.b]) right after the crossing, before the next crossing involving ([u.sub.a], vb) (if any), and before [v.sub.b]. Free to make (u'a, v'a) as small as desired, we might assume that this new backbone arc does not intersect anything (with the exception of its tail lying on ([u.sub.a], [v.sub.b]) at the moment).

We perform this transformation for all interference arcs of (D, M), resulting in an auxiliary backboned digraph (D', M') (Figure 6 (b)). For every original backbone arc ([u.sub.a], [v.sub.a]) of (D, M) and each interference arc ([u.sub.a], [v.sub.b]) out-going from [u.sub.a], we have thus added x copies of ([u.sub.a],[v.sub.a]) to the digraph, where x denotes the number of arc crossings in which ([u.sub.a], vb) was involved. There are thus a certain number of copies of ([u.sub.a], [v.sub.a]) in (D', M'), including the original copy of ([u.sub.a], [v.sub.a]), that are "surrounding" the crossings (meaning that, for every interference arc ([u.sub.a], [v.sub.b]) that is crossed, there is a copy of ([u.sub.a], [v.sub.a]) lying on ([u.sub.a], [v.sub.b]) before and after every arc crossing involving ([u.sub.a], [v.sub.b])).

Let us now modify (D, M') further. To each arc crossing of (D, M) involving two interference arcs ([u.sub.a], vb) and ([u.sub.c], vd), we associate, in (D', M'), four "surrounding" backbone arcs, being, as going from [u.sub.a] to [u.sub.b] , the copy of ([u.sub.a], [v.sub.a]) located before the crossing and the copy of ([u.sub.a], [v.sub.a]) located after the crossing, and, as going from [u.sub.c] to vd, the copy of ([u.sub.c], [v.sub.c]) located before the crossing and the copy of ([u.sub.c], [v.sub.c]) located after the crossing. We are now ready to get rid of the conflicts of (D, M). In (D, M'), remove all interference arcs that are, in (D, M), involved in arc conflicts. Then, for every arc crossing of (D, M) that involves two interference arcs ([u.sub.a], vb) and ([u.sub.c], vd), add, in (D', M'), a new k-crossover gadget where the crossing was occurring, and embed that gadget in such a way that its four corner arcs fully lie in the face surrounding the gadget, and so that no two opposite corner arcs appear consecutively in that face. Next, identify two opposite corner arcs of the gadget with the two copies of ([u.sub.a], [v.sub.a]) associated to the crossing, and identify the two other opposite corner arcs with the two copies of ([u.sub.c], [v.sub.c]) associated to the crossing (Figure 6 (c)). Once this has been done for all arc crossings, finally consider every interference arc ([u.sub.a], vb) that is involved in some crossings in (D, M), and, denoting ([u'.sub.a], [v'.sub.a]) the last copy of ([u.sub.a], [v.sub.a]) (as going from [u.sub.a] to vb) in (D', M'), add the interference arc ([u'.sub.a], vb) to (D', M') (Figure 6 (d)). Assuming we do have a k-crossover in hand, we denote by UC(D, M) the backboned digraph obtained from (D, M) in this way, where that k-crossover gadget is implicitly used to replace the arc crossings.

We now prove that, assuming we do have a k-crossover gadget, using it to construct UC(D, M) from (D, M) results in UC(D, M) having the desired properties.

Proposition 3.2. Let (D, M) be a matched digraph drawn in a good way, and assume we have a k-crossover gadget for some k > 3. Then, the backboned digraph (D', M') = UC(D, M), constructed as described above using copies of that gadget, admits a planar embedding. Furthermore, BMRN*(D, M) < k ifandonlyifBMRN*(D',M') < k.

Proof: The first part of the claim follows from arguments used to describe the construction of UC(D, M). When adding to (D, M') the backbone arcs that will later become the corner arcs of the crossover gadgets, we note that, by how these arcs are positioned, when removing all interference arcs involved in arc crossings we get a planar digraph. Adding the gadgets does not create new arc crossings, as these gadgets admit planar embeddings with their four corner arcs being fully in the outer face (by definition), and, when identifying their corner arcs to four existing arcs, we can "shape" the gadget so that it is roughly drawn like the arc crossing it is locally replacing. This way, we make sure that no arc of the gadget is involved in a new arc crossing.

We now focus on proving the last part of the statement.

* First assume that we have a k-BMRN*-colouring [phi] of (D, M). We derive one [phi]' of (D, M'). For every backbone arc ([u.sub.a], [v.sub.a]) of (D, M), we set [phi]'(([u.sub.a], [v.sub.a])) = [phi](([u.sub.a], [v.sub.a])). Now, for every other copy ([u'.sub.a],[v'.sub.a]) of ([u.sub.a],[v.sub.a]) in (D',Mr), we set [phi]'(([u'.sub.a],[v'.sub.a])) = [phi](([u.sub.a],[v.sub.a])). Note that this does not create any indirect conflict involving two backbone arcs (a, b) and (c, d), via, say, the interference arc (a, d). Indeed, either (a, b) and (c, d) both belong to (D, M), in which case (a, d) also does and we have [phi]((a, b)) = [phi]((c, d)), an indirect conflict that is a contradiction to the definition of [phi]. Otherwise, we have, say, that (a, b) is actually a copy of an original backbone arc (a', b'). By the existence of (a, d), we deduce that, in (D, M), there is an interference arc (a', d), which is involved in arc crossings that resulted in the addition of (a, b) to (D', M'). By construction of [phi]', we have [phi]'((a', b')) = [phi]'((a, b)), while, if (a, b) and (c, d) are in conflict, [phi]'((a, b)) = [phi]'((c, d)). Thus, we have [phi]((a', b')) = [phi]((c, d)), while (a', d) exists in (D, M), which is an indirect conflict by [phi]. This is a contradiction.

The only backbone arcs of (D', M') that remain to be coloured are those of the k-crossover gadgets. Consider such a gadget in (D',M'), where ([u'.sub.a],[v'.sub.a]), ([u.sub.a],[v.sub.a]) and ([u'.sub.b],[v'.sub.b]), ([u'.sub.b],[v".sub.b]) are the two pairs of opposite corner arcs, being copies of some original backbone arcs ([u.sub.a], [v.sub.a]) and ([u.sub.b], [v.sub.b]), respectively, of (D,M). By construction of [phi]' so far, we have [phi]'(([u'.sub.a],[v'.sub.a])) = [phi]'(([u".sub.a],[v"a])) and [phi]'(([u'.sub.b], [v'.sub.b])) = [phi]'(([u'.sub.b],[v'.sub.b])). By the definition of a k-crossover gadget, [phi]' can be extended to the gadget provided each pair of its opposite corner arcs are assigned the same colour, which is the case here. Thus, [phi]' can be extended to all gadgets used to construct (D', M'), which thus admits [phi]' as a k-BMRN* -colouring.

* Now assume that we have a k-BMRN*-colouring [phi]' of (D', M'), which we wish to extend to one [phi] of (D, M). Every backbone arc ([u.sub.a],[v.sub.a]) of (D, M) also exists in (D', M'); then we simply set [phi](([u.sub.a],[v.sub.a])) = [phi]'(([u.sub.a],[v.sub.a])). Now consider, in (D,M), two backbone arcs ([u.sub.a],[v.sub.a]) and ([u.sub.b],vb) such that ([u.sub.a],[v.sub.b]) is an interference arc. If that interference arc is also present in (D', M'), then we have [phi]'(([u.sub.a], [v.sub.a])) [not equal to] [phi]'(([u.sub.b], vb)) and so, by [phi], the backbone arcs ([u.sub.a], [v.sub.a]) and ([u.sub.b], [v.sub.b]) are not involved in an indirect conflict. Now, if ([u.sub.a], vb) is not an interference arc of (D', M'), then it must be that this arc is involved in arc crossings in (D, M). By construction, there is a copy ([u'.sub.a],[v'.sub.a]) of ([u.sub.a], [v.sub.a]) in (D', M') (located right after the last arc crossing involving ([u.sub.a],[v.sub.b]) in (D, M)) such that ([u'.sub.a],[v.sub.b]) is an interference arc (replacing ([u.sub.a],[v.sub.b])). Then [phi]'(([u'.sub.a],[v'.sub.a])) = [phi]'(([u.sub.b],vb)). By the definition of a k-crossover gadget, we have [phi]'(([u.sub.a], [v.sub.a])) = [phi]'(([u'.sub.a], [v'.sub.a])). From this, we deduce that [phi](([u.sub.a], [v.sub.a])) = [phi](([u.sub.b], [v.sub.b])), and that there cannot be indirect conflicts by [phi].

This concludes the proof.

We now show how to deduce the NP-hardness of Planar k-BMRN*-Colouring from the previous results and observations (assuming a k-crossover gadget exists).

Theorem 3.3. For any k [greater than or equal to] 3, ifk-crossover gadgets exist, then Planar k-BMRN* -Colouring is NP-hard.

Proof: The proof is by reduction from the k-COLOURING problem, which is NP-hard for any k [greater than or equal to] 3. Let G be an undirected graph; we build a planar backboned digraph (D, B) such that G admits a proper k-vertex-colouring if and only if (D, B) admits a k-BMRN*-colouring.

Let G be an acyclic orientation of G (obtained, for instance, by labelling the vertices [v.sub.1],... ,[v.sub.n] and orienting every edge towards the vertex with the largest index), and let ([D.sub.G], [M.sub.G]) be the matched digraph of G. Consider a good drawing of ([D.sub.G], [M.sub.G]), and, from it, build (D,B) the backboned digraph UC([D.sub.G], [M.sub.G]) obtained from ([D.sub.G], [M.sub.G]) by removing arc crossings using copies of a k-crossover gadget. Note that the whole construction is achieved in polynomial time; in particular, by the properties of a good drawing of a matched digraph, at most a quadratic number of k-crossover gadgets must be used to get rid of all arc crossings.

By Proposition 3.2, (D, B) is planar. Furthermore, it preserves the BMRN*-colourability of ([D.SUB.G], [M.sub.G]), while, in ([D.sub.G], [M.sub.G]), finding a k -BMRN*-colouring is equivalent to finding a proper k-vertex-colouring of G (Observation 3.1). Thus, G admits aproper k-vertex-colouring if and only if (D, B) admits a k-BMRN*-colouring.

In what follows, we prove that a 6-crossover gadget exists. At the end of this section, we will show how, from that gadget, we can derive k-crossover gadgets for any k [member of] {3,4, 5}.

3.2 A 6-crossover gadget

The 6-crossover gadget we exhibit is made of several pieces with particular colouring properties, which we introduce little by little to ease the understanding.

The core of our 6-crossover gadget is the backboned digraph depicted in Figure 7. From now on, we deal with its vertices and arcs using the terminology from the figure. Its backbone arcs ([f.sub.1], [f.sub.2]), ([f.sub.3], [f.sub.4]), ([f.sub.5], [f.sub.6]), ([f.sub.7], [f.sub.8]) are the peripheral arcs. Its main property of interest is the following one:

Proposition 3.4. Let (D, B) be the backboned digraph depicted in Figure 7. In every 6-BMRN*-colouring [phi] of(D, B), we have [phi](([f.sub.1], [f.sub.2])) = [phi](([f.sub.5], [f.sub.6])) = [phi] (([f.sub.3], [f.sub.4])) = [phi](([f.sub.7], [f.sub.8])).

Proof: Let [phi] be a 6-BMRN*-colouring of (D, B). To avoid a direct conflict, we must have [phi](([e.sub.1], [e.sub.2])) = [phi](([e.sub.2], [e.sub.3])). Similarly, no two of the arcs ([a.sub.1], [a.sub.2]), ([a.sub.2], [a.sub.3]), ([a.sub.3], [a.sub.4]), ([a.sub.4],a5) can be assigned the same colour: either to avoid a direct conflict (case of two consecutive arcs), or an indirect conflict (otherwise). Furthermore, the colour of ([e.sub.1], [e.sub.2]) cannot be assigned to any ([a.sub.i], [a.sub.i+1]) of these four arcs because of the interference arc ([a.sub.i], [e.sub.2]), while the colour of ([e.sub.2], [e.sub.3]) cannot be assigned to (ai, ai+1) because of the interference arc ([e.sub.2], ai+1). Thus, all six arcs ([e.sub.1], [e.sub.2]), ([e.sub.2], [e.sub.3]), ([a.sub.1], [a.sub.2]), ([a.sub.2], [a.sub.3]), ([a.sub.3], [a.sub.4]), ([a.sub.4], [a.sub.5]) are assigned different colours by [phi]. Now, we note that none of the colours of ([a.sub.1], [a.sub.2]), ([a.sub.2], [a.sub.3]), ([a.sub.3], [a.sub.4]), ([a.sub.4], [a.sub.5]) can be assigned to ([f.sub.1], [f.sub.2]), because of the four interference arcs joining these arcs. A consequence is that [phi](([f.sub.1], [f.sub.2])) [member of] {[phi](([e.sub.1], [e.sub.2])), [phi](([e.sub.2], [e.sub.3]))}.

Repeating these arguments for the arcs ([f.sub.3], [f.sub.4]), ([f.sub.5], [f.sub.6]), ([f.sub.7], [f.sub.8]), we get that each of the arcs ([f.sub.1], [f.sub.2]), ([f.sub.3], [f.sub.4]), ([f.sub.5],[f.sub.6]), ([f.sub.5],[f.sub.6]) must be assigned a colour from {[phi](([e.sub.1], [e.sub.2])), [phi](([e.sub.2],[e.sub.3]))}. Because of the interference arcs ([f.sub.1], [f.sub.8]), ([f.sub.3], [f.sub.2]), ([f.sub.5], [f.sub.4]), ([f.sub.7], [f.sub.6]), we must have [phi](([f.sub.1], [f.sub.2])) [not equal to] [phi] (([f.sub.3], [f.sub.4])) [not equal to] [phi](([f.sub.5], [f.sub.6])) [not equal to] [phi](([f.sub.7], [f.sub.8])). Thus, we must have [phi](([f.sub.1], [f.sub.2])) = [phi](([f.sub.5], [f.sub.6])) = [phi] (([f.sub.3], [f.sub.4])) = [phi](([f.sub.7], [f.sub.8])).

Our 6-crossover gadget will also be made of towers, being copies of the backboned digraph depicted in Figure 8. Again, from now on we refer to its vertices and arcs using the terminology in the figure. The backbone arcs ([i.sub.3],[i.sub.4]), ([i.sub.4], [i.sub.5]), ([g.sub.3], [g.sub.4]), ([g.sub.4], [g.sub.5]) are its four left-side arcs, while the backbone arcs ([i.sub.1], [i.sub.2]), ([i.sub.2], [i*.sub.2]), ([g.sub.1], [g.sub.2]), ([g.sub.2], [g.sub.2]) are its four right-side arcs. Its backbone arc ([f.sub.1], [f.sub.2]) is the base arc. It has the following properties:

Proposition 3.5. Let (D, B) be the backboned digraph depicted in Figure 8. In every 6-BMRN* -colouring [phi] of(D, B), we have:

1. all of ([g.sub.1], [g.sub.2]), ([g.sub.2], [g.sub.3]), ([g.sub.3], [g.sub.4]), ([g.sub.4],g5) have different colours by [phi], and similarly for all of([i.sub.1], [i.sub.2]), ([i.sub.2], [i.sub.3]), ([i.sub.3], [i.sub.4]), ([i.sub.4], [i.sub.5]);

2. {[phi](([g.sub.1], [g.sub.2])), [phi](([g.sub.2], [g.sub.3])), [phi](([g.sub.3], [g.sub.4])), [phi] (([g.sub.4], g5))} = {[phi](([i.sub.1], [i.sub.2])), [phi](([i.sub.2], [i.sub.3])), [phi](([i.sub.3], [i.sub.4])), [phi](([i.sub.4], [i.sub.5]))};

3. all of ([g.sub.1], [g.sub.2]) , ([g.sub.2] , [g.sub.3]), ([i.sub.1], [i.sub.2]), ([i.sub.2], [i.sub.3]) have different colours by [phi], and similarly for all of ([g.sub.3], [g.sub.4]), ([g.sub.4],[g.sub.5]), ([i.sub.3],[i.sub.4]), ([i.sub.4],[i.sub.5]);

4. [phi](([f.sub.1], [f.sub.2])) [member of] {[phi](([g.sub.1], [g.sub.2])), [phi](([g.sub.2], [g.sub.3])), [phi](([g.sub.3], [g.sub.4])), [phi](([g.sub.4], [g.sub.5]))}.

Proof: The first item is because no two arcs from these sets of four arcs can have the same colour by [phi], either because they are consecutive (direct conflict), or because they are joined by an interference arc (indirect conflict).

The second item is because [phi](([h.sub.1], [h.sub.2])) and [phi](([h.sub.2], h3)) must differ from all of [phi](([g.sub.1], [g.sub.2])), [phi](([g.sub.2],[g.sub.3])), [phi](([g.sub.3],[g.sub.4])), [phi](([g.sub.4], [g.sub.5])), and similarly [phi](([h.sub.1], [h.sub.2])) and[phi](([h.sub.2], h3)) must be different from all of [phi](([i.sub.1],[i.sub.2])), [phi](([i.sub.2], [i.sub.3])), [phi](([i.sub.3], [i.sub.4])), [phi](([i.sub.4], i5)). This is because of all interference arcs between [h.sub.1],[h.sub.2], h3 and these eight arcs. Thus, by the first item, [phi](([g.sub.1], [g.sub.2])), [phi](([g.sub.2],[g.sub.3])), [phi](([g.sub.3],[g.sub.4])), [phi](([g.sub.4], [g.sub.5])) are four different colours, and [phi](([h.sub.1], [h.sub.2])), [phi](([h.sub.2], h3)) are the last two colours. All of [phi](([i.sub.1], [i.sub.2])), [phi](([i.sub.2], [i.sub.3])), [phi](([i.sub.3], [i.sub.4])), [phi](([i.sub.4], [i.sub.5[)) must be distinct colours (still by the first item), and must be different from [phi](([h.sub.1],[h.sub.2])),[phi](([h.sub.2], [h.sub.3])).

The third item is because of the four interference arcs ([g.sub.2], [i.sub.2]), ([g.sub.2], [i.sub.2]), ([i.sub.2],[g.sub.2]), ([i.sub.1], [g.sub.2]). These interference arcs force the four colours [phi](([g.sub.2], [i.sub.2])), [phi](([g.sub.2], [i.sub.2])), [phi](([i.sub.2], [g.sub.2])), [phi](([i.sub.1], [g.sub.2])) to be different. By the first and second items, we then deduce that {[phi](([i.sub.3], [i.sub.4])), [phi](([i.sub.4], i5))} = {[phi](([g.sub.1],[g.sub.2])), [phi](([g.sub.2], [g.sub.3]))}, and similarly that {[phi](([i.sub.1], [i.sub.2])), [phi](([i.sub.2], [i.sub.3]))} = {[phi](([g.sub.3],[g.sub.4])), [phi](([g.sub.4], [g.sub.5]))}. Thus, the four left-side arcs receive different colours, that are exactly the colours received by the four right-side arcs.

The fourth item is because of previous arguments, and because of the presence of the interference arcs ([f.sub.1], [g.sub.2]), ([g.sub.2], [f.sub.1]), ([f.sub.1],[g.sub.4]), ([g.sub.4], [f.sub.2]). That is, we have [phi](([g.sub.1], [g.sub.2])) = [phi] (([f.sub.1], [f.sub.2])) because of ([f.sub.1],[g.sub.2]), we have [phi](([g.sub.2],[g.sub.3])) = [phi] (([f.sub.1], [f.sub.2])) because of ([g.sub.2], [f.sub.1]{), we have [phi](([g.sub.3], [g.sub.4])) = [phi] (([f.sub.1], [f.sub.2])) because of ([f.sub.1],[g.sub.4]), and we have [phi](([g.sub.4], [g.sub.5])) = [phi] (([f.sub.1] , [f.sub.2])) because of ([g.sub.4], [f.sub.2]).

Our 6-crossover gadget is depicted in Figure 9. The central octagon C is the core from Figure 7. Each of the four peripheral backbone arcs of C serves as the base arc of a tower from Figure 8. Note that, going anticlockwise, all four towers [T.sub.0], ..., [T.sub.3] are "oriented" the same way (with respect to the four base arcs). The four backbone arcs ([y.sub.0], [z.sub.0]), ..., ([y.sub.3], [z.sub.3]) with both sides on the outer face are the corner arcs. The tail [y.sub.i] of each such arc ([y.sub.i], [z.sub.i]) is joined, via out-going interference arcs only, to the base arc of the tower [T.sub.i], to the four left-side arcs from that tower [T.sub.i], and to the four right-side arcs from the next tower [T.sub.i+1] (modulo 4).

Proposition 3.6. The backboned digraph (D, B) depicted in Figure 9 is a 6-crossover gadget.

Proof: Figure 9 shows that (D,B) indeed admits planar embeddings where its four corner arcs have both sides on the outer face. It remains to show that (D, B) has the desired colouring properties, i.e.,:

* (D,B) has 6-BMRN*-colourings;

* in every 6-BMRN*-colouring of (D, B), every two opposite corner arcs are assigned the same colour;

* there exist 6-BMRN*-colourings of (D, B) where all four corner arcs are assigned the same colour;

* there exist 6-BMRN*-colourings of (D, B) where two opposite corner arcs are assigned some colour, that is different from the colour assigned to the remaining two opposite corner arcs.

Figure 9 shows an example of an arc-colouring which is a 6-BMRN*-colouring of (D, B). Let us now prove thoroughly that (D, B) has the desired properties, by describing how a 6-BMRN*-colouring [phi] of (D, B) behaves, starting from the core C, continuing with its towers [T.sub.0], ..., [T.sub.3], and propagating to the corner arcs ([y.sub.0], [z.sub.0]),..., ([y.sub.3], [z.sub.3]). For simplicity, we assume below that [phi] assigns colours in {1,..., 6}.

By Proposition 3.4, the four peripheral backbone arcs of the core are assigned two different colours only, in such a way that no two consecutive of them are assigned the same colour. Let us thus assume that the backbone arcs of the core that are the base arcs of [T.sub.0] and [T.sub.2] are assigned colour 1, while the backbone arcs of the core that are the base arcs of T1 and [T.sub.3] are assigned colour 2. Let us now focus on [T.sub.0]. By Proposition 3.5, the four left-side arcs of [T.SUB.0] must be assigned four different colours different from 1. We distinguish two cases, depending on whether 2 is one of these colours or not.

* Assume 2 is not one of these colours. Then the four colours assigned to the left-side arcs of [T.SUB.0] are 3,4, 5, 6. Still by Proposition 3.5, we deduce that the four right-side arcs of [T.SUB.0] are also assigned colours 3,4, 5, 6. By construction, we note that ([y.sub.0], [z.sub.0]) cannot be assigned a colour assigned to the four left-side arcs of [T.SUB.0] and to its base arc. Thus, we must have [phi](([y.sub.0], [z.sub.0])) = 2. Similarly, ([y.sub.3], [z.sub.3]) cannot be assigned a colour assigned to the four right-side arcs of [T.SUB.0] and to the base arc of [T.sub.3]; the only available colour for ([y.sub.3], [z.sub.3]) is thus 1. In the tower [T.sub.3], the four left-side arcs must be assigned different colours, that must be different from that of ([y.sub.3], [z.sub.3]) (because of interference arcs) and that of the base of [T.sub.3]. Thus, the four left-side arcs of [T.sub.3] are assigned colours 3,4,5,6, which are also the colours of the four right-side arcs of [T.sub.3] by Proposition 3.5.

Repeating these last arguments to [T.sub.2] and then T1, we successively deduce that ([y.sub.2], [z.sub.2]) must be assigned colour 2, the left-side arcs (and right-side arcs) of [T.sub.2] must be assigned colours 3,4,5, 6, the arc ([y.sub.1], [z.sub.1]) must be assigned colour 1, and the left-side arcs (and right-side arcs) of T1 must be assigned colours 3,4,5, 6. Then [phi] is a 6-BMRN*-colouring where 1 = [phi](([y.sub.1], [z.sub.1])) = [phi](([y.sub.3], [z.sub.3])) =

[phi](([y.sub.0], [z.sub.0])) = [phi](([y.sub.2], [z.sub.2])) = 2.

* Assume 2 is one of the four colours assigned to the four left-side arcs of [T.SUB.0] . Without loss of generality, we may assume that these colours are 2,3,4,5. By Proposition 3.5, these colours are also those of the right-side arcs of [T.sub.0]. By the interference arcs leaving from [y.sub.0] to [T.SUB.0], the colour assigned to ([y.sub.0], [z.sub.0]) must be different from 1,2,3,4, 5, and it must thus be 6. We now consider T1: its four right-side arcs must be assigned distinct colours different from that of ([y.sub.0], [z.sub.0]) and that of the base arc of T1. Then the four right-side arcs of T1 are assigned colours 1, 3,4,5, and these are also the colours of the four left-side arcs of T1. Then ([y.sub.1], [z.sub.1]) must be assigned a colour different from that of the four left-side arcs of T1 and that of the base arc of T1. Then [phi](([y.sub.1], [z.sub.1])) = 6. That colour cannot be assigned to the right-side arcs of [T.sub.2]; since these colours must be different from the one of the base arc of [T.sub.2], they are 2,3,4, 5. These colours are also the colours of the left-side arcs of [T.sub.2] by Proposition 3.5.

Continuing that way, we deduce that ([y.sub.2], [z.sub.2]) must be assigned colour 6, the left-side arcs (and right-side arcs) of [T.sub.3] must be assigned colours 1, 3,4,5, and the arc ([y.sub.3],[z.sub.3]) must be assigned colour 6. This results in [phi] being a 6-BMRN*-colouring where [phi](([y.sub.0],[z.sub.0])) = [phi](([y.sub.1],[z.sub.1])) = [phi](([y.sub.2],[z.sub.2])) = [phi](([y.sub.3], [z.sub.3])) = 6.

This concludes the proof.

3.3 Summarizing and going farther

From our 6-crossover gadget we can easily deduce, for any k [member of] {3,4, 5}, a k-crossover gadget in which the same colouring mechanisms apply. For instance:

* For k = 5, remove the arcs ([a.sub.4], [a.sub.5]), ([b.sub.4],[b.sub.5]), ([c.sub.4], [c.sub.5]), ([d.sub.4], [d.sub.5]) from the core, and the arcs ([i.sub.4], [i.sub.5]), ([g.sub.1],[g.sub.2]) from the tower.

* For k = 4, additionally remove the arcs ([a.sub.3],[a.sub.4]), ([b.sub.3],[b.sub.4]), ([c.sub.3], [c.sub.4]), ([d.sub.3], [d.sub.4]) from the core, and the arcs ([i.sub.1], [i.sub.2]), ([g.sub.4],[g.sub.5]) from the tower.

* For k = 3, additionally remove the arcs ([a.sub.2],[a.sub.3]), ([b.sub.2], [b.sub.3]), ([c.sub.2], [c.sub.3]), ([d.sub.2], [d.sub.3]) from the core, and the arc ([h.sub.1], [h.sub.2]) from the tower.

It can easily be seen that, under those modifications, we do end up with a k-crossover gadget in each case, essentially because some particular sets of arcs (with size k - 2 decreasing as k gets smaller) must be assigned different colours. From this and Theorem 3.3, we immediately get that Planar k-BMRN*-Colouring is NP-hard for every k [member of] {3,4,5,6}.

Theorem 3.7. Planar k-BMRN* -Colouring is NP-hard for every k [member of] {3,4,5, 6}.

With some extra effort, we can also prove that, for k [member of] {3,4,5, 6}, Planar k-BMRN*-Colouring remains NP-hard when restricted to planar spanned digraphs. Note that the reduced backboned digraphs we construct in the proof of Theorem 3.7 are far from being spanned, as the backbones we get have many connected components (already note that the core of each copy of the 6-crossover gadget generates nine such connected components). In the next result, we explain how to make these backbones connected without altering the general colouring properties. We show this for k = 6 below, which is the most intricate case, but the arguments also apply for the modified k-crossover gadgets with k [member of] {3,4,5} mentioned earlier.

Theorem 3.8. Planar 6-BMRN* -Colouring is NP-hard when restricted to planar spanned digraphs.

Proof: Consider the reduction from the proof of Theorem 3.3, performed using copies of the 6-crossover gadget exhibited in Proposition 3.6. Then (D, B) is a planar backboned digraph (obtained from G in polynomial time), and G has a proper 6-vertex-colouring if and only if (D, B) has a 6-BMRN*-colouring. Furthermore, in the good drawing of (D, B), by shaping all crossover gadgets similarly to the crossings they replace, we still retain the property that the [u.sub.i]'s lie on the outer face.

We now explain how to turn (D, B) into a planar spanned digraph (D',T), in such a way that the colouring equivalence with G is preserved. We first add a vertex r at the very bottom of the drawing, under all uj's. This r will be the root of our eventual out-tree T. Our goal now, is to repeatedly add, starting from r, directed paths from a connected component of B to another one, so that a bigger connected component (actually an out-tree) is formed, until all connected components are absorbed to a unique out-tree T with root r. The crucial point is the following. Assume (a, b), (c, d) are backbone arcs; if we add a long directed path (made up of backbone arcs only) from, say, b to c, then we note that these added arcs do not interfere with the colouring of (a, b) and (c, d) in a 6-BMRN*-colouring. This is because the inner arcs of such a directed path, if long enough, are subject to only two colour constraints. In other words, assuming (a, b) and (c, d) are coloured, we can easily extend the colouring to the arcs of the joining directed path (assuming again it is long enough).

So the question now is whether, starting from r, we can add long directed paths (made up of new backbone arcs) going to all connected components of B (more precisely to their unique vertex with no in-coming backbone arc), creating only one out-tree, without breaking planarity. Since all [u.sub.i]'s belong to the outer face, we can freely add, for every [u.sub.i], a long directed path from r to [u.sub.i], so that all ([u.sub.i], [v.sub.j])'s now belong to a single connected component (being an out-tree with root r) of T. It now remains to reach the connected components of the crossover gadgets. As can be seen in the drawing of Figure 9, assuming the corner arc ([y.sub.0], [z.sub.0]) belongs to T, from [y.sub.0] we can easily add three long directed paths navigating in faces and going to the vertices [i.sub.1],[g.sub.1], [f.sub.1] of the next tower T1, thus adding three connected components of that tower to T. Once the vertex [i.sub.2] of T1 is part of T, we can then easily add a long directed path to its vertex [h.sub.1] of that tower to add the last connected component of T1 to T. After that, assuming ([y.sub.1], [z.sub.1]) (the other corner arc adjacent to T1) is not already part of T, we can freely add a long directed path from, say, the vertex [i.sub.5] of [T.sub.1] (navigating in a common face) to[y.sub.1], so that ([y.sub.1], [z.sub.1]) is added as well. From ([y.sub.1], [z.sub.1]), we can easily reach the next tower [T.sub.2], and so on. From this, we deduce that all copies of the original backbone arcs of ([D.sub.G], [M.sub.G]) can be added to T, and similarly the connected components of B belonging to the towers of the crossover gadgets. For every crossover gadget, it just remains to connect to T the five inner connected components of its core, which is easy to do assuming [f.sub.1], [f.sub.3], [f.sub.5], [f.sub.7] (which are incident to the base arcs of the towers) are already part of T. Namely, navigating inside faces to preserve planarity, we can add a long directed path from [f.sub.2] to [a.sub.1], from [f.sub.4] to [d.sub.1], from [f.sub.6] to [c.sub.1], from [f.sub.8] to [b.sub.1], and finally from [a.sub.1] to [e.sub.1].

Repeating this procedure to all crossover gadgets, we can make sure that T eventually is an out-tree with root r, and we end up with a planar spanned digraph (D', T) such that G has a proper 6-vertex-colouring if and only if (D', T) has a 6-BMRN*-colouring. In particular, note that the number of connecting directed paths we must add is polynomial, since the number of crossover gadgets is polynomial by the properties of a good drawing. Thus, the whole construction is achieved in polynomial time.

4 Connection between BMRNT-index and girth

The planar backboned digraph depicted in Figure 3 has "large" BMRN* -index (for a planar digraph), mainly due to its several short cycles (with length 2 or 3). In this section, we investigate the effects of forbidding small cycles on the BMRN* -index.

We prove that, as one could expect, the BMRN*-index of planar spanned digraphs decreases as the girth grows. We prove this in the general case, i.e., when no further backbone restrictions are imposed. Under an additional structural condition (backbone with bounded maximum degree), we give a result involving a stronger girth assumption. To summarize, our results in this section are as follows:

Theorem 4.1. Let (D, B) be a planar backboned digraph. Then:

* if g(D) [greater than or equal to] 5 and [DELTA]+(B) [less than or equal to] 1, then BMRN* (D, B) [less than or equal to] 7;

* if g(D) [greater than or equal to] 7, then BMRN* (D, B) [less than or equal to] 6;

* if g(D) [greater than or equal to] 16, then BMRN* (D, B) [less than or equal to] 4;

* if g(D) [greater than or equal to] 21, then BMRN* (D, B) [less than or equal to] 3;

* there is no k such that if g(D) [greater than or equal to] k, then BMRN* (D, B) [less than or equal to] 2.

4.1 General case

Throughout this section, we deal with vertices having certain degrees. A k-vertex is a vertex having degree precisely k. A [k.sup.-] -vertex (resp. [k.sup.+]-vertex) is a vertex having degree at most (resp. at least) k. For some l [greater than or equal to] 1, an l-thread refers to a path ([v.sub.1],..., [v.sub.l+2]) where the l inner vertices [v.sub.2],..., [v.sub.l+1] are 2-vertices. Under a mild minimum degree assumption, threads are well-known to exist in planar graphs with large enough girth:

Theorem 4.2 (e.g. [4]). Every planar graph with minimum degree at least 2 and girth at least 5l+1 contains an l-thread.

In some of the upcoming proofs, we will need the fact that trees have low BMRN* -index:

Theorem 4.3. Let (D, B) be a backboned digraph. If D is a tree, then BMRN* (D,B) [less than or equal to] 2.

Proof: The proof is by induction on |V(D)| + |A(D)|. As the claim can easily be verified for trees with small order, we focus on the general case. In particular, we may assume that all vertices of D are part of the backbone, as otherwise we could remove "useless" vertices, and a 2-BMRN*-colouring of the remaining backboned digraph would also be one of (D, B). Also, we may assume that no interference arc (u, v) is "useless", i.e., we have [d+.sub.B](u) [greater than or equal to] 1 and [d.sub.B](v) = 1.

If B has only one connected component, then (D,B) has no interference arcs (as otherwise D would have cycles). In this case, we only have to deal with direct conflicts, which can be done by simply considering the bipartition ([V.sub.1], [V.sub.2]) of D, and, for i = 1,2, assigning colour i to all backbone arcs originating from a vertex in Vi. Thus, we may assume that B has several connected components, connected via interference arcs. If we contract, in D, all connected components of B to vertices, resulting in an oriented multigraph G, then und(G) cannot have cycles as otherwise D would as well. This implies that G is actually an oriented graph, and that two connected components of B are joined by at most one interference arc.

Since (D, B) is assumed to have no useless interference arcs, und(G) is actually connected, and G is thus an oriented tree. For every vertex v of G, let C(v) denote the connected component of B corresponding to v. We deduce a 2-BMRN*-colouring of each connected component of B, one after another, such that all colourings comply with each other and give a 2-BMRN*-colouring of the whole (D, B). This is done by considering the connected components of B as the corresponding vertices of und(G) are encountered during a BFS performed from an arbitrary root r of G.

We thus start with r. Since nothing is coloured yet, we can freely choose, as a 2-BMRN*-colouring of C(r), any 2-BMRN*-colouring, which exists by the induction hypothesis. Let us now consider the general case, i.e., that during the BFS of und(G), we are now dealing with a vertex v, whose parent in und(G) (by the BFS ordering) is u. Recall that either (u, v) or (v, u) can be the corresponding arc in G. We assume in what follows that (u, v) is the arc, but the symmetric arguments, in case the arc is (v, u), also hold. Let [x.sub.u] denote the vertex of C(u) from which the corresponding interference arc originates in (D, B), and [x.sub.v] denote the vertex of C(v) at which the interference arc terminates in (D, B). By the induction hypothesis, C(v) admits a 2-BMRN*-colouring. Free to permute the colours, we may assume that the colour assigned to the unique backbone arc in-coming to [x.sub.v] is different from the unique colour assigned to the backbone arcs out-going from [x.sub.u]. Then, there is no indirect conflict raised, and the whole partial colouring is a partial 2-BMRN*-colouring of (D, B).

Going on like this until all vertices of G have been treated by the BFS, we end up with a 2-BMRN* -colouring of (D, B).

We now prove all results (but the first one, postponed to the next subsection) in Theorem 4.1, by dedicating a theorem or observation to each item. We voluntarily modify the order in which these results are delivered, as some of the proofs depend on other ones.

We start off by observing that, in general, planar backboned digraphs with arbitrarily large girth might require at least three colours in a BMRN*-colouring:

Observation 4.4. There is no k such that planar backboned digraphs (D, B) with girth at least k have BMRN* (D, B) < 3.

Proof: This is because large girth does not prevent a backboned digraph to have an odd number of backbone arcs, each of which acting as a constraint for another in a "cyclic" way (i.e., which would correspond to an odd-length cycle for proper vertex-colouring of undirected graphs). Such backbone arcs force the use, in a BMRN*-colouring, of at least three colours. This occurs, for instance, when a planar backboned digraph (D, B) contains the following configuration. Let k > 3 be any odd integer. For every i [member of] {0,..., k - 1}, assume (D,B) has a backbone arc ([v.sub.i], [v'.sub.i]), and, modulo k, the interference arc ([v.sub.i], [v'.sub.i+1]). Then it is easy to see that two "consecutive" backbone arcs ([v.sub.i], [v'.sub.i]) and ([v.sub.i +1], [v'.sub.i+1]) must receive different colours by a BMRN*-colouring. Since there is an odd number of arcs in that "cycle", at least three colours are needed.

We now prove that, in general, if the girth of a planar backboned digraph is larger than some threshold, then its BMRN*-index becomes less than some value.

Theorem 4.5. Let (D,B) be a planar backboned digraph. If D has girth at least 21, then BMRN* (D,B) [less than or equal to] 3.

Proof: Assume the statement is wrong, and let (D, B) be a planar backboned digraph with girth at least 21 verifying BMRN*(D, B) > 3. We consider such a (D, B) that is minimum in terms of |V(D)| + |A(D)|. This property implies that D is connected. It also implies that, for every interference arc (u, v), we must have [d+.sub.B] (u) > 1 and [d-.sub.B] (v) = 1, as otherwise this arc could not be involved in any indirect conflict, and we could just remove it from (D, B), and deduce a 3-BMRN*-colouring of the remaining backboned digraph (in which every connected component is either a backboned oriented tree, which has 3-BMRN*-colourings by Theorem 4.3, or a smaller planar backboned digraph with girth at least 21) that is also one of (D, B), a contradiction. This in turn implies that every vertex v of D must be part of B, as otherwise we could find, in (D,B), interference arcs that are useless.

Our aim is to find a 4-thread in D by means of Theorem 4.2. That theorem tells us that the existence of such threads is, despite the girth of D, not guaranteed if [delta](D) = 1. We thus first need to investigate how 1-vertices behave in D.

First off, we note that if v is a vertex of D adjacent to 1-vertices, then v is adjacent to at most two 1-vertices. Indeed, if v is adjacent to three 1-vertices [u.sub.1], [u.sub.2], [u.sub.3], then we must have two arcs, say (v, [u.sub.1]) and (v, [u.sub.2]), being backbone arcs. This is because every vertex must be incident to a backbone arc (by minimality of (D, B)), and every vertex has in-degree at most 1 in the backbone. In that case, we consider (D',B') the backboned digraph obtained when removing [u.sub.1] from D. Since (D',B') is a planar backboned digraph with girth at least 21 that is smaller than (D, B), it has a 3-BMRN*-colouring which we can extend to (v, [u.sub.1]) by simply assigning the colour of (v, [u.sub.2]) to (v, [u.sub.1]). This is correct since these two backbone arcs are subject to the same colour constraints. Thus, we get a 3-BMRN*-colouring of (D, B), a contradiction. Consequently, if a vertex v of D is adjacent to 1-vertices, then it is adjacent to at most two 1-vertices. Furthermore, if [u.sub.1], [u.sub.2] are two 1-vertices adjacent to v, then, without loss of generality, ([u.sub.1],v) and (v, [u.sub.2]) are backbone arcs.

Assume now that D has a 1-vertex u, and let v be its unique neighbour. By minimality of (D, B), vertices v and u must be joined by a backbone arc. Assume (v, u) is that backbone arc. We claim that v must be a 4+-vertex. Indeed, consider the backboned digraph (D', B') obtained from (D, B) by removing u; again, (D', B') admits a 3-BMRN*-colouring. If we cannot extend it to (v, u), thus to (D, B), then this means that the three colours appear "around" v. The colours that cannot be assigned to (v, u) are the following: the one assigned to the unique backbone arc (w,v) (if any), and, for every interference arc (v,w) incident to v, the one assigned to the unique backbone arc in-coming to w (if any). In other words, every arc incident to v in (D', B') prevents us from assigning at most one colour to (v, u). Thus, for the three colours to be not assignable to (v, u), it must be that v has degree at least 3 in (D', B'), and thus at least 4 in (D, B). These arguments also hold in the case where (u, v) is a backbone arc ((u, v) cannot be assigned the unique colour assigned to the backbone arcs out-going from v (if any), and, for every interference arc (w, v), the unique colour assigned to the backbone arcs out-going from w).

Now, assume that D has a vertex v adjacent to two 1-vertices u1,u2. By arguments above, we may assume that (u1,v) and (v, u2) are backbone arcs of (D, B). We claim that v is a 6+-vertex. Indeed, first consider the backboned digraph (D', B') obtained when removing [u.sub.1] from (D, B). Again, (D', B') has a 3-BMRN*-colouring. We try to extend it to ([u.sub.1], v). The colour assigned to ([u.sub.1],v) must be different from that of (v, [u.sub.2]). It must also be different, for every interference arc (w, v), from the unique colour assigned to the backbone arcs out-going from w, if any. Thus, there must be at least two interference arcs in-coming to v, to make sure that the colouring cannot be extended to (u1, v) (in which case we would get a contradiction). Now consider (D', B') the backboned digraph obtained from (D, B) by removing [u.sub.2]. Note that we may suppose that v is not incident to other out-going backbone arcs, as otherwise we could just assign their colour to (v, [u.sub.2]). Now, by symmetric arguments as above, for a 3-BMRN*-colouring of (D', B') to be not extendable to (v, [u.sub.2]), there must be at least two interference arcs out-going from v. We thus deduce that v has degree at least 6 in D.

We are now ready to combine all these arguments for deducing the existence of a 4-thread in D. We apply the following simple iterative procedure: As long as D has a 1-vertex, we just remove it. Let D' denote the resulting digraph once all 1-vertices have been peeled off (and thus no 1-vertex remains). It is easy to see that D' cannot be a tree, unless D was one (as the presence of any cycle in D makes it impossible for D' to be a tree, and removing 1-vertices from a graph cannot disconnect it). Also, D' cannot be empty. Then D' is a (connected) planar digraph with girth at least 21 and [delta](D') > 2. Then, by Theorem 4.2, D' has a 4-thread ([v.sub.1],..., [v.sub.6]), where [v.sub.2],... ,[v.sub.5] are its 2-vertices. The crucial point is that this 4-thread is also a 4-thread in D. This is because, although seemingly iterative, the process of repeatedly removing 1-vertices from D actually only removes vertices that were already of degree 1 in D. This is because vertices of D are adjacent to at most two 1-vertices, and vertices v of D adjacent to 1-vertices are of large degree. Indeed, either v is adjacent to only one 1-vertex in D, in which case v is a 4+-vertex in D and it becomes a 3+-vertex once its adjacent 1-vertex has been removed, or v is adjacent to two 1-vertices in D, in which case v is a 6+-vertex in D and thus it becomes a 4+-vertex once its two adjacent 1-vertices have been removed. Hence, all 2-vertices [v.sub.2], ..., [v.sub.5] of the 4-thread in D' are also 2-vertices in D, and this thread is thus also a 4-thread in D.

We now deal with this 4-thread ([v.sub.1],..., [v.sub.6]) in (D, B). Assume first that ([v.sub.3], [v.sub.4]) is a backbone arc. If ([v.sub.3], [v.sub.2]) is not a backbone arc, then we consider the backboned digraph (D', B') obtained by removing ([v.sub.3], [v.sub.4]) from (D, B). By arguments similar to that above, (D, B') admits a 3-BMRN*-colouring, which we wish to extend to ([v.sub.3], [v.sub.4]). This is possible because ([v.sub.3], [v.sub.4]) is subject to at most two colour constraints. Indeed, there are two possibilities regarding the arc joining [v.sub.2] and [v.sub.3]: either ([v.sub.2],[v.sub.3]) is a backbone arc, or ([v.sub.3], [v.sub.2]) is an interference arc (in which case ([v.sub.1], [v.sub.2]) must be a backbone arc). Then ([v.sub.3], [v.sub.4]) must be assigned a colour different from either the colour of ([v.sub.2], [v.sub.3]) (first case) or the unique one assigned to the backbone arcs out-going from [v.sub.1] (that of ([v.sub.1],[v.sub.2]), second case), and that of ([v.sub.4], [v.sub.5]) (case where this is a backbone arc), or that of ([v.sub.5], [v.sub.6]) (otherwise: if ([v.sub.4], [v.sub.5]) is not a backbone arc, then ([v.sub.5],[v.sub.4]) must be an interference arc, and thus ([v.sub.5], [v.sub.6]) must be a backbone arc). This is a contradiction.

Now assume that both ([v.sub.3], [v.sub.2]) and ([v.sub.3],[v.sub.4]) are backbone arcs. We here consider (D', B') to be the back-boned digraph obtained after removing ([v.sub.3], [v.sub.2]), ([v.sub.3],[v.sub.4]). Again, it admits a 3-BMRN*-colouring which we wish to extend to the two removed arcs, assigning them a same colour. We claim that, here as well, at most two colours only must be avoided. Indeed, we cannot assign to ([v.sub.3], [v.sub.2]), ([v.sub.3], [v.sub.4]) the colour of ([v.sub.2], [v.sub.1]) (case where that arc is a backbone arc), or the unique colour assigned to the backbone arcs out-going from [v.sub.1] (otherwise: if ([v.sub.2], [v.sub.1]) is not a backbone arc, then ([v.sub.1], [v.sub.2]) must be an interference arc by minimality of (D, B)). Similarly, we cannot assign to ([v.sub.3], [v.sub.2]), ([v.sub.3], [v.sub.4]) the colour of ([v.sub.4], [v.sub.5]) (case where it is a backbone arc), or the colour of ([v.sub.5],[v.sub.6]) (otherwise: if ([v.sub.4], [v.sub.5]) is not a backbone arc, then ([v.sub.5], [v.sub.4]) must be an inter-ference arc, and ([v.sub.5], [v.sub.6]) must be a backbone arc). Thus one of the three colours is not used around, and we can freely assign it to ([v.sub.3], [v.sub.2]), ([v.sub.3], v4), resulting in a 3-BMRN*-colouring of (D, B), a contradiction.

The last case to consider is when the arc joining [v.sub.3] and [v.sub.4] is an interference arc. By symmetry, we may assume that ([v.sub.3], [v.sub.4]) is an interference arc. Then, by minimality of (D, B), both ([v.sub.3], [v.sub.2]) and ([v.sub.5], [v.sub.4]) are backbone arcs. In that case, we consider (D, B') the backboned digraph obtained when removing ([v.sub.3], [v.sub.2]) from (D, B). A 3-BMRN*-colouring of (D', B') can be extended to ([v.sub.3], [v.sub.2]), thus to (D, B), because this arc is subject to at most two colour constraints only: either the colour of ([v.sub.2], [v.sub.1]) (if it is a backbone arc) or the unique colour assigned to the backbone arcs out-going from [v.sub.1] (otherwise), and the colour of ([v.sub.5],[v.sub.4]). This is yet another contradiction, which concludes the proof.

Theorem 4.6. Let (D,B) be a planar backboned digraph. If D has girth at least 16, then BMRN* (D,B) [less than or equal to] 4.

Proof: The proof starts similarly as that of Theorem 4.5. Let (D, B) be a minimum counterexample to the claim. Since we are now working with four colours, from arguments we have used earlier the following properties of D and D' (the digraph obtained when removing all 1-vertices from D) can be deduced:

* every vertex of D is adjacent to at most two 1-vertices;

* every vertex of D adjacent to a 1-vertex is a 5+-vertex;

* every vertex of D adjacent to two 1-vertices is an 8+-vertex;

* D' has 3-threads, each of which is a 3-thread of D.

Let ([v.sub.1],..., [v.sub.5]) be a 3-thread of D, where [v.sub.2],... ,[v.sub.4] are its 2-vertices. Note that we may assume that [v.sub.1], [v.sub.5] are 3+-vertices, as otherwise D would have a 4-thread, from which we could deduce a 4-BMRN* -colouring of (D, B) just as in the proof of Theorem 4.5. In most cases, a 4-BMRN*-colouring of (D, B) can be deduced from this 3-thread ([v.sub.1],... ,[v.sub.5]). Actually, only one case is not reducible. Let us first prove that all other cases are indeed reducible.

Assume first that [v.sub.3] is incident to out-going backbone arcs. There are two cases to consider. First, assume that both ([v.sub.3],[v.sub.2]) and ([v.sub.3], [v.sub.4]) are backbone arcs. We here remove [v.sub.3] from (D,B); the remaining backboned digraph admits a 4-BMRN* -colouring that can be extended to ([v.sub.3], [v.sub.2]) and ([v.sub.3], [v.sub.4]), a contradiction. Indeed, we must avoid either the colour of ([v.sub.2], [v.sub.1]) (if it is a backbone arc) or the unique colour assigned to the backbone arcs out-going from [v.sub.1] (otherwise), and the colour of ([v.sub.4], [v.sub.5]) (if it is a backbone arc) or the unique colour assigned to the backbone arcs out-going from [v.sub.5] (otherwise). Second, assume that only ([v.sub.3], [v.sub.2]) is a backbone arc. By minimality of (D, B), ([v.sub.3], [v.sub.4]) is an interference arc, and ([v.sub.5],[v.sub.4]) is a backbone arc. We here remove only ([v.sub.3], [v.sub.2]) from (D, B). Here, for extending a 4-BMRN*-colouring of the remaining backboned digraph to ([v.sub.3], [v.sub.2]), we must avoid either the colour of ([v.sub.2],[v.sub.1]) (if it is a backbone arc) or the colour assigned to the backbone arcs out-going from [v.sub.1] (otherwise), and the unique colour assigned to the backbone arcs out-going from [v.sub.5] (i.e., the colour of ([v.sub.5], [v.sub.4])). Since we have four colours in hand, we can find an open colour for ([v.sub.3], [v.sub.2]), a contradiction.

Thus, we now assume that [v.sub.3] is incident to only one in-coming backbone arc. Assume ([v.sub.2],[v.sub.3]) is that backbone arc. Regarding the arc joining [v.sub.3] and [v.sub.4], by minimality there are two cases: either ([v.sub.3], [v.sub.4]) is a backbone arc, or ([v.sub.4], [v.sub.3]) is an interference arc (in which case ([v.sub.4], [v.sub.5]) must be a backbone arc). In the first case, we just remove ([v.sub.3], [v.sub.4]) from (D, B), deduce a 4-BMRN*-colouring, and extend it to ([v.sub.3], [v.sub.4]) as this arc is subject to at most two colour constraints. Indeed, we must avoid the colour of ([v.sub.2], [v.sub.3]), and the colour of either ([v.sub.4], [v.sub.5]) (when ([v.sub.4], [v.sub.5]) is a backbone arc) or the colour assigned to the backbone arcs out-going from [v.sub.5] (when ([v.sub.5], [v.sub.4]) is an interference arc). In the second case, if ([v.sub.2], [v.sub.1]) is an interference arc, then we are done, because we can just remove ([v.sub.2],[v.sub.3]) from (D, B), deduce a 4-BMRN*-colouring, an extend it to ([v.sub.2] ,[v.sub.3]) as this arc is subject to at most two colour constraints. Indeed, we must avoid the colour of the unique backbone arc in-coming to [v.sub.1] (if any), and the colour of ([v.sub.4], [v.sub.5]).

It can be checked that the remaining type of 3-thread ([v.sub.1],... ,[v.sub.5]), which is when ([v.sub.2],[v.sub.1]), ([v.sub.2],[v.sub.3]), ([v.sub.4], [v.sub.5]) are backbone arcs while ([v.sub.4], [v.sub.3]) is an interference arc, cannot be reduced that simply, via counting arguments only. We call such 3-threads bad threads. Before going on, we need to exhibit a few properties of these bad threads in (D,B).

A first important property is deduced from the fact that, for a bad 3-thread ([v.sub.1],..., [v.sub.5]), we have the backbone arcs ([v.sub.2],[v.sub.1]) and ([v.sub.4], [v.sub.5]). This means that, in (D, B), a vertex v can be incident to at most one bad thread, as otherwise v would have two backbone arcs coming in. Another property is that [v.sub.1] and [v.sub.5] must be 4+-vertices; this is again deduced by removing either ([v.sub.2], [v.sub.1]) and ([v.sub.2],[v.sub.3]) (for establishing the bound on the degree [v.sub.1]), or ([v.sub.4], [v.sub.5]) (for establishing the bound on the degree of [v.sub.5]), and counting the number of colour constraints around. Lastly, for a 3-thread ([v.sub.1],..., [v.sub.5]) of (D, B), the vertex [v.sub.1] (and similarly [v.sub.5]) can be adjacent to at most one 1-vertex (via an out-going backbone arc), and, in that case, we recall that [v.sub.1] (resp. [v.sub.5]) is a 5+-vertex.

We are now ready to conclude. Start from (D,B), and, as in the proof of Theorem 4.5, remove 1-vertices as long as possible. The remaining digraph (D', B') cannot be a tree, remains connected, it is planar with girth at least 16, and, as mentioned earlier, it has minimum degree 2. (D', B') thus has a 3-thread T1 = ([v.sub.1],..., [v.sub.5]), which is also a 3-thread in (D, B). If T1 is not bad, then we are done. So assume that T1 is a bad 3-thread. Back in (D', B'), we remove the vertices [v.sub.2],[v.sub.3], [v.sub.4], resulting in a backboned digraph (D", B"). Recall that, in (D, B), both [v.sub.1] and [v.sub.5] are 4+-vertices, and, if any of them is also adjacent to a unique 1-vertex, then it is even a 5+-vertex. This implies that, in (D", B"), both [v.sub.1] and [v.sub.5] are 3+-vertices, and they do not have any backbone arc coming in. Also, D" remains of minimum degree at least 2.

Although D" might have several connected components, they all have girth at least 16. Thus, in D", by Theorem 4.2 we can again find a 3-thread [T.sub.2], which is also a 3-thread in D. Again, if [T.sub.2] is not a bad 3-thread in (D, B), then we are done. Thus we may assume that [T.sub.2] is bad, and, by the properties we have on the first and last vertices of bad threads, we know that T1 and [T.sub.2] do not intersect. Next, we again remove the inner degree-2 vertices of [T.sub.2] from the current digraph; it remains of minimum degree at least 2, and it remains a planar digraph whose all connected components have girth at least 16.

We continue this process as long as possible. That is, for a backboned digraph obtained from D after removing the 1-vertices and the inner vertices from some bad 3-threads [T.sub.1],..., [T.sub.k] of (D, B), we deduce the existence of another 3-thread [T.sub.k+1] by Theorem 4.2, which is also present in (D, B). If [T.sub.k+1] is not a bad thread, then we are done. Otherwise, we remove its three inner vertices from the current digraph, and we go on. We know that the two ends of [T.sub.k+1] remain of degree strictly more than 2, and thus so do all vertices. Furthermore, all resulting connected components remain of girth at least 16. Also, recall that no two threads Ti, Tj can share vertices (because any vertex of (D, B) can be incident to at most one bad thread, and after removing a bad thread no new 2-vertex can be created). The process will thus end up with finding a 3-thread that is no bad. Back in (D, B), this is a 3-thread that can be reduced, and from its existence we get that (D, B) has 4-BMRN*-colourings; a contradiction.

Theorem 4.7. Let (D, B) be a planar backboned digraph. If D has girth at least 7, then BMRN* (D,B) < 6.

Proof: This is proved by designing a particular vertex-colouring [phi] of D. To every vertex v of D with d+B(v) > 1, we assign a 2-element colour [phi](v) = {[c.sub.1](v),[c.sub.2](v)} so that, when assigning colour [phi](v) to all backbone arcs out-going from v, the resulting "derived" arc-colouring forms a BMRN*-colouring of (D, B). The function [c.sub.1] will take value in {1, 2}, while [c.sub.2] will take value in {1,2,3}, so that [phi] is a 6-colouring.

We construct [phi] in the following way. Let (V1, V2) denote the bipartition of B (in case B has several connected components, we consider any bipartition of each component). For every vertex v [member of] [V.sub.1], we set [c.sub.1](v) = 1, while we set [c.sub.1](v) = 2 for every v [member of] [V.sub.2]. This way, note that, in (D, B), we have already dealt with direct conflicts by the arc-colouring derived from [phi] (because no two consecutive backbone (u, v), (v, w) arcs originate from vertices in the same partite set). It remains to deal with indirect conflicts, which is done by defining [c.sub.2] appropriately.

For i = 1, 2, we denote by Di the digraph obtained from (D, B) and [c.sub.1] as follows. The vertices of [D.sub.i] are the vertices v of D verifying [c.sub.1](v) = i. The arcs of Di model the potential indirect conflicts in (D,B) between vertices v with [c.sub.1](v) = i. That is, for every two vertices u,v with [c.sub.1](u) = [c.sub.1](v) = i, we add the arc (u,v) to Di if (u,v') is an interference arc of (D,B), where (v,v') is a backbone arc. That is, the presence of the arc (u, v) in Di indicates that u and v should receive distinct colours by a BMRN*-colouring of (D, B) (to avoid an indirect conflict), while its direction indicates the direction of the corresponding interference arc (it goes from u to an out-neighbour of v). Note that [D.sub.i], in general, is a multidigraph.

Observe that each [D.sub.i] is a planar digraph. Indeed, seen differently, Di was obtained from D by deleting all arcs out-going from vertices in [V.sub.3-i], and contracting all backbone arcs out-going from vertices in [V.sub.i]. This means that [D.sub.i] is a minor of D; since D was assumed planar, so is [D.sub.i], as planar graphs form a minor-closed family of graphs.

Let us now focus on [D.sub.1]. Recall that its arcs join vertices (with the same colour by [c.sub.1]) whose out-going backbone arcs must not be assigned the same colour in a BMRN*-colouring of (D, B) (to avoid some indirect conflict). Thus, by the arc-colouring derived from [phi], no colour conflict involving two vertices of [D.sub.1] will arise as soon as [c.sub.2], when restricted to [D.sub.1], is a proper vertex-colouring. We claim that, because D has girth at least 7, [D.sub.1] itself has girth at least 4, and thus admits a proper 3-vertex-colouring by Grotzsch Theorem [6].

Assume the contrary, i.e., that [D.sub.1] has a 2-cycle or 3-cycle C.

* If C = (u, v, u) has length 2, then there are two possible orientations for C in [D.sub.1].

- On the one hand, assume there are two arcs from u to v in [D.sub.1]. Since D is simple, this means that there are two interference arcs (u, [v.sub.1]), (u, [v.sub.2]) in (D, B), where (v,[v.sub.1]), (v,[v.sub.2]) are two backbone arcs. Then (u, [v.sub.1], v, [v.sub.2],u) is a 4-cycle of D, a contradiction to it having girth at least 7.

- On the other hand, assume D1 has two arcs (u, v) and (v, u). This means that (D, B) has two interference arcs (u, v'), (v, u'), where (u, u'), (v, v') are backbone arcs. Then (u, u', v, v', u) is a 4-cycle, a contradiction.

* If C = (u, v, w, u) has length 3, then there are two possible (non-isomorphic) orientations in [D.sub.1]:

- On the one hand, assume the three arcs are (u, v), (v, w), (w, u). This means that (D, B) has three interference arcs (u, v'), (v, w'), (w, u'), where (u, u'), (v, v'), (w, w') are three backbone arcs. Then (u, v', v, w', w, u', u) is a 6-cycle in D, a contradiction.

- On the other hand, assume that the three arcs are (u, v), (v, w), (u, w). This means that, in (D,B), one of the following two situations occurs:

* (D, B) has three interference arcs (u, v'), (u, w'), (v, w'), where (v, v'), (w, w') are two backbone arcs. Then (u, v', v, w', u) is a 4-cycle, a contradiction.

* (D, B) has three interference arcs (u, v'), (u, w'), (v, w"), where (v, v'), (w, w'), (w, w") are two backbone arcs. Then (u, v', v, w", w, w', u) is a 6-cycle, a contradiction.

Thus, [D.sub.1] has girth at least 4, meaning it admits a proper 3-vertex-colouring. Similarly, [D.sub.2] admits a proper 3-vertex-colouring as well. These two colourings yield our [c.sub.2].

4.2 Bounded-degree backbone

One notable property of the spanned digraph (D, T) in Figure 2 is that T is a directed path, i.e., it has maximum outdegree 1. This indicates that having, in a planar backboned digraph, the backbone arcs inducing a very simple topology is sometimes sufficient to have "large" BMRN*-index. The other way around, in planar spanned digraphs the interference arcs are sufficient to make the number of colours large. Yet, in the following result we show how to take advantage of a simple backbone to prove that Question 1.1 is true for planar spanned digraphs with even smaller girth, and that eight colours are not necessary to colour them.

Theorem 4.8. Let (D, B) be a planar backboned digraph. If D has girth at least 5 and [DELTA]+ (B) [less than or equal to] 1, then BMRN* (D, B) [less than or equal to] 7.

Proof: Assume the claim is wrong, and consider (D, B) a smallest counterexample to the claim (in terms of |V(D) | + |A(D) |). By minimality, we may suppose that D is connected, that all vertices are part of the backbone, and that there are no useless interference arcs.

We might as well suppose that D has no bridge, say (u, v), such that none of u, v is a 1-vertex. Indeed, on the one hand, if (u, v) is a backbone arc, then we can remove (u, v) from (D,B), resulting in the disjoint union of two backboned digraphs ([D.sub.1], [B.sub.1]), ([D.sub.2], [B.sub.2]), where [B.sub.1], [B.sub.2] are the restrictions of B to [D.sub.1], [D.sub.2]. Because none of u,v is a 1-vertex, note that both ([D.sub.1] + (u,v), [B.sub.1] + (u,v)) and ([D.sub.1] + (u,v), [B.sub.2] + (u, v)) admit a 7-BMRN*-colouring (either by induction or Theorem 4.3). It is then easy to see that, when permutting the colours of these two colourings so that (u, v) gets the same colour in each of them, a 7-BMRN*-colouring of (D, B) is obtained. On the second hand, if (u, v) is an interference arc, then we can just, by freely permutting the colours, consider 7-BMRN*-colourings of ([D.sub.1], [B.sub.1]) and (D2, B2) such that the unique colour assigned to the backbone arcs out-going from u is different from the colour of the unique backbone arc in-coming to v. This forms a 7-BMRN*-colouring of (D, B), a contradiction. Thus, omitting its arcs incident to 1-vertices, we may assume that D has no bridge.

Assuming (D, B) exists, we get to a contradiction through the use of the so-called discharging method, which consists in the following steps. We first prove that some configurations (subdigraphs with certain properties) are reducible in (D, B), meaning that if (D, B) had one of these reducible configurations, then we would find a way to deduce a 7-BMRN*-colouring of (D, B) from it, a contradiction. Next, through the discharging phase itself, we will supply a precise amount of charge to the elements (vertices and faces) of (D, B) and, because of the reducible configurations, show that, upon only moving charges between elements in a very specific way, a contradiction to the initial provided amount of charges is obtained.

1. First reducible configurations

As a general tool, we start off by proving that, in (D, B), two vertices with small degree cannot be joined by a backbone arc.

Claim 4.9. Let (u, v) be a backbone arc of (D, B). Then

[d-.sub.B] (u) + [d+.sub.D-B] (u) + [d+.sub.B] (v) + [d-.sub.D-B] (v) [greater than or equal to] 7.

Proof ofthe claim. Assume to the contrary that (D, B) has abackbonearc (u, v) where [d-.sub.B](u)+[d+.sub.D_B](u) + [d+.sub.B] (v) + [d.sub.D-B] (v) < 7. Let (D', B') be the planar backboned digraph obtained by removing (u, v) from (D, B). By minimality of (D, B), this (connected, by previous arguments on bridges) digraph (D', B'), which is still of girth at least 5 with [DELTA]+ (B') < 1, admits a 7-BMRN*-colouring [phi]. We show below that [phi] can be extended to (u, v), thus to (D, B), a contradiction.

By the definition of BMRN*-colouring, those colours around (u, v) that cannot be assigned to (u, v) are the following (assuming they all exist):

* the colour of the backbone arc in-coming to u;

* the colour of the backbone arc out-going from v;

* for every interference arc (u, w) out-going from u, the colour of the backbone arc in-coming to w;

* for every interference arc (w, v) in-coming to v, the colour of the backbone arc out-going from w.

It can easily be seen that any other arc incident to u or v does not yield any colouring constraint for extending [phi] to (u, v). Also, any arc incident to u or v constrains the assignation of at most one colour to (u, v). Since each of the seven colours we are playing with must be not assignable to (u,v), the result follows.

In particular through Claim 4.9, we deduce properties of small-degree vertices in (D, B).

Claim 4.10. Let v be a vertex of (D, B) being adjacent to 1-vertices; then:

1. v is adjacent to at most two 1-vertices;

2. every arc between v and a 1-vertex is a backbone arc;

3. if v is adjacent to a one 1-vertex, then d(v) [greater than or equal to] 8;

4. if v is adjacent to exactly two 1-vertices, then d(v) [greater than or equal to] 14; moreover, the two backbone arcs joining v and these two 1-vertices have opposite directions.

Proof of the claim. The first and second items, as well as the last part of the fourth item, are because every vertex of (D, B) must be incident to a backbone arc, and we have [DELTA]+(B) [less than or equal to] 1. The third item and the first part of the fourth item follow from a direct application of Claim 4.9. Recall in particular that removing a backbone arc from (D, B) results in a connected digraph (since bridges are incident to 1-vertices, by previous arguments), which implies that the girth restriction is preserved upon removing single arcs.

Claim 4.11. D has no 3-thread.

Proof of the claim. Assume D has a 2-vertex v adjacent to two 2-vertices u, w. By minimality of (D, B), v must be incident to a backbone arc; assume (u, v) or (v, u) is that backbone arc. Then we get a contradiction to Claim 4.9, since both u and v have degree 2.

From Claim 4.11, we know that all l-threads in (D,B), if there are any, verify l [member of] {1,2}. Some of these threads are reducible because of Claim 4.9. The remaining irreducible threads, which we cannot reduce immediately via the degree condition in the claim, have the following properties:

Claim 4.12. An irreducible thread of (D, B) is either:

* A 2-thread ([v.sub.1], [v.sub.2], [v.sub.3], [v.sub.4]); in that case, ([v.sub.1],[v.sub.2]) and ([v.sub.3],v4) (resp. ([v.sub.4], [v.sub.3]) and ([v.sub.2], [v.sub.1])) are backbone arcs, while ([v.sub.3], [v.sub.2]) (resp. ([v.sub.2], [v.sub.3])) is an interference arc. Furthermore, both [v.sub.1] and [v.sub.4] are 7+-vertices.

* A 1-thread ([v.sub.1], [v.sub.2], [v.sub.3]); in that case, at least one of ([v.sub.1],[v.sub.2]), ([v.sub.2], [v.sub.1]), ([v.sub.3], [v.sub.2]), and ([v.sub.2], [v.sub.3]) is a back-bone arc. Furthermore, each of [v.sub.1], [v.sub.3] incident to such a backbone arc is a 7+ -vertex.

Proof of the claim. First assume ([v.sub.1],[v.sub.2], [v.sub.3], v4) is a 2-thread of (D, B). Note that the arc joining [v.sub.2] and [v.sub.3] cannot be a backbone arc, as otherwise Claim 4.9 would yield a contradiction. Thus that arc must be an interference arc, say ([v.sub.2], [v.sub.3]) without loss of generality. By minimality of (D, B), this arc cannot be removed, which means that ([v.sub.2],[v.sub.1]) and (v4, [v.sub.3]) must be backbone arcs. Now, knowing that both ([v.sub.2], [v.sub.1]) and(v4, [v.sub.3]) are backbone arcs, and [v.sub.2], [v.sub.3] are 2-vertices, the last part of the first item follows from Claim 4.9. Now assume ([v.sub.1],[v.sub.2], [v.sub.3]) is a 1-thread. If none of its two arcs is a backbone arc, then [v.sub.2] could be just removed from (D,B), contradicting its minimality. So one of its two arcs is a backbone arc, and its end different from [v.sub.2] must be a 7+-vertex by Claim 4.9.

For an irreducible 2-thread ([v.sub.1],[v.sub.2], [v.sub.3], [v.sub.4]), we define [v.sub.1] (resp. v4) as the support vertex of [v.sub.2] (resp. [v.sub.3]). For an irreducible 1-thread ([v.sub.1], [v.sub.2], [v.sub.3]), we know that at least one of the two arcs is a backbone arc; we here define the support vertex of [v.sub.2] as being the end of that arc different from [v.sub.2] (if the two of [v.sub.1],[v.sub.3] are candidates, then we choose any of them). For every 2-vertex of D, we have thus defined a support vertex, which is a 7+-vertex.

Similarly as for the previous claims, Claim 4.9 can be used to prove the following:

Claim 4.13. Let v be a vertex of (D, B) supporting some 2-vertices; then:

1. v supports at most two 2-vertices;

2. the number of 1-vertices adjacent to v plus the number of 2-vertices supported by v is at most 2;

3. if v is adjacent to a 1-vertex and a 2-vertex it supports, then d(v) [greater than or equal to] 13;

4. if v is adjacent to two 2-vertices it supports, then d(v) [greater than or equal to] 12.

Proof of the claim. The first item is because [DELTA]+(B) [less than or equal to] 1 and, by definition, vertices support adjacent 2-vertices via backbone arcs. The second item follows from these reasons, and the fact that the only arc incident to a 1-vertex must be a backbone arc, by the minimality of (D,B). The third and fourth items follow from Claim 4.9, by considering the two backbone arcs incident to v going to the two vertices with degree 1 or 2 (recall that these two backbone arcs have different directions with respect to v, due to the backbone restrictions).

2. First discharging process

To every vertex v of D, we assign an initial charge [omega](v) = 2d(v) - 6. To every face f, we assign an initial charge [omega](f) = d(f)-6. Playing with Euler's formula, we get

[mathematical expression not reproducible]

This means that the total amount of charge is strictly negative. Throughout this proof, the goal is, without creating any new charge, to move charge from elements to elements, before proving that the total amount of charge eventually gets non-negative, a contradiction.

The discharging rules of the first discharging phase are the following:

R1. Every face sends 2 to each of its incident 1-vertices.

R2. Every vertex sends 2 to each of its adjacent 1-vertices.

R3. Every vertex sends 2 to each of its adjacent 2-vertices it supports.

For every element (vertex or face) e of D, let us denote by [omega]'(e) the charge of e once rules R1 to R3 above have been performed. Let us now study the value of [omega]'(e) for each element e.

First assume that e = v is some vertex. Note that, by rules R1 to R3, only 1-vertices and 2-vertices receive some charge. According to Claims 4.10 and 4.12, only 7+-vertices can send charge, because only these types of vertices neighbour 2--vertices. By Claim 4.13, vertices can send charge to at most two adjacent vertices, and, from Claims 4.10 and 4.13, only 12+-vertices send charge to two adjacent vertices. Thus:

* If v is a 1-vertex, then v does not send any charge. It however receives 2 from its unique neighbour, via rule R2, and 2 from the unique face to which v is incident (rule R1). Thus [omega]'(v) = [omega](v) + 2 x 2 = - 4 + 4 = 0.

* If v is a 2-vertex, then, through rule R3, it receives 2 from its supporting vertex, while it does not send any charge. Thus [omega]'(v) = [omega](v) + 2 = - + 2 = 0.

* If v is a k-vertex for k [member of], then v does not send nor receive charge; thus [omega]'(v) = [omega](v) = 2k -6 > 0.

* If v is a k-vertex for k G {7,..., 11}, then v sends 2 to at most one adjacent 1-vertex or 2-vertex it supports (through rule R2 or R3), while v does not receive any charge. Thus [omega]'(v) = [omega](v) -2 [greater than or equal to] (2k -6) -2 = 2k -8 [greater than or equal to] 14 -8 = 6.

* If v is a k-vertex with k > 12, then v sends 2 to at most two adjacent 1-vertices or 2-vertices it supports (through rule R2 or R3). Also v does not receive any charge. Thus [omega]'(v) = [omega](v) - 2 x 2 [greater than or equal to] (2k - 6) - 4 = 2k - 10 > 24 - 10 = 14.

Let us finally assume that e = f is a face. Note that, through rules R1 to R3, f does not receive any charge; but f sends 2 to each 1-vertex incident to it. Let f' denote the face obtained from f by deleting all its incident 1-vertices, say there are x such. Since D has girth at least 5, we have d(f') [greater than or equal to] 5. Actually, we have d(f) = d(f') + 2x. Thus, [omega]'(f) = [omega](f) - 2x, and f, after applying the discharging rules, eventually has the same charge [omega]'(f) that a face with length d(f') would get by [omega]. Thus, [omega]'(f) < 0 only when f' is a 5-face, in which case we actually have [omega]'(f) = - 1.

We note that, at this point, the only elements e of D that verify [omega]'e) < 0 are faces f whose support, i.e., the cycle obtained after removing the 1-vertices incident to f, is a 5-cycle. More precisely, [omega]'(f) = -1 for such a face. In what follows, we apply additional discharging rules to make sure that such faces have non-negative charge, to get our final contradiction. The main argument we will use is the fact that, for every vertex v with d(v) > 3, its remaining charge [omega]'(v) is rather large. That is, all vertices v with d(v) [greater than or equal to] 4 verify [omega]' (v)/d(v) > 0. More specifically, we note that [omega]' (v)/d(v) [greater than or equal to] 0 [greater than or equal to] 1 whenever d(v) [member of] {6,8, 9,... }, while, when d(v) [member of] {4,5,7 }, we have [omega]'(v)/d(v) [greater than or equal to] 1/2. Even more specifically, we note that a 7-vertex v verifies [omega]'(v)/d(v) < 1 only when v is the support of exactly one adjacent 2-vertex (recall Claim 4.12), in which case [omega]'(v)/d(v) = 6/7.

Below, we refer to such a 7-vertex as a weak 7-vertex.

3. More reducible configurations

We focus on the 5-faces of D (which cannot be incident to 1-vertices, since D has girth at least 5) having most of their vertices being of small degree. More precisely, we say that a 5-face is bad if it has at most one vertex that is not a 3--vertex, and, if that vertex exists, it is a 4-vertex, 5-vertex or weak 7-vertex. In other words, a 5-face is not bad as soon as it has at least two 4+-vertices, or whenever it has a 6-vertex, non-weak 7-vertex, or any k-vertex with k > 8. Conversely, a face (of any length) of D is said heavy if it contains at least three 4+-vertices, including two 6+-vertices. A face of D is said almost heavy if it contains at least three 4+-vertices, including a 6+-vertex and a 5-vertex that does not belong to a bad 5-face.

Claim 4.14. (D, B) has no bad 5-face f = ([v.sub.1],..., [v.sub.5], [v.sub.1]) where [v.sub.1] is a 2-vertex, [v.sub.2] is a weak 7-vertex, and [v.sub.3], [v.sub.4], [v.sub.5] are 3-vertices.

Proof of the claim. Assume (D, B) has such a bad 5-face f. For each [v.sub.i] of [v.sub.3],[v.sub.4], [v.sub.5], we denote by [v'.sub.i] its unique neighbour not on f.

By minimality of (D, B) and by Claim 4.9, the arc joining [v.sub.1] and [v.sub.5] cannot be a backbone arc, which implies that the arc joining [v.sub.1] and [v.sub.2] must be a backbone arc. Let us assume that ([v.sub.1],[v.sub.2]) is a backbone arc. By minimality of (D, B), ([v.sub.1], [v.sub.1]) is an interference arc. By the same arguments, we deduce sequentially that ([v'.sub.5],[v.sub.5]) and ([v.sub.4], [v.sub.4]) are backbone arcs, while ([v.sub.4], [v.sub.5]) and ([v.sub.4], [v.sub.3]) are interference arcs (this is because two 3-vertices cannot be joined by a backbone arc, as otherwise Claim 4.9 would yield a contradiction).

Again by minimality, we know that one of the two arcs incident to [v.sub.3] must be a backbone arc directed toward [v.sub.3]; there are two possibilities:

* ([v'.sub.3],[v.sub.3]) is a backbone arc, in which case ([v.sub.2],[v.sub.3]) must be an interference arc, by minimality of (D, B). Then we get a contradiction when applying Claim 4.9 onto ([v.sub.1],[v.sub.2]), as this arc is subject to at most six colour constraints.

* ([v.sub.2], [v.sub.3]) is a backbone arc, in which case, applying Claim 4.9 onto ([v.sub.1], [v.sub.2]), we deduce that the remaining five arcs incident to [v.sub.2] must be interference arcs directed toward [v.sub.2]. We then get a contradiction when applying Claim 4.9 onto ([v.sub.2], [v.sub.3]).

The case where ([v.sub.2],[v.sub.1]) is a backbone arc can be dealt with in a very similar way, using symmetric arguments.

Claim 4.15. (D, B) has no bad 5-face f = ([v.sub.1],..., [v.sub.5], [v.sub.1]) where all [v.sub.i]'s are 3-vertices.

Proof of the claim. Assume (D, B) has such a bad 5-face f. According to Claim 4.9, none of the arcs of f can be a backbone arc. By minimality of (D, B), this means that, for each [v.sub.i], its unique incident arc not belonging to f must be a backbone arc. For each [v.sub.i], let us denote by [v'.sub.i] its unique neighbour not in f. Assume without loss of generality that ([v.sub.1],[v'.sub.1]) is a backbone arc. By minimality of (D,B), we deduce that the two interference arcs incident to [v.sub.1] (thus on f) are directed towards [v.sub.5] and [v.sub.2]. Again by minimality, we deduce that both ([v'.sub.2] ,[v.sub.2]) and ([v'.sub.5], v5) are backbone arcs, and thus that ([v.sub.3], [v.sub.2]) and ([v.sub.4], [v.sub.5]) are interference arcs. Going on this way, we deduce that ([v.sub.3], [v'.sub.3]) and ([v.sub.4], [v'.sub.4]) are backbone arcs. We finally get to a contradiction, because the interference arc joining [v.sub.3] and [v.sub.4], whatever be its direction, cannot be involved in an indirect conflict. This is a contradiction to the minimality of (D, B).

Claim 4.16. (D, B) has no bad 5-face f = ([v.sub.1],..., [v.sub.5],[v.sub.1]) where [v.sub.1] is a weak 7-vertex, and [v.sub.2],... ,[v.sub.5] are 3-vertices.

Proof of the claim. For i = 2,3,4, 5, we denote by [v'.sub.i] the neighbour of vi not on f. Similarly as in the proof of Claim 4.15, without loss of generality we may assume that ([v.sub.3],[v'.sub.3]) and ([v'.sub.4], [v.sub.4]) are backbone arcs, while ([v.sub.3], [v.sub.2]), ([v.sub.3], [v.sub.4]) and ([v.sub.5],[v.sub.4]) are interference arcs. Since [v.sub.1] is weak, it is adjacent to a 2-vertex [v'.sub.1], thus not on f. Also, the arc joining [v.sub.1] and [v'.sub.1] is a backbone arc, since [v.sub.1] supports [v.sub.1].

Assume ([v.sub.1],[v'.sub.1]) is a backbone arc. By Claim 4.9, at least five of the other six arcs incident to [v.sub.1] must be interference arcs out-going from [v.sub.1]. If ([v.sub.5], [v.sub.1]) or ([v.sub.2], [v.sub.1]) is a backbone arc, then we get a contradiction by applying Claim 4.9 onto it. Thus, both ([v.sub.1], [v.sub.2]) and ([v.sub.1],[v.sub.5]) are interference arcs. Also, ([v.sub.5], [v'.sub.5]) and ([v'.sub.2], [v.sub.2]) are backbone arcs. In that situation, we get, in particular, that the arc ([v.sub.1],[v.sub.5]) is useless, contradicting the minimality of (D, B).

Lastly, if ([v'.sub.1], [v.sub.1]) is a backbone arc, then reversing the arguments used to deal with the previous case also gives a contradiction in all cases.

Claim 4.17. If (D, B) has a bad 5-face f = ([v.sub.1],..., [v.sub.5],[v.sub.1]) where [v.sub.1] is a 4-vertex and [v.sub.2],... ,[v.sub.5] are 3-vertices, then [v.sub.1] is also incident to a heavy face.

Proof of the claim. For i = 2,3,4, 5, we denote by [v'.sub.i] the neighbour of [v.sub.i] not on f. Similarly as in the proof of Claim 4.15, without loss of generality we may assume that ([v.sub.3],[v.sub.3]) and ([v'.sub.4], [v.sub.4]) are backbone arcs, while ([v.sub.3], [v.sub.2]), ([v.sub.3], [v.sub.4]) and ([v.sub.5],[v.sub.4]) are interference arcs. Also, since [v.sub.1] is is a 4-vertex, still by Claim 4.9 none of the arcs joining [v.sub.5] and [v.sub.1], and [v.sub.2] and [v.sub.1] can be a backbone arc. By minimality of (D, B), we deduce that ([v.sub.5],[v.sub.5]) and ([v'.sub.2], [v.sub.2]) must be backbone arcs, while ([v.sub.5],[v.sub.1]) and ([v.sub.1],[v.sub.2]) are interference arcs.

Still by minimality of (D, B), the presence of these two arcs imply that the two remaining arcs incident to [v.sub.1] must be backbone arcs, one ([v.sub.1], [v'.sub.1]) being directed away from [v.sub.1], one ([v".sub.1], [v.sub.1]) being directed toward [v.sub.1]. Claim 4.9, applied to these arcs, now implies that v'1 and v'1 are both 6+-vertices. The face that contains [v.sub.1],[v'.sub.1], [v".sub.1] is then the desired heavy face.

Claim 4.18. If (D, B) has a bad 5-face f = ([v.sub.1],..., [v.sub.5],[v.sub.1]) where [v.sub.1] is a 5-vertex and [v.sub.2],... ,[v.sub.5] are 3-vertices, then [v.sub.1] is also incident to a heavy face or to an almost-heavy face.

Proof of the claim. As in the proof of Claim 4.17, we may assume that ([v'.sub.2],[v.sub.2]), ([v.sub.3],[v'.sub.13), ([v'.sub.4],[v.sub.4]) and ([v.sub.5],[v'.sub.5]) are backbone arcs, while ([v.sub.3],[v.sub.2]), ([v.sub.3],[v.sub.4]), ([v.sub.1],[v.sub.2]), ([v.sub.5],[v.sub.4]) and ([v.sub.5],[v.sub.1]) are interference arcs. Again by minimality of (D, B), two of the three remaining arcs incident to v1 must be backbone arcs, one being directed toward [v.sub.1], one being directed away from [v.sub.1]. Let us thus denote ([v.sub.1],[v'.sub.1]) and ([v".sub.1], [v.sub.1]) the two backbone arcs incident to v1. Without loss of generality, we may assume that ([v.sub.1],[v"'.sub.1]) is an interference arc, where [v'".sub.1] [not equal to] [v'.sub.1], [v".sub.1] does not belong to f.

Note that, for any i [member of] {2,..., 5}, applying Claim 4.9 on the arc joining [v.sub.i] and [v'.sub.i] yields that [v'.sub.i] must be a 6+-vertex. Applying Claim 4.9 on ([v".sub.1] [v.sub.1]), we deduce that [v".sub.1] is a 6+-vertex. Applying the claim on ([v.sub.1], [v'.sub.1]), we deduce that [v'.sub.1] is a 5+-vertex. If [v'.sub.1] is a 6+ vertex, then we are done, because either [v.sub.1],[v'.sub.5] and one of [v'.sub.1], [v".sub.1] all belong to a same heavy face, or [v.sub.1], [v'.sub.1] and one of [v'.sub.1],[v".sub.1] all belong to a same heavy face. Thus, we may assume that [v'.sub.1] is a 5-vertex. Again, we note that the two faces containing the arc ([v"'.sub.1], [v.sub.1]) cannot include one of [v'.sub.2] or [v'.sub.5], as otherwise we would get a heavy face including [v.sub.1], [v".sub.1] and [v.sub.2] or [v'.sub.5]. Thus, we may assume that one face incident to ([v.sub.1],[v'.sub.1]) contains [v'.sub.5], while one face incident to ([v.sub.1],[v"'.sub.1]) contains [v'.sub.2]. Now, after removing ([v.sub.1],[v'.sub.1]) from (D, B), if a 7-BMRN*-colouring of the remaining backboned digraph cannot be extended to ([v.sub.1],[v'.sub.1]), then it means that each of the other four arcs incident to [v'.sub.1] must each be either a backbone arc out-going from [v'.sub.1], or an interference arc in-coming to [v'.sub.1]. This prevents [v'.sub.1] from being part of a bad 5-face, as, as seen so far, a 5-vertex being the only 4+-vertex of a bad 5-face must be incident to an out-going interference arc and an in-coming interference arc (just as [v.sub.1] in f). Since [v'.sub.1] does not belong to any bad 5-face, we have that the face containing [v.sub.1],[v'.sub.1],[v'.sub.5] is an almost-heavy face containing [v.sub.1].

The arguments used in the proofs of Claims 4.17 and 4.18 yield another property of bad 5-faces having a 4-vertex or a 5-vertex.

Claim 4.19. If (D, B) has a bad 5-face f = ([v.sub.1],... ,[v.sub.5],[v.sub.1]) where [v.sub.1] is a 4-vertex or 5-vertex and [v.sub.2],... ,[v.sub.5] are 3-vertices, then v1 is not incident to another bad 5-face.

Proof of the claim. By the arguments used in the proof of Claim 4.18, if [v.sub.1] is a 4-vertex or 5-vertex being the only 4+-vertex of a bad 5-face f, then the two arcs incident to [v.sub.1] on f must be one out-going interference arc and one in-coming interference arc. Furthermore, two of the other arcs incident to v1 must be one out-going backbone arc and one in-coming backbone arc. Also, f must have its five arcs being interference arcs, and the four arcs incident to the four 3-vertices of f must be backbone arcs. From all these arguments, it is easy to check that the statement is true. In particular, one way to see this is that, under all these assumptions, all faces (different from f) containing [v.sub.1] include a backbone arc.

4. Second discharging process

For the second discharging phase, we apply, from the charge function [omega]', these rules:

R4. Every 4-vertex v that is not a 4-vertex or a 5-vertex incident to a bad 5-face sends w'(v)/d(v) to each of the at most d(v) faces it is incident to.

R5. Every 4-vertex or 5-vertex v incident to a bad 5-face sends w'(v)/d(v) to each of the at most d(v) non-heavy and non-almost-heavy faces it is incident to. Furthermore, v sends another w'(v)/d(v) to each bad 5-face it is incident to.

For every vertex or face e of D, let us denote by [omega]"(e) the charge of e once rules R4 and R5 have been applied. We now analyze how [omega]'(e) was altered to [omega]"(e), for each element e.

First, assume e = v is a vertex. Note that, by the rules, no vertex receives charge, and thus we necessarily have [omega]"(v) [less than or equal to] [omega]'(v). If d(v) [less than or equal to] 3, then no charge is sent by v, which means that [omega]"(v) = [omega]'(v) = 0.

If v is not a 4-vertex or 5-vertex incident to a bad 5-face, then, by rule R4, v splits its charge between the at most d(v) faces it is incident to. Thus [omega]" (v) [greater than or equal to] [omega]' (v) - d(v) x w'(v)/d(v) = 0. Now, if v is a 4-vertex or 5-vertex incident to a bad 5-face, then, by Claims 4.17, 4.18 and 4.19, v is incident to at most one bad 5-face f and at least one heavy or almost-heavy face f . By rule R5, v sends w'(v)/d(v) to each incident face (including f) but f, and instead sends another w'(v)/d(v) to f. Thus v sends w'(v)/d(v) at most d(v) times, and [omega]" (v) > [omega]' (v) - d(v) x w'(v)/d(v) = 0 .

Second, assume e = f is a face. By rules R4 and R5, no face sends charge. Thus [omega]"(f) > [omega]'(f). Furthermore, as stated earlier we already have [omega]'(f) > 0 whenever the support of f is not a 5-cycle. So, we may now focus on those cases where the support of f is a 5-cycle, in which case [omega]'(f) = -1. If f is not a 5-face, then f is incident to a 1-vertex u. By Claim 4.10, the neighbour v of u is an 8+-vertex, and v also is incident to f. ByruleR4, vertexv sends w'(v)/d(v) [greater than or equal to] 1 to f, and thus [omega]" (f > [omega]' (f) + w'(v)/d(v) [greater than or equal to] -1 + 1 = 0. The last case to consider is when f is actually a 5-face. First assume that f is not bad. If f is not heavy and almost-heavy, then f contains at least two 4+-vertices v, v which, through rule R4, send w'(v)/d(v),w'(v)/d(v)) [greater than or equal to] 12 to f. Thus [omega] (f) [greater than or equal to] [omega] (f)+ w'(v)/d(v) + w'(v)/d(v) [greater than or equal to] - 1 + 2 x 1/2 =0. If f is heavy or almost-heavy, then f contains either two 6+-vertices v, v', or a 6+-vertex v and a 5-vertex v' that does not belong to any bad 5-face. By ruleR4, v and v send w'(v)/d(v), w'(v)/d(v)) [greater than or equal to] 1/2 to f. Thus [omega]" (f) [greater than or equal to] [omega]' (f) + w'(v)/d(v) + w'(v)/d(v) [greater than or equal to]-1 + 2x12=0. We may thus lastly assume that f is a bad 5-face. By definition, f thus has at most one 4+-vertex. By Claim 4.15, f cannot have only 3-vertices. By Claim 4.12, f cannot have two consecutive 2-vertices (a 2-thread), as otherwise f would have at least two 7+-vertices, and would thus not be bad. If f has a 2-vertex, then, by the same claim, f must have a 7+-vertex v, which we may assume is a 7-vertex by definition of bad 5-face. We may also assume that v is weak, as otherwise, by rule R4, v would send w'(v)/d(v) [greater than or equal to] 1 to f , and thus [omega]" f [greater than or equal to] [omega] (f) + w'(v)/d(v) [greater than or equal to] -1 + 1 = 0. Now, because v is the only 4+-vertex of f, a second 2-vertex of f must be adjacent to v (still by Claim 4.12). Furthermore, v must be the support of these two 2-vertices (by definition of a supporting vertex); this is a contradiction to Claim 4.13, which states that a vertex adjacent to two 2-vertices must be a 12+-vertex. Consequently, if f is a bad 5-face containing a 2-vertex, then this 2-vertex is adjacent to a weak 7-vertex (that supports it) in f, and the remaining three vertices of f are 3-vertices; this is the configuration described in Claim 4.14, which is forbidden.

We may thus assume that f is a bad 5-face having exactly one 4-vertex, one 5-vertex, or one weak 7-vertex v, while the other four vertices of f are 3-vertices. By Claim 4.16, actually v cannot be a weak 7-vertex. Thus v is a 4-vertex or 5-vertex, and, by Claims 4.17 and 4.18, it sends 2 x w'(v)/d(v) to , while w'(v)/d(v) [greater than or equal to] 2. Then w" (f) [greater than or equal to] w'(f)+ 2 x w'(v)/d(v) [greater than or equal to]-1 + 2x2=0.

Thus, we now have

[mathematical expression not reproducible]

the desired contradiction. Thus, (D, B) cannot exist and the claim is true.

5 Conclusion

Following [3], we have investigated, in this work, the behaviour of the BMRN*-index of planar backboned digraphs, answering some open questions from that seminal work. We have exhibited planar spanned digraphs with BMRN*-index 8, which meets the upper bound for that class of digraphs. We have proved that the Planar k-BMRN*-Colouring problem is NP-hard for every k [member of] {3,..., 6}, even when restricted to planar spanned digraphs. Finally, we have investigated how the BMRN*-index of a planar backboned digraph behaves in front of its girth.

We however leave a few aspects open, which we believe might be interesting to study in a later work. First, we have proved that the BMRN*-index of a planar backboned digraph can be as large as 8, and it thus makes sense wondering about the structure of planar backboned digraphs with large BMRN* -index. In particular:

Question 5.1. What is the complexity of Planar 7-BMRN*-Colouring?

Our approach of using crossover gadgets is of course still applicable here. However, we were not able to design 7-crossover gadgets. Designing such gadgets indeed requires lots of interference arcs, which hardly comply with the planarity requirement. Nevertheless, our bet is that Planar 7-BMRN*-Colouring should also be NP-hard.

Another remaining algorithmic question is about the complexity of Planar k-BMRN-Colouring for planar spanned digraphs, the variant of Planar k-BMRN*-Colouring for BMRN-colouring. Recall that the difference between BMRN-colouring and BMRN*-colouring is that, by the former, it is not mandatory, for every vertex, that all incident out-going backbone arcs are assigned the same colour. Thus, the only context where BMRN-colouring and BMRN*-colouring coincide is when considering backbones B with [DELTA]+(B) [less than or equal to] 1. As can be noted in Figure 8, the tower we have designed for our 6-crossover gadget has vertices incident to multiple out-going backbone arcs, which are crucial to ensure the planarity of the whole graph. We were unfortunately unsuccessful in designing a similar 6-crossover gadget (D, B) with [DELTA]+(B) [less than or equal to] 1; however, we feel that Planar k-BMRN-Colouring should be NP-hard when restricted to planar spanned digraphs.

Question 5.2. For every k [MEMBER OF] {4, 5,6,7}, what is the complexity of Planar k-BMRN-Colouring?

Note that it could be interesting as well to wonder about these algorithmic concerns for restricted families of planar spanned digraphs. In particular, due to the results in [3], outerplanar spanned digraphs have BMRN*-index (and, thus, BMRN-index) at most 5 (which is tight in general), and the proof of that result implies that the BMRN*-index of such a digraph can be determined in polynomial time. The same, however, was not proved for the BMRN-index of these digraphs, though we suspect it should hold true.

Question 5.3. For every k [member of] {3,4}, what is the complexity of k-BMRN-Colouring when restricted to outerplanar spanned digraphs?

Regarding planar backboned digraphs with large girth, we were not able to exhibit some better girth threshold above which 5-BMRN*-colourings always exist. For instance, we think the following question could be an interesting first step to consider:

Question 5.4. Is it true that every planar backboned digraph (D,B) with girth at least 11 has BMRN* -index at most 5?

We believe the value 11 in that question would be a nice value, as this is the girth threshold guaranteeing the existence of 2-threads in planar graphs with minimum degree 2 (recall Theorem 4.2). Using this fact would be a nice enhancement of our proof of Theorems 4.5 and 4.6. However, we were not successful with this approach, as several types of 2-threads cannot be reduced when five colours are allowed. It is likely that more sophisticated arguments are needed here, or even new approaches.

Another related aspect is how much can the girth conditions in Theorem 4.1 be lowered, namely for a given k [member of] {3,4, 5, 6, 7}, what is the smallest g(k) such that planar backboned digraphs (D, B) with g(D) [greater than or equal to] g(k) have BMRN*-index at most k. This is a legitimate question, as the bounds we have exhibited seem far from optimal in general.

Question 5.5. For every k [member of] {3,..., 7}, what is the smallest g(k) such that planar backboned digraphs (D, B) with g(D) [greater than or equal to] g(k) have BMRN*-index at most k?

As a first step towards the first case, that of k = 3, let us mention that there exist planar backboned digraphs with girth 6 and BMRN*-index 4, such as the one depicted in Figure 10. Thus, 7 [less than or equal to] g(3) [less than or equal to] 21.

Finally, it might be interesting to focus on particular classes of planar digraphs. For instance, in [3], the authors proved that the BMRN*-index of an outerplanar backboned digraph is at most 5, which is tight. Another interesting class of planar digraphs to consider could be that of grids (triangular, square, etc.). An intriguing case is that of square grids. It is fairly easy to see that the BMRN*-index of a backboned directed square grid (D, B) is at most 5, because grids admit distance-2 5-colourings (which can be derived to 5-BMRN*-colourings of (D, B), as mentioned in the introduction). Regarding lower bounds, one can easily come up with example of backboned directed square grids with BMRN*-index 4. However, even via lots of computer experimentations, we were not able to find backboned directed square grids with BMRN* -index 5. This makes us wonder about the following question, which would be interesting to answer towards understanding better the connection between BMRN*-colourings and distance-2 colourings.

Question 5.6. Is it true that every backboned directed square grid has BMRN* -index at most 4?

References

[1] K. Appel, W. Haken. Every planar map is four colorable. I. Discharging. Illinois Journal of Mathematics, 21:429-490, 1977.

[2] K. Appel, W. Haken, J. Koch. Every planar map is four colorable. II. Reducibility. Illinois Journal of Mathematics, 21:491-567, 1977.

[3] J. Bensmail, T. Blanc, N. Cohen, F. Havet, L. Rocha. Backbone colouring and algorithms for TDMA scheduling. Discrete Mathematics and Theoretical Computer Science, 21(3), 2019, #24.

[4] G.J. Chang, G.-H. Duh. On the precise value of the strong chromatic index of a planar graph with a large girth. Discrete Applied Mathematics, 247:389-397 2018.

[5] M.R. Garey, D.S. Johnson, L. Stockmeyer. Some simplified NP-complete graph problems. Theoretical Computer Science, 1(3):237-267, 1976.

[6] H. Grotzsch. Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz fur dreikreisfreie Netze auf der Kugel. Wiss. Z. Martin-Luther-U., Halle-Wittenberg, Math.-Nat. Reihe, 8:109-120, 1959.

(i) Throughout this work, to make the distinction between backboned digraphs and spanned digraphs clear, whenever possible we write (D, B) for a backboned digraph and (D,T) for a spanned digraph.
COPYRIGHT 2021 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2021 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Bensmail, Julien
Publication:Discrete Mathematics and Theoretical Computer Science
Article Type:Report
Geographic Code:1USA
Date:Jan 1, 2021
Words:19864
Previous Article:Exponential multivalued forbidden configurations.
Next Article:Binary patterns in the Prouhet-Thue-Morse sequence.
Topics:

Terms of use | Privacy policy | Copyright © 2022 Farlex, Inc. | Feedback | For webmasters |