Printer Friendly

Edge-partitioning graphs into regular and locally irregular components.

A graph is locally irregular if every two adjacent vertices have distinct degrees. Recently, Baudon et al. introduced the notion of decomposition into locally irregular subgraphs. They conjectured that for almost every graph G, there exists a minimum integer [[chi]'.sub.irr] (G) such that G admits an edge-partition into [[chi]'.sub.irr] (G) classes, each of which induces a locally irregular graph. In particular, they conjectured that [[chi]'.sub.irr] (G) [less than or equal to] 3 for every G, unless G belongs to a well-characterized family of non-decomposable graphs. This conjecture is far from being settled, as notably (1) no constant upper bound on [[chi]'.sub.irr](G) is known for G bipartite, and (2) no satisfactory general upper bound on [[chi]'.sub.irr](G) is known.

We herein investigate the consequences on this question of allowing a decomposition to include regular components as well. As a main result, we prove that every bipartite graph admits such a decomposition into at most 6 subgraphs. This result implies that every graph G admits a decomposition into at most 6([log[chi](G)] + 1) subgraphs whose components are regular or locally irregular.

Keywords: regular graph, locally irregular graph, regular-irregular decomposition

1 Introduction

It is a well-known fact that, in every simple graph, there have to be at least two vertices with the same degree. If we define a totally irregular graph as a graph whose every two distinct vertices have distinct degrees, then this folklore result, put differently, says that no totally irregular simple graph with order at least 2 exists. Several works then aimed at introducing and studying antonyms of the notion of regular simple graphs. The such notion investigated throughout this paper is the one of locally irregular graphs, which are graphs in which every two adjacent vertices have distinct degrees.

Our investigations are motivated by the recent work of Baudon et al. in [2] wherein is considered the following decomposition problem. Clearly a simple graph G does not have to be locally irregular (consider e.g. any regular graph). In such a situation, we would like to decompose G into locally irregular subgraphs, where by a decomposition of G into k locally irregular subgraphs we refer to a partition [E.sub.1] [union] [E.sub.2] [union]... [union] [E.sub.k] of E(G) such that G[[E.sub.i]] is locally irregular for every i [member of] {1, 2,..., k}. A decomposition of G into k locally irregular subgraphs can equivalently be seen as a k-edge-colouring of G whose each colour class induces a locally irregular subgraph. Such an edge-colouring is said locally irregular. From this point of view, as usual we are interested in finding the least number of colours used by a locally irregular edgecolouring of G (if any). This parameter, which is denoted [[chi]'.sub.irr](G), is called the irregular chromatic index of G.

It is important to mention that there exist graphs for which the irregular chromatic index is not defined, that is graphs which cannot be decomposed into locally irregular subgraphs at all (consider [K.sub.2] for an easy example). Such graphs, said exceptional, were fully characterized in [2]. Namely, a graph G is exceptional if and only if (1) G is an odd-length path, (2) G is an odd-length cycle, or (3) G belongs to the family T, described inductively as follows. First, the triangle [K.sub.3] belongs to T. Every other graph of T can then be constructed by taking an auxiliary graph F being either an even-length path or an odd-length path with a triangle glued to one of its ends, then choosing a graph H [member of] T containing a triangle with at least one vertex v of degree 2 in H, and finally identifying v with a vertex of degree 1 of F.

Theorem 1 ([2]). A graph G is exceptional if and only if (1) G is an odd-length path, (2) G is an odd-length cycle, or (3) G belongs to T.

Regarding non-exceptional graphs, Baudon et al. conjectured the following in [2].

Conjecture 2 ([2]). For every non-exceptional graph G, we have [[chi]'.sub.irr](G) [less than or equal to] 3.

Conjecture 2 was verified for several classes of graphs, including trees, complete graphs, Cartesian products of graphs verifying Conjecture 2, and regular graphs with degree at least [10.sup.7], see [2]. This latter result was proved by means of a probabilistic approach and is perhaps the most significant one as regular graphs are in some sense the "least locally irregular" graphs. It is worth mentioning that Conjecture 2, if true, would be sharp since some graphs have irregular chromatic index 3, like e.g. [C.sub.6]. There actually even exist infinitely many trees with irregular chromatic index 3, as pointed out in [3], though the authors noted that the irregular chromatic index of every tree can be determined in linear time.

No weaker version of Conjecture 2 involving another (possibly big) constant term has been proved at the moment, and we believe such should be hard to prove. Actually, the only known explicit upper bound on the irregular chromatic index of non-exceptional graphs is the following, exhibited in [2].

Theorem 3 ([2]). For every non-exceptional graph G, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The upper bound in Theorem 3 was only exhibited for theoretical and existential purposes, that is to show the existence of a locally irregular edge-colouring of every graph which is not exceptional. Roughly speaking, the proof of Theorem 3 shows that every non-exceptional graph can be decomposed into edge-disjoint [P.sub.3]'s, which is the smallest (non-trivial) locally irregular graph. In particular, this proof does not take into account that a locally irregular graph does not have to be connected.

The status of Conjecture 2 (or even a weaker version of it) for bipartite graphs is quite intriguing. Although it can be easily shown that Conjecture 2 is true when restricted to particular families of bipartite graphs (including trees, complete bipartite graphs, regular bipartite graphs, see [2]), we are still far from an argument settling the general bipartite case.

Question 4. Can we prove that, for some absolute constant k [greater than or equal to] 3 and every non-exceptional bipartite graph G, we have [[chi]'.sub.irr](G) [less than or equal to] k?

When dealing with Question 4 (or more generally Conjecture 2), one might be tempted to invoke inductive arguments to prove an upper bound on [[chi]'.sub.irr]. Many reasons unfortunately make this approach unlikely to work. In particular, when removing some elements from a graph, we may be left with components isomorphic to [K.sub.2], which we cannot colour as it may spoil the local irregularity of the coloured subgraph, or make that colour induce a component isomorphic to [K.sub.2]. Mainly because of this reason, we have the feeling that knowing how to deal with [K.sub.2] components might be one of the keystones for tackling Question 4 and Conjecture 2.

Our investigations are hence motivated by the following resulting question: How easier can Question 4 (and Conjecture 2) be tackled if we allow a locally irregular edge-colouring to induce connected components isomorphic to [K.sub.2]? Or, more generally, regular components? This leads to the notion of regular-irregular graph, which we define as a graph whose each connected component is either regular or locally irregular (i). So the question of interest above can now be rephrased as follows: What is the least number of colours in an edge-colouring c of a (not necessarily) bipartite graph, such that each colour class of c induces a regular-irregular graph?

This paper is organized as follows. In Section 2, we start by introducing the notion of regular-irregular chromatic index of graphs, and exhibit very first properties of it. In Section 3 we raise a conjecture on the regular-irregular chromatic index of all graphs, and support it by showing it to (sometimes almost) hold when restricted to particular families of graphs. We then focus on bipartite graphs in Section 4. As a main result, we show that every bipartite graph has regular-irregular chromatic index at most 6. This result implies, in Section 5.1, that every graph G has regular-irregular chromatic index at most 6( [log [chi](G)] + 1), where [chi](G) denotes the classic chromatic number of G. In Section 5.2, we explain why a promising decomposition approach introduced by Addario-Berry et al. in [1] does not seem to be applicable to deduce a better upper bound on the regular-irregular chromatic index. To this end, we show the NP-completeness of the problem of deciding whether a graph with a particular structure admits a particular locally irregular subgraph. Concluding remarks are gathered in Section 6.

2 Decomposing graphs into regular-irregular graphs

We say that an edge-colouring c of a graph G is regular-irregular if every colour class of c induces a regular-irregular graph. The first important thing to note is that, unlike locally irregular edge-colouring, a regular-irregular edge-colouring may induce components isomorphic to [K.sub.2], which is 1-regular. Consequently, by colouring each edge of a graph with a different colour, we get a regular-irregular edge-colouring (inducing regular components only). So the regular-irregular chromatic index of every graph G, which we define as the least number [[chi]'.sub.reg-irr](G) of colours used by a regular-irregular edge-colouring of G, is defined.

Observation 5. For every graph G, we have [[chi]'.sub.reg-irr](G) [less than or equal to] |E(G)|.

As every locally irregular edge-colouring is clearly also regular-irregular, all results on locally irregular edge-colouring of graphs naturally apply to regular-irregular edge-colouring. In particular, we can improve Observation 5 using Theorem 3, as it can be easily checked by hand that every exceptional graph can be made colourable by just removing one edge from it.

Corollary 6. For every graph G, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

In a regular-irregular k-edge-colouring c of a graph G, by definition each colour i of c can induce a subgraph whose some components are regular (forming a subgraph [G.sub.r,i] made up of regular components), while the other components are locally irregular (forming a locally irregular subgraph [G.sub.l,i]). It is worth mentioning that, from c, we can easily deduce a 2k-edge-colouring c' of G where every colour of c' induces either regular components only, or locally irregular components only. Typically c' can be obtained from c by considering every colour i [member of] {1,2,..., k} of c, and colouring the edges of [G.sub.r,i] with colour i' and the edges of [G.sub.l,i] with colour i". So all upper bounds on [[chi]'.sub.reg-irr] exhibited throughout this paper yield upper bounds on this modified edge-colouring notion.

Other relationships between the regular-irregular chromatic index and other graph invariants and notions can be expressed. To begin with, since a proper edge-colouring of a graph is an edge-colouring whose each colour induces a forest of [K.sub.2] 's (which are 1-regular), by Vizing's Theorem [6] we can immediately improve Observation 5 to the following, where [chi]' denotes the classic chromatic index parameter. Observation 7. For every graph G, we have

[[chi]'.sub.reg-irr](G) [less than or equal to] [chi]'(G) [less than or equal to] [DELTA](G) + 1.

The arboricity of a graph G, denoted a(G), is the least number of colours of an edge-colouring of G where every colour induces a forest. Since every forest has regular-irregular chromatic index at most 2, see upcoming Lemma 10, we directly get the following.

Observation 8. For every graph G, we have [[chi]'.sub.reg-irr](G) [less than or equal to] 2a(G).

Of course, Observation 8 can be extended to every variant of the arboricity parameter, as long as the resulting induced subgraphs have bounded regular-irregular chromatic index. For instance, the star arboricity of G, denoted s(G), is the least number of colours used by an edge-colouring of G inducing forests of stars. Since every star is either regular (when it has order 2) or locally irregular (otherwise), we directly get that [[chi]'.sub.reg-irr](G) [less than or equal to] s(G) for every graph G.

3 On graphs with constant regular-irregular chromatic index

In previous Section 2, we have expressed relationships between the regular-irregular chromatic index and generally unbounded (by some constant) graph invariants. But the relationship between the regularirregular chromatic index and the irregular chromatic index, recall Corollary 6, and Conjecture 2 suggest that the regular-irregular chromatic index of every graph should be at worst bounded above by 3. Investigations on small graphs (in particular those with irregular chromatic index 3) even suggest that the following stronger conjecture should be true.

Conjecture 9. For every graph G, we have [[chi]'.sub.reg-irr](G) [less than or equal to] 2.

Several families of graphs supporting Conjecture 9 can be pointed out. First, every regular or locally irregular graph has regular-irregular chromatic index 1 and, thus, directly agrees with Conjecture 9. Among the families of regular and locally irregular graphs of interest, let us mention complete graphs (which were shown to have irregular chromatic index exactly 3 in [2]), cycles (some of which are exceptional, and some others of which have irregular chromatic index exactly 3, see [2]), and stars.

Of course trees are not all regular or locally irregular, so some of these graphs have regular-irregular chromatic index at least 2. Actually it is easily seen that trees have star arboricity at most 2, and, hence, have regular-irregular chromatic index at most 2, agreeing with Conjecture 9. We reprove this formally below as this result will be of some use in next sections.

Lemma 10. For every tree T, we have [[chi]'.sub.reg-irr](T) [less than or equal to] 2.

Proof: To obtain a regular-irregular 2-edge-colouring c of T, proceed as follows. Choose an arbitrary node r of T, and perform a breadth-first search algorithm from r. This defines a partition [V.sub.0] [union] [V.sub.1] [union]... [union] [V.sub.d] of the nodes of T where each part [V.sub.i] contains the nodes of T which are at distance exactly i from r. Basically, we have [V.sub.0] = {r} and every edge joins two nodes located in consecutive parts. Now, for every edge uv [member of] E(T) with u [member of] [V.sub.i] and v [member of] [V.sub.i+1] (for some i [member of] {0,1,..., d - 1}), set c(uv) = 1 if i [equivalent to] 0 (mod 2), or c(uv) = 2 otherwise. It should be clear that, because T is a tree, colours 1 and 2 of c induce two forests of stars, which are either regular or locally irregular. So c is regular-irregular, as claimed. []

Observation 8 can be used to show that families of graphs whose arboricity is bounded above by some constant k have their regular-irregular chromatic index bounded above by 2k. Although 2k may be larger than 2, such constant upper bounds remain of interest, especially for families of graphs whose irregular chromatic index is not known to be bounded above by some constant. In particular, one well-known result of Schnyder states that every planar graph has arboricity at most 3, see [5]. So, from Observation 8, we directly derive the following.

Theorem 11. For every planar graph G, we have [[chi]'.sub.reg-irr](G) [less than or equal to] 6.

4 On the regular-irregular chromatic index of bipartite graphs

In this section, we study Conjecture 9 with respect to bipartite graphs (i.e. the counterpart of Question 4 for regular-irregular edge-colouring). As a main result, we prove the following.

Theorem 12. For every bipartite graph G, we have [[chi]'.sub.reg-irr](G) [less than or equal to] 6.

We prove Theorem 12 by showing that every bipartite graph can be edge-partitioned into two subgraphs with regular-irregular chromatic index at most 2 and 4, respectively, namely a forest and a bipartite graph whose all components are Eulerian (ii).

We first introduce results related to Eulerian bipartite graphs.

Lemma 13. For every connected Eulerian bipartite graph G whose at least one part has even size, we have [[chi]'.sub.irr](G) [less than or equal to] 2.

Proof: Let V(G) = A [union] B be the bipartition of G, with |A| > 2 even. Set x = |A| and y = |B|. Since G is connected, by Eulerianity we have that y [greater than or equal to] 2 (as otherwise G would be a star, and hence would not be Eulerian). Set A = {[a.sub.1], [a.sub.2],..., [a.sub.x]} and B = {[b.sub.1], [b.sub.2],... , [b.sub.y]}. We prove a stronger statement, namely that G admits a 2-edge-colouring c such that:

Property 1: for every vertex a [member of] A, there are an odd number of edges incident to a which are coloured with 1 by c,

Property 2: for every vertex b [member of] B, there are an even number of edges incident to b which are coloured with 1 by c.

Since every vertex of G has even degree by Eulerianity, it should be clear that c is locally irregular as soon as it has Properties 1 and 2, then ensuring that G has irregular chromatic index at most 2.

Start by colouring with 1 all edges of G. Clearly Property 2 is already fulfilled, but no vertex of A satisfies Property 1. More precisely, due to the parity of x, an even number of vertices of A violate Property 1. Then repeatedly apply the following recolouring procedure to c. Let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

be a simple path (i.e. with no repeated [a.sub.i]'s or [b.sub.i]'s) of G joining a| and a2. Such exists as G is connected. Now just "invert" the colours used by c on the edges of P, i.e. the colours of the edges among

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

That is, colour with 2 every such edge coloured with 1, and vice-versa. Note that this procedure has the property that only the endvertices of P, which are [a.sub.1] and [a.sub.2], have the parity of their number of edges coloured with 1 by c changed. So [a.sub.1] and [a.sub.2] do not violate Property 1 any more, and no new vertex violating either Property 1 or 2 arose from the recolouring. Repeating the same procedure with [a.sub.3] and [a.sub.4] (instead of [a.sub.1] and [a.sub.2]), then [a.sub.5], and [a.sub.6], and so on, we eventually get c satisfying both Properties 1 and 2. []

Note that the proof of Lemma 13 only applies to connected Eulerian bipartite graphs having a part with even size since the recolouring procedure, when applied once, makes only two new vertices of A meet Property 1. In particular, if the two parts of G have odd size, then, applying the same modification scheme on A, we can only fix an even number of conflicts while there are an odd number of them. So we have to handle these specific bipartite graphs separately.

For this purpose, we first need to introduce a specific class of bipartite graphs. In what follows, an almost locally irregular bipartite graph designates a bipartite graph G with bipartition A[union] B satisfying the following:

* there is a specific vertex a [member of] A such that d(a) is even and all vertices of A \ {a} have odd degree,

* all vertices of B have even degree.

So G can actually be locally irregular (typically when the degree of a is different from the degrees of its neighbours), but, if it is not, then the only adjacent vertices with the same degree in G are necessarily a and some of its neighbours.

We prove below that every connected almost locally irregular bipartite graph has regular-irregular chromatic index at most 3.

Lemma 14. For every connected almost locally irregular bipartite graph G, we have [[chi]'.sub.reg-irr](G) [less than or equal to] 3.

Proof: We use the terminology introduced above to deal with the bipartition of G and its specific vertex a all along this proof. If G is locally irregular, then clearly [[chi]'.sub.reg-irr](G) = 1, so now assume G is not locally irregular. We show below that we can find a subset P [subset] E(G) of edges such that G - P is locally irregular and P induces a forest. Once such a decomposition of G is obtained, a regular-irregular 3-edge-colouring of G is obtained by colouring with 1 all edges of G - P and using at most two other colours for the edges of G[P] (according to Lemma 10), implying the claim.

Start with P = [??]. Because of the structure of G, as mentioned earlier necessarily the (possible multiple) conflicts why G is not locally irregular involve a and neighbours of a with degree [d.sub.G](a). Arbitrarily choose one such vertex [b.sub.1], and add a[b.sub.1] to P. Clearly P induces a path. Besides, note that, due to the structure of G, no neighbour of a in G - P has degree [d.sub.G-P](a) = [d.sub.G](a) - 1, since this value is odd. So a cannot be involved in any conflict making G - P being not locally irregular. Actually the only neighbour of a in G with odd degree in G - P is [b.sub.1], but a and [b.sub.1] are not adjacent in G - P.

If G - P is locally irregular, then we are done. Otherwise, since G - P is a bipartite graph whose all vertices in A have odd degree and all vertices in B but [b.sub.1] have even degree, it means that there is at least one vertex [a.sub.2] [member of] A such that [b.sub.1][a.sub.2] [member of] E(G - P) and [d.sub.G-P]([b.sub.1]) = [d.sub.G-P]([a.sub.2]). Recall that [a.sub.2] [not equal to] a. So just add [b.sub.1][a.sub.2] to P. For similar reasons as above, we now have [d.sub.G-P]([b.sub.1]) = [d.sub.G-P](a) - 1 = [d.sub.G](a) - 2, all vertices of B have even degree in G - P, and all vertices of A but a2 have odd degree in G - P. Again, if G - P is still not locally irregular, then necessarily there is at least one vertex [b.sub.3] [not equal to] [b.sub.1] neighbouring [a.sub.2] such that [d.sub.G-P]([a.sub.2]) = [d.sub.G-P]([b.sub.3]). So just add [a.sub.2][b.sub.3] to P. And so on.

The important thing to note is that the degree sequence

([d.sub.G-P](a), [d.sub.G-P]([b.sub.1]), [d.sub.G-P]([a.sub.2]), [d.sub.G-P]([b.sub.3]),...)

is strictly decreasing, except for its two last values which are equal. More precisely, because of all the successive conflicts which had to be fixed, in G we have

[d.sub.G](a) = [d.sub.G]([b.sub.1]), [d.sub.G]([a.sub.2]) = [d.sub.G]([b.sub.1]) - 1, [d.sub.G]([b.sub.3]) = [d.sub.G]([a.sub.2]) - 1,... .

This property has two consequences. On the one hand, because the degrees in G of the ends of the successive edges added to P are strictly decreasing, the recolouring procedure cannot last forever. So eventually, assuming G - P has never been locally irregular before, an edge, say, [a.sub.i][b.sub.i+1] with [d.sub.G-P]([a.sub.i]) = [d.sub.G-P]([b.sub.i+1]) = 1 will be added to P, making [b.sub.i+1] having degree 0 in the next occurrence of G - P and, hence, impossible to be involved in any degree conflict. Said differently, the remaining graph G - P is necessarily locally irregular at this point.

On the other hand, the fact that the degree sequence is strictly decreasing (except for its last two terms) implies that G[P] has no cycle. Assume indeed that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [i.sub.p] < [i.sub.p+1] for every p [member of] {1,2,..., k - 1}, is one smallest cycle of G[P]. Due to the bipartiteness of G, this cycle has length at least 4, so k [greater than or equal to] 4. According to the arguments above, the edge [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] was added to P because, at some point, we had [d.sub.G-P]([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) = [d.sub.G-P]([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]). But, at this very moment, we had, say, [d.sub.G-P]([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) = d, and hence

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

according to the above arguments, and, in particular,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

But d - k [not equal to] d since k [greater than or equal to] 4, a contradiction.

So, at the end of the described above procedure, G[P] has no cycle, and is hence a forest. Actually it can be easily seen that G[P] is a path, but both forests and paths have regular-irregular chromatic index at most 2, recall Lemma 10. Besides, G - P is locally irregular, as claimed. []

Using Lemma 14, we can now deal with connected Eulerian bipartite graphs whose two parts have odd size.

Lemma 15. For every connected Eulerian bipartite graph G whose two parts have odd size, we have [[chi]'.sub.reg-irr](G) [less than or equal to] 4.

Proof: Let V(G) = A [union] B denote the bipartition of G, and set x = |A| and y = |B|, where x, y [greater than or equal to] 3 (as otherwise G would be a star, and hence would not be Eulerian) are odd numbers. As in the proof of Lemma 13, we deduce a regular-irregular 4-edge-colouring of G by modifying an initial edge-colouring c of G using only one colour, then two, and finally at most four. If at some point of the procedure c becomes regular-irregular, then of course we end up the procedure immediately.

Start by colouring with 1 all edges of G. Let a be an arbitrary vertex of G which is not a cut vertex. Without loss of generality, we may suppose that a G A (otherwise, just relabel the parts A and B). Set A = {a, [a.sub.1], [a.sub.2],... , [a.sub.x-2], [a.sub.x-1]} and G' = G - {a}. Now, for every odd i [member of] {1, 3, 5,... , x - 2}, similarly as in the proof of Lemma 13 choose an arbitrary simple path P of G' starting from [a.sub.i] and ending at [a.sub.i+1] (such exists since G' is connected by our choice of a), and colour with 2 all edges along P coloured with 1 by c, and vice-versa.

For similar reasons as in the proof of Lemma 13, at the end of the procedure, the edge-colouring c, which is now a 2-edge-colouring, fulfils the following:

Property 1: every vertex in A \ {a} is incident to an odd number of edges coloured with 1 by c in G,

Property 2: every vertex in B is incident to an even number of edges coloured with 1 by c in G.

Besides, since the above procedure was performed on paths in G', we also have the following:

Property 3: all edges incident to a in G are coloured with 1 by c.

Since G is Eulerian, note that this last property equivalently means that a is incident to an even number of edges coloured with 1 by c.

If c is already regular-irregular, then we are done. Otherwise, because of the properties of c, the only conflicts involve a and some of its neighbours (Properties 1 and 2), and colour 1 of c (Property 3). More precisely, the number of edges incident to a and coloured with 1 by c is equal to the number of edges coloured with 1 incident to some of its neighbours. Now consider all maximal (in terms of edges) connected subgraphs of G induced by colour 1 of c, and let [G.sub.1] be the (only) one including a. Because of the properties of c, note that [G.sub.1] is actually a connected almost locally irregular bipartite graph. According to Lemma 14, there exists a regular-irregular {1,3,4}-edge-colouring of [G.sub.1]. This regular-irregular edge-colouring of [G.sub.1] and the restriction of c to G - E([G.sub.1]) (which induces two locally irregular subgraphs) form a regular-irregular 4-edge-colouring of G. []

We are now ready to prove Theorem 12.

Proof of Theorem 12: We can suppose G is connected (otherwise, independently apply the upcoming arguments on all components of G). In case G is Eulerian, then we directly get that [[chi]'.sub.reg-irr](G) [less than or equal to] 4 by Lemma 13 or 15, hence that [[chi]'.sub.reg-irr](G) < 6. Now, if G is not Eulerian, then we decompose G into one Eulerian bipartite graph G[X], where X [subset] E(G), and one forest G - X. Independently decomposing these edge-disjoint subgraphs into at most 4 (Lemmas 13 and 15) and 2 (Lemma 10) regular-irregular subgraphs, we obtain a decomposition of G into at most 6 regular-irregular subgraphs, implying the claim.

Set X = [??]. As long as G - X is not a forest, we repeat the following procedure. Since G - X is not a forest, it has an induced cycle C. Then add all edges of C to X. At the end of the procedure, it should be clear that every vertex of G has even degree in G[X], so G[X] is Eulerian (and is bipartite since G is bipartite itself). Besides, the subgraph G - X is clearly a forest because of the halting condition. This concludes the proof. []

5 From bipartite graphs to all graphs

5.1 An upper bound on [[chi]'.sub.reg-irr](G) involving [chi](G)

We first note that every graph G can be decomposed into at most [log [chi](G)] + 1 bipartite graphs.

Lemma 16. Every graph G can be decomposed into at most [log [chi](G)] + 1 bipartite graphs.

Proof: Set k = [chi](G) and let [V.sub.0], [V.sub.2],..., [V.sub.k - 1] be a proper vertex-colouring of G. We produce a ([log k] + 1) -edge-colouring c of G whose each colour induces a bipartite graph. Consider every two distinct integers i,j [member of] {0,1,..., k-1}. Clearly, because i [not equal to] j, some bits of the binary representations of i and j have tobe different. Let x [member of] {1, 2,..., [log k] +1} be the right-most position in which the two binary representations differ. Then just colour with colour x all edges of G whose one end is in [V.sub.i] and other end is in [V.sub.j].

It should be clear that every edge of G is assigned a colour by c, and c uses at most [log k] + 1 colours. Now assume one colour of c, say x, induces a subgraph with an induced cycle [v.sub.1][v.sub.2]... [v.sub.2l+1][v.sub.1] of odd length. Then, because [v.sub.1] and [v.sub.2] are adjacent, we have [v.sub.1] [member of] [V.sub.i] and [v.sub.2] [member of] [V.sub.j] with i [not equal to] j, and the xth bit of the binary representation of i is, say, 0 while the xth bit of the binary representation of j is 1. Similarly, we know that [v.sub.3] belongs to some [V.sub.j'], where j [not equal to] j' and possibly i = j', and the xth bit of the binary representation of j, which is 1, is different from the xth bit of the binary representation of j', which is hence 0. Repeating the same argument, because of the length of [v.sub.1][v.sub.2]... [v.sub.2e+1][v.sub.1], we get that [v.sub.2l+1][v.sub.1] is coloured with x while the colour classes of the proper vertex-colouring containing [v.sub.1] and [v.sub.2l+1], which are different, have their binary representation having both xth bit 1, a contradiction. []

We are now ready to state the main result of this section.

Theorem 17. For every graph G, we have [[chi]'.sub.reg-irr](G) [less than or equal to] 6([log [chi](G)] + 1).

Proof: Start by decomposing G into [log[chi](G)] + 1 bipartite subgraphs, and then independently (i.e. using distinct colours) decompose each of these [log [chi](G)] +1 subgraphs into at most 6 regular-irregular subgraphs. Such decompositions exist according to Lemma 16 and Theorem 12. []

Brooks' Theorem, which states that [chi](G) [less than or equal to] [DELTA](G) + 1 for every graph G, and Theorem 17 directly imply that we have

[[chi]'.sub.reg-irr](G) [less than or equal to] 6[log([DELTA](G) + 1)] + 1

for every graph G. Actually, by Brooks' Theorem we even know that [chi](G) = [DELTA](G) + 1 if and only if G is a complete graph or a cycle with odd length. Since these graphs are regular, and hence have regular-irregular chromatic index 1, we can even improve Observation 7 to the following.

Corollary 18. For every graph G, we have [[chi].sub.reg-irr](G) [less than or equal to] 6( [log [DELTA](G)] +1).

[FIGURE 1 OMITTED]

5.2 On using decompositions into AB-graphs

In [2] is noted that locally irregular edge-colouring is connected to the notion of detectable edge-colouring, where an edge-colouring c of a graph G is detectable whenever every two adjacent vertices of G receive distinct multisets of incident colours by c. More precisely, it was pointed out that detectable edge-colouring and locally irregular edge-colouring are equivalent in some contexts. Led investigations on detectable edge-colouring are quite the same as those on locally irregular edge-colouring. Notably, most of the results related to detectable edge-colouring are about the existence of a positive constant k such that every connected graph G different from K2 has detectable chromatic index [[chi]'.sub.det](G) at most k, where

[[chi]'.sub.det](G) = min{k : G admits a detectable k-edge-colouring}.

Towards this question, the best known upper bound on [[chi]'.sub.det] (G) is 4, which was proved by Addario-Berry et al. in [1], while the sharpest upper bound is believed to be 3. So that we sketch the proof that 4 is an upper bound on [[chi]'.sub.det] (G), for the sake of clarity we first need to introduce the following definition.

By an AB-graph we refer to a graph G whose vertex set V(G) admits a bipartition A(G) [union] B(G) (or simply A [union] B when no ambiguity is possible) such that:

* for every edge uv of G, we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

* for every vertex u [member of] A, we have |[N.sub.B] (u) | [greater than or equal to] 1,

* for every vertex u [member of] A, we have |[N.sub.A](u)| [less than or equal to] |[N.sub.B] (u)|.

So an AB-graph G has basically no edges joining vertices in B, while every of its vertices in A has more neighbours in B than it has in A (see Figure 1).

The mentioned above proof that [[chi]'.sub.det](G) [less than or equal to] 4 holds, roughly reads as follows. First, the authors prove, using some arguments, that this inequality is true whenever [chi](G) [less than or equal to] 3. Next, in the case where [chi](G) > 3, a detectable 4-edge-colouring of G is obtained by first decomposing G into three particular AB-subgraphs having their parts A and B overlapping in some fashion. The edges of these AB-subgraphs are then coloured independently, using mainly the property that every AB-graph H has a subgraph H' including all edges joining vertices in A(H) and satisfying [d.sub.H'](u) = [d.sub.H'](v) for every two adjacent vertices u, v [member of] A(H). Said differently, every AB-graph H has an AB-subgraph H' including all edges in A(H), and whose A part is, in a sense, locally irregular (but vertices in B may have neighbours in A with the same degree).

One could naturally wonder whether the proof scheme above can be adapted to prove upper bounds on the irregular chromatic index, or on the regular-irregular chromatic index. As a main result, we prove below that one the most natural adaptations one can imagine, cannot be applied. Our proof of this statement relies on the NP-completeness of a particular subgraph problem, which we believe is of independent interest.

Regarding the explanations above, we say that a subgraph H' of an AB-graph H is A-covering if A(H') = A(H) and H'[A(H')] = H[A(H)]. In other words, H' is A-covering H if H' includes all edges of H whose two ends are in part A (refer to Figure 1 for a concrete example). One direction towards Conjecture 9 could be to adapt the strategy above by Addario-Berry et al. for regular-irregular edge-colouring. Since the regular-irregular chromatic index of every graph G with [chi](G) [less than or equal to] 3 is bounded above by some constant, recall Theorem 17, the beginning of such a proof would be unchanged. So then, considering a graph G with [chi](G) > 3, as above we can assume that [E.sub.1] [union] [E.sub.2] [union] [E.sub.3] is a partition of E(G) where each G[[E.sub.i]] is an AB-graph. It would then remain to show that an AB-graph has bounded regular-irregular chromatic index.

A natural idea to get a constant upper bound on the regular-irregular chromatic index, would hence be to show that an AB-graph H has bounded regular-irregular chromatic index. One strategy for that, could be to first deduce a locally irregular A-covering AB-subgraph H' of H. Note then that E(H) \ E(H') would induce a bipartite graph. We would hence end up with a decomposition of H into two graphs with bounded regular-irregular chromatic index, concluding the proof.

The previous idea is actually not applicable as one can construct counterexamples showing that an AB-graph, though its strong structure, does not always admit a locally irregular A-covering AB-subgraph. Instead of simply exhibiting counterexamples showing this statement, we below prove this differently, namely by showing that the following problem is NP-complete.

LOCALLY IRREGULAR A-COVERING AB-SUBGRAPH

Input: an AB-graph G.

Question: does G admit a locally irregular A-covering AB-subgraph?

Our proof of this statement is by reduction from the following well-known NP-complete problem.

1-IN-3 SATISFIABILITY

Input: a 3CNF formula F over clauses [C.sub.1], [C.sub.2],..., [C.sub.m] and variables [x.sub.1], [x.sub.2],... , [x.sub.n].

Question: is F "1-in-3 satisfiable", i.e. is there a truth assignment to the variables of F for which every clause of F has only one true literal?

Before describing the reduction, we first need to introduce a few definitions and gadgets, and to point out some remarks. When considering the disjoint union of two AB-graphs [H.sub.1] and [H.sub.2] (resulting in a graph G), it should be understood that the union is always performed in such a way that A(G) = A([H.sub.1])[union]A([H.sub.2]) and B(G) = B([H.sub.1]) [union] B([H.sub.2]). Under this convention, note that the union of two AB-graphs is also an AB-graph. Now, by a forced edge of the AB-graph G, we refer to an edge which necessarily belongs to every locally irregular A-covering AB-subgraph of G. By definition, in particular E(G[A(G)]) is a subset of forced edges (by the required A-covering property). On the contrary, an edge of G which cannot belong to any locally irregular A-covering AB-subgraph of G is called bad.

[FIGURE 2 OMITTED]

The first gadget we introduce allows us to add bad edges in an AB-graph. This gadget, denoted D, which is depicted in Figure 2, is the AB-graph with the following structure:

* V(D) = {u, v, w, r}, with A(D) = {u, v, r} and B(D) = {w},

* E(D) = {uv,uw,vw,rw}.

We refer to r and rw as the root and root edge of D, respectively. We prove below that rw, i.e. the root edge of D, is a bad edge.

Lemma 19. The root edge of D is bad.

Proof: By definition, the edge uv belongs to every locally irregular A-covering AB-subgraph H of D. Because H is locally irregular, necessarily exactly one of uw and vw belongs to H so that [d.sub.H](u) [less than or equal to] [d.sub.H](v). So we have {[d.sub.H](u), [d.sub.H](v)} = {1, 2} and w is adjacent to one vertex with degree 2 in H (see Figure 2). Then rw [??] E(H) since otherwise we would have [d.sub.H](w) = 2, a contradiction. []

As a consequence of Lemma 19, note that the root edge of every D gadget in any AB-graph G remains bad, that is, no matter whether other edges are incident to the root vertex r in G.

The second family of gadgets we introduce is the family of B-forbidding gadgets. Formally a (k, B)-forbidding gadget, for some k [greater than or equal to] 3, is an AB-graph F with a root vertex r [member of] A(F) and a root edge rw with w B(F) such that rw is forced and w has degree k in every locally irregular A-covering AB-subgraph of [member of] .

We now give explicit examples of B-forbidding gadgets. Assume k [greater than or equal to] 3 is fixed, and let [F.sub.k,B] be the (k, B)-forbidding gadget defined as follows. Let first w be a vertex in B([F.sub.k,B]), and consider the following construction.

[FIGURE 3 OMITTED]

Bi-star construction: Add two adjacent vertices x andy to A([F.sub.k,B]). Then add edges joining x and k -3 new vertices with degree 1, which are added to A([F.sub.k,B]). Repeat the same procedure but with y instead of x. So far A([F.sub.k,B]) induces a tree whose two vertices x and y have degree k - 2, while all other vertices have degree 1. Now identify each vertex u of A([F.sub.k,B]) with the roots of sufficiently many D gadgets so that u has as many neighbours in B([F.sub.k,B]) than in A([F.sub.k,B]). Finally, add the edges xw and yw.

Repeat the bi-star construction above exactly k - 1 times. Finally, add a vertex r to A([F.sub.k,B]) and join it to w. Note that [F.sub.k,B] is an AB-graph at the end of the construction. We show that [F.sub.k,B] is a (k, B)-forbidding gadget with root r and root edge rw. See Figure 3 for an illustration dedicated to [F.sub.3,B] .

Lemma 20. [F.sub.k,B] is a (k, B)-forbidding gadget for every k [greater than or equal to] 3.

Proof: Let H be a locally irregular A-covering AB-subgraph of [F.sub.k,B] . Recall that all edges of [F.sub.k,B] [A([F.sub.k,B])] belong to H by definition, and that the root edges of the D gadgets attached to some vertices in A([F.sub.k,B]) are bad according to Lemma 19. Because every two vertices x and yjoined to w resulting from any bi-star construction have the same degree in [F.sub.k,B] [A([F.sub.k,B])], which is k - 2, and xy [member of] E(H), necessarily exactly one of xw and yw belongs to H (because these edges between A([F.sub.k,B]) and B([F.sub.k,B]) are the only ones being not bad) so that [d.sub.H](x) [not equal to] [d.sub.H](y). Repeating the same argument for all bi-stars, we get that w has degree at least k - 1 in H and is adjacent to vertices with degree k - 1 in H. So necessarily wr [member of] E(H) since otherwise H would not be locally irregular (see Figure 3 for an illustration for [F.sub.3,B]). Then wr is forced and w always has degree k in H, as claimed. []

We finally introduce the last family of A-forbidding gadgets used in our upcoming reduction. For some k [greater than or equal to] 3, a (k, A)-forbidding gadget is almost the same as a (k, B)-forbidding gadget, except that the vertices with the forced degree are located in the A side, while the root is located on the B side. We can obtain a (k, A)-forbidding gadget [F.sub.k,A] e.g. as follows. Start from a vertex w in A([F.sub.k,A]), and identify w and the roots of k - 1 (k - 1, B)-forbidding gadgets. Finally just add a vertex r in B([F.sub.k,A]) and the edge wr to [F.sub.k,A]. As above, we call r the root of [F.sub.k,A], while wr is the root edge of [F.sub.k,A].

Lemma 21. [F.sub.k,A] is a (k, A)-forbidding gadget for every k [greater than or equal to] 3.

Proof: Assume H is a locally irregular A-covering AB-subgraph of [F.sub.k,A]. According to Lemma 20, the root edges of the k - 1 (k - 1, B) -forbidding gadgets attached to w belong to H. Sow has degree at least k - 1 and is adjacent to vertices with degree k - 1 in H, still according to Lemma 20. Then wr must belong to H, and [d.sub.H](w) = k. []

We are now ready to prove the main result of this section.

Theorem 22. The LOCALLY IRREGULAR A-COVERING AB-SUBGRAPH problem is NP-complete.

Proof: Given an AB-graph G and one of its subgraphs H, we can check in polynomial time whether H is a locally irregular A-covering AB-subgraph of G. So LOCALLY IRREGULAR A-COVERING AB-SUBGRAPH is clearly an NP problem.

We show the NP-hardness of LOCALLY IRREGULAR A-COVERING AB-SUBGRAPH by reduction from 1 -IN-3 SATISFIABILITY. Let us first raise some remarks about the structure of the formula F. First, it is known that the monotone version of 1-IN-3 SATISFIABILITY remains NP-complete [4], so it can be assumed throughout that no clause of F includes a negated variable. We can also raise observations about the form of the clauses in F. For every k [member of] {1,2,3}, we call a clause of F a k-clause if it includes k distinct variables. Clearly, F is not 1-in-3 satisfiable if it includes a 1-clause. Since 1-clauses of F can be detected in polynomial time, we can assume throughout that F has no such clause. Note furthermore that if F includes a 2-clause C = ([x.sub.i] [and] [x.sub.i] [and] xj) with i [not equal to] j, then [x.sub.i] and [x.sub.j] are necessarily set to false and true, respectively, by every truth assignment making F 1-in-3 satisfied. In such a situation, we say that [x.sub.i] and [x.sub.j] are forced to false and true, respectively, by C.

From F, we construct an AB-graph GF such that

F is 1-in-3 satisfiable

GF has a locally irregular A-covering AB-subgraph.

For every variable xi appearing in F, add a vertex [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to B([G.sub.F]). Now consider the clauses of F. On the one hand, for every 2-clause [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (with hence [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] being forced to false and true, respectively, by [C.sub.j]), first identify [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] with the root of one new (3, A)-forbidding gadget. The resulting vertex adjacent to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is denoted [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Next, add a vertex [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to A([G.sub.F]), identify [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] with the roots of two new (3, B)-forbidding gadgets, and add the edge [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to GF. We have the following.

Claim 1. Assume [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a 2-clause of F. Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is bad, while [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is forced.

Proof: Let H be a locally irregular A-covering AB-subgraph of [G.sub.F]. Since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] was identified with the roots of two (3, B)-forbidding gadgets, by Lemma 20 we know that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] has degree at least 2 in H, and is adjacent to vertices with degree 3 in H. Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] cannot belong to H since otherwise we would have [d.sub.H]([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) = 3. Concerning [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], this edge is the root edge of one (3, A)-forbidding gadget, so it is forced according to Lemma 21. []

On the other hand, for every 3-clause [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], add a vertex [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to A([G.sub.F]), the edges [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to [G.sub.F], and identify [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] with the roots of one new (3, B)-forbidding gadget, one new (5, B)-forbidding gadget and one new (6, B)-forbidding gadget. All edges of [G.sub.F] of the form [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] or [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are called clause edges.

Claim 2. Assume [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a 3-clause of F. Then exactly one of the clause edges [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] belongs to a locally irregular A-covering AB-subgraph of [G.sub.F].

Proof: Assume H is a locally irregular A-covering AB-subgraph of [G.sub.F]. Then the root edges of the (3, B)-, (5, B)- and (6, B)-forbidding gadgets attached to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] belong to H according to Lemma 20. So [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] has degree at least 3 and is adjacent to vertices with degree 3, 5 and 6 in H. Because of that fact, note that we cannot have none, two, or three of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] belonging to H. So exactly one of these edges belong to H, as claimed. []

For every variable [x.sub.j] of F, we denote n([x.sub.j]) the number of distinct clauses which contain [x.sub.j]. To end up the construction of [G.sub.F], consider every vertex [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and identify it with the roots of four new (3, A)-forbidding gadgets, one new (n([x.sub.j]) + 4, A)-forbidding gadget, one new (n([x.sub.j]) + 5, A)-forbidding gadget, one new (n([x.sub.j]) + 6, A)-forbidding gadget, and so on up to one (2n([x.sub.j]) + 2, A)-forbidding gadget. Such forbidding gadgets exist since we gave examples of (k, A)-forbidding gadgets for every k [greater than or equal to] 3.

Claim 3. For every variable [x.sub.i] of F, either none or all of the clause edges incident to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] belong to a locally irregular A-covering AB-subgraph of [G.sub.F].

Proof: Assume H is a locally irregular A-covering AB-subgraph of [G.sub.F]. Since the root edges of the four (3, A)- and the (n([x.sub.i]) + 4, A)-, (n([x.sub.i]) + 5, A)-,... , (2n([x.sub.i]) + 2, A)-forbidding gadgets attached to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] belong to H according to Lemma 21, the degree of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in H is at least n([x.sub.i]) + 3 and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is adjacent to vertices with degree n([x.sub.i]) +4, n([x.sub.i]) + 5,..., 2n([x.sub.i]) + 2 in H. Then just note that if the conditions of the claim are not met by H, then H cannot be locally irregular. []

Since all used gadgets are AB-graph, we have that [G.sub.F] is also an AB-graph, as desired. We claim that we have the desired equivalence between F and [G.sub.F]. To see this holds, assume, given a locally irregular A-covering AB-subgraph H of [G.sub.F], that having a clause edge incident to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] belonging to H simulates the fact that [x.sub.i] provides true to the corresponding clause. Then Claims 1 and 2 depict the fact that a clause of F is considered satisfied if and only if it has only one variable evaluated true by a truth assignment of F. Claim 3 depicts the fact that, by a truth assignment, every variable provides the same truth value to every clause which contains it. So from a truth assignment making F 1-in-3 satisfied we can deduce a locally irregular A-covering AB-subgraph of [G.sub.F], and vice-versa. So the equivalence holds. []

6 Concluding remarks

In this paper, we have introduced the notion of regular-irregular edge-colouring of graphs and mainly shown Theorem 17, which provides our best upper bound on the regular-irregular chromatic index of graphs. Although this upper bound should not be optimal, recall Conjecture 9, it is better than every upper bound we know about decompositions into locally irregular subgraphs only (see Corollary 6).

One straight way to improve the multiplicative factor in Theorem 17 would be to improve Theorem 12. Showing Conjecture 9 to be true when restricted to bipartite graphs would notably improve the upper bound of Theorem 17 to 2( [log [chi](G)] + 1), which would be optimal regarding the strategy consisting in decomposing graphs into bipartite subgraphs, and then independently decomposing the resulting bipartite subgraphs.

Speaking of bipartite graphs, we actually almost proved Conjecture 9 when restricted to these graphs as we know that every bipartite graph involving a part of even size has regular-irregular chromatic index at most 2, recall Lemma 13. An important thing to note is that, in the proof of Lemma 15, every regular subgraph induced by a regular-irregular decomposition is actually isomorphic to [K.sub.2]. In other words, we actually proved something stronger than Lemma 15, namely that every bipartite graph admits a decomposition into 4 subgraphs whose components are isomorphic to [K.sub.2] or locally irregular. So one way to improve our results could be to check whether it is easier to decompose bipartite graphs into locally irregular subgraphs and general regular graphs.

Acknowledgements

The authors would like to thank Prof. Mariusz Wozniak from whom came the idea to consider decompositions of graphs into regular and locally irregular components rather than just decompositions into [K.sub.2]'s and locally irregular components. Thanks are also due to the anonymous referees for their very constructive comments. The first author was supported by ERC Advanced Grant GRACOL, project no. 320812.

References

[1] L. Addario-Berry, R.E.L. Aldred, K. Dalal, and B.A. Reed. Vertex colouring edge partitions. Journal of Combinatorial Theory, Series B, 94(2):237-244, 2005.

[2] O. Baudon, J. Bensmail, J. PrzybyLo, and M. Wozniak. On decomposing regular graphs into locally irregular subgraphs. European Journal of Combinatorics, 49:90-104, 2015.

[3] O. Baudon, J. Bensmail, and E. Sopena. On the complexity of determining the irregular chromatic index of a graph. Journal of Discrete Algorithms, 30:113-127, 2015.

[4] T.J. Schaefer. The complexity of satisfiability problems. In Proceedings of the 10th Annual ACM Symposium on Theory of Computing, pages 216-226, 1978.

[5] W. Schnyder. Embedding planar graphs on the grid. In Proceedings of the 1st ACM-SIAM Symposium on Discrete Algorithms, pages 138-148, 1990.

[6] V.G. Vizing. On an estimate of the chromatic class of a p-graph. Diskret. Analiz., 3:25-30, 1964.

Julien Bensmail (1) Brett Stevens (2)

(1) Technical University of Denmark, Denmark

(2) Carleton University, Ottawa, Canada

received 17th Feb. 2015, revised 20th Jan. 2016, accepted 27 Jan. 2016.

(i) We consider that a regular-irregular graph can include both types of components. For example, a graph made up of two locally irregular components, one cubic component and one 5-regular component is regular-irregular.

(ii) A Eulerian graph is a graph whose all vertices have even degree.
COPYRIGHT 2016 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2016 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Bensmail, Julien; Stevens, Brett
Publication:DMTCS Proceedings
Article Type:Report
Date:Jan 1, 2016
Words:9551
Previous Article:The complexity of deciding whether a graph admits an orientation with fixed weak diameter.
Next Article:Arithmetic completely regular codes.
Topics:

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