Skip to main content

Complexity of greedy edge-colouring

Abstract

The Grundy index of a graph G =(V, E) is the greatest number of colours that the greedy edge-colouring algorithm can use on G. We prove that the problem of determining the Grundy index of a graph G=(V, E) is NP-hard for general graphs. We also show that this problem is polynomial-time solvable for caterpillars. More specifically, we prove that the Grundy index of a caterpillar is Δ(G) or Δ(G)+1 and present a polynomial-time algorithm to determine it exactly.

Background

All the graphs considered in this paper are without loops but may have multiple edges.

A (proper) k-colouring of a graph G =(V, E) is a surjective mapping c:V→{1,2,…,k} such that c(u)≠c(v) for any edge u vE. The chromatic number is χ(G)=min{ kG admits a k-colouring}. On the algorithmic point of view, finding the chromatic number of a graph is a hard problem. For all k≥3, it is NP-complete to decide whether a graph admits a k-colouring (see [2]). Furthermore, it is NP-hard to approximate the chromatic number within \(|V(G)|^{\varepsilon _{0}}\phantom {\dot {i}\!}\) for some positive constant ε 0, as shown by Lund and Yannakakis [5].

Hence, lots of heuristics have been developed to colour a graph. The most basic and widespread because it works online is the greedy algorithm. Given a vertex ordering σ=v 1<<v n of V(G), this algorithm colours the vertices in the order v 1,…,v n , assigning to v i the smallest positive integer not used on its lower-indexed neighbours. A colouring resulting of the greedy algorithm is called a greedy colouring. The Grundy number Γ(G) is the largest k such that G has a greedy k-colouring. Easily, χ(G)≤Γ(G)≤Δ(G)+1.

Zaker [6] showed that for any fixed k, one can decide in polynomial time whether a given graph has Grundy number at most k. However, determining the Grundy number of a graph is NP-hard [6], and given a graph G, it is even NP-complete to decide whether Γ(G)=Δ(G)+1 as shown by Havet and Sampaio [3]. In addition, Asté et al. [1] showed that for any constant c≥1, it is NP-complete to decide whether Γ(G)≤c·χ(G).

Graph colouring of many graph classes has also been studied. One of the classes is the one of line graphs. The line graph of a graph G, denoted L(G), is the graph whose vertices are the edges of G, with e fE(L(G)) whenever e and f share an end-vertex. Colouring line graphs corresponds to edge-colouring. A k-edge-colouring of a graph G is a surjective mapping ϕ:E(G)→{1,…,k} such that if two edges e and f are adjacent (i.e. share an end-vertex), then ϕ(e)≠ϕ(f). A k-edge-colouring may also be seen as a partition of the edge set of G into k disjoint matchings M i ={eϕ(e)=i}, 1≤ik. By edge-colouring, we mean either the mapping ϕ or the partition.

The chromatic index χ (G) of a graph G is the least k such that G admits a k-edge-colouring. It is easy to see that χ (G)=χ(L(G)). Obviously, Δ(G)≤χ (G) and Shannon’s and Vizing’s theorems state that \(\chi '(G)\leq \max \{\frac {3}{2}\Delta (G) ; \Delta (G)+\mu (G)\}\), where μ(G) is the maximum number of edges between two vertices of G. Holyer [4] showed that for any k≥3, it is NP-complete to decide if a k-regular graph has chromatic index k.

Edge colouring naturally arises in modelling some channel assignment problems in wireless network. From such a network, one can construct the communication graph whose vertices are the nodes of the network, and two vertices are connected by an edge whenever they communicate. In order to avoid interferences between the different signals arriving at a node, we need to assign distinct frequencies to the communications at each node. This corresponds to finding an edge-colouring of the communication graph.

Usually, the communications begin at different dates, and we need to assign the frequencies online. Usually, the frequencies are assigned greedily according to the following the greedy algorithm for edge-colouring, which corresponds to the greedy algorithm to colour a line graph. Given a graph G =(V, E) and an edge ordering θ=e 1<<e n , assign to e i the least positive integer that was not already assigned to lower-indexed edges adjacent to it. An edge-colouring obtained by this process is called a greedy edge-colouring, and it has the following property:For every j < i, every edge e in M i is adjacent to an edge in M j . (P)Note that an edge-colouring satisfying (P) is a greedy edge-colouring relative to any edge ordering in which the edges of M i precede those of M j when i<j.

The Grundy index Γ (G) of a graph G is the largest number of colours of a greedy edge-colouring of G. Notice that Γ (G)=Γ(L(G)). By definition, χ (G)≤Γ (G). Furthermore, as an edge is adjacent to at most 2Δ(G)−2 other edges (Δ(G)−1 at each end-vertex), colouring the edges greedily uses at most 2Δ(G)−1 colours. So Δ(G)≤Γ (G)≤2Δ(G)−1. There are graphs for which the Grundy index equals the maximum degree, stars for example. On the opposite, for any Δ, there is a tree with maximum degree Δ and Grundy index 2Δ−1. Indeed, consider the trees \(B^{\prime }_{k}\) defined recursively as follows: \(B^{\prime }_{1} = P_{2}\), \(B^{\prime }_{2} = P_{3}\) and the root of P 2 is one of its vertex and the root of P 3 is one of its leaves; \(B^{\prime }_{k}\) is obtained from the disjoint union of \(B^{\prime }_{k-1}\) and \(B^{\prime }_{k-2}\) by adding an edge between their roots, and the root of \(B^{\prime }_{k}\) is the root of \(B^{\prime }_{k-2}\). An easy induction shows that for every positive k, Δ(B2k′)=Δ(B2k+1′)=k+1 and that the root of \(B^{\prime }_{2k}\) has degree k and the root of \(B^{\prime }_{2k+1}\) has degree k+1. Now, Γ (B k′)=k for every k, because one can show easily by induction the following stronger statement.

Proposition 1.

For every positive integer k, there is a greedy k-edge-colouring of \(B^{\prime }_{k}\) such that the colours assigned to the edges incident to the root are all the odd numbers up to k, if k is odd, and all the even numbers up to k if k is even.

In this paper, we study the complexity of finding the Grundy index of a graph. We prove that it is NP-hard by showing that the following problem is co-NP-complete. MINIMUM GREEDY EDGE-COLOURING Instance: A graph G. Question: Γ (G)=Δ(G)?

The proof, to be detailed in the Section ‘Co-NP-completeness results’, is a reduction from 3-EDGE-COLOURABILITY OF CUBIC GRAPHS which was proved to be NP-complete by Holyer [4]. We recall that a cubic graph is a 3-regular graph. The reduction also proves that it is co-NP-complete to decide if Γ (G)=χ (G). 3-EDGE-COLOURABILITY OF CUBIC GRAPHS Instance: A cubic graph G. Question: Is G 3-edge colourable?

We then extend the result to a more general problem. f -GREEDY EDGE-COLOURING Instance: A graph G. Question: Γ (G)≤f(Δ(G))?

We show that for any function f such that kf(k)≤2k−2, the problem f -GREEDY EDGE-COLOURING is co-NP-Complete.

Since determining the Grundy index is NP-hard, a natural question to ask is for which class of graphs it can be done in polynomial time. Obviously, it is the case for the class of graphs with maximum degree k. Indeed, the Grundy index of a graph G in this class is at most 2k−1, and for every 1≤i≤2k−1, one can check in polynomial time whether Γ (G)≤j. So we must look at classes for which the maximum degree is not bounded. In the Section ‘Greedy edge-colouring of caterpillars’, we consider caterpillars which are trees such that the deletion of all leaves results in a path, called backbone. We show that if T is a caterpillar then Γ (T)≤Δ(T)+1 and then give a linear-time algorithm to compute the Grundy index of a caterpillar. In view of this result, a natural question is the following:

Problem 2.

Can we compute in polynomial time the Grundy index of a given tree?

Co-NP-completeness results

The aim of this section is to prove that f -GREEDY EDGE-COLOURING is co-NP-complete for every function f such that kf(k)≤2k−2 for all k.

For the sake of clarity, we first show that MINIMUM GREEDY EDGE-COLOURING is co-NP-complete.

MINIMUM GREEDY EDGE-COLOURING is clearly in co-NP, because a greedy edge-colouring of a graph G with at least Δ(G)+1 colours is a certificate that Γ (G)>Δ(G). We show that it is co-NP-complete.

Theorem 3.

MINIMUM GREEDY EDGE-COLOURING is co-NP-Complete.

We now prove the co-NP-completeness by reduction from 3-EDGE-COLOURABILITY OF CUBIC GRAPHS.

Let H be a cubic graph on n vertices w 1,…w n . Let G be the graph defined by V(G)=V(H){u 1,…,u n }{v, a, bm, c} and E(G)=E(H){u i w i 1≤in}{v u i 1≤in}{av, bv, cv}. See Fig. 1.

Fig. 1
figure 1

Graph G obtained from a cubic graph H

In G, d(v)=n+3, while the degree of all other vertices is at most 4. Thus, Δ(G)=d(v)=n+3 because n≥4 has H is cubic. Moreover, every edge of G is adjacent to at most n+3 edges so Γ (G)≤n+4=Δ(G)+1. Hence, the Grundy index of G is either Δ(G) or Δ(G)+1. The co-NP-completeness of MINIMUM GREEDY EDGE-COLOURING follows directly from the following claim.

Claim 3.1.

χ (H)=3 if and only if Γ (G)=Δ(G)+1.

Proof.

() Suppose that there exists a 3-edge-colouring ϕ of H. Let us extend ϕ into a greedy edge-colouring of G with Δ(G)+1=n+4 colours. Set ϕ(a v)=1, ϕ(b v)=2, ϕ(c v)=3, and for all 1≤in, ϕ(u i w i )=4 and ϕ(u i v)=i+4. Notice that every vertex w i is incident to an edge of H of each colour in {1,2,3} since H is cubic. Then, it is straightforward to check that ϕ is a greedy (n+4)-edge-colouring of G.

() Suppose that there is a greedy (n+4)-edge-colouring of G. Some edge is coloured n+4. But such an edge has to be adjacent to at least n+3 edges and thus to be one of the v u i , say v u n . The edge v u n is adjacent to exactly n+3 edges. So by Property (P), all edges adjacent to v u n receive distinct colours in {1,…,n+3}.

Let us first prove by induction on 1≤jn that the edge e j adjacent to v u n labelled n+5−j is one of the v u i , the result holding for j=1. Suppose now that j≥2. The edge e j must have degree at least n+5−j since it is adjacent to v u n and one edge of each colour in {1,…,n+4−j} by Property (P). Hence, e j must be incident to v since u n w n is adjacent to four edges. Then e j must have degree at least n+3 since it is adjacent to the j−1 edges e l for 1≤l<j and one edge of each colour in {1,…,n+4−j}. Hence, e j is one of the v u i .

Hence, without loss of generality, we may assume that ϕ(v u i )=i+4 for all 1≤in. The edge v u i is adjacent to an edge-coloured 4. This edge must be u i w i since the edges av, bv and cv are adjacent to at most two edges coloured in {1,2,3}. Thus, ϕ(u i w i )=4 for all 1≤in.

Now every edge u i w i is adjacent to three edges, one of each colour in {1,2,3}. Since ϕ(v u i )≥5, these three edges must be the three edges adjacent to w i in H. Thus, all the edges of H are coloured in {1,2,3}. Hence, the restriction of ϕ to H is a 3-edge-colouring.

Remark 4.

Observe that the graph G has chromatic index Δ(G). Indeed, colour the edges adjacent to v with the colours 1,…,Δ(G) and then extend greedily this colouring to the other edges. Since all the remaining edges are adjacent to at most four edges, they will all get a colour less than or equal to 5. Since Δ(G)≥5, we obtain a Δ(G)-edge-colouring. Hence, the above reduction shows that it is co-NP-complete to decide whether Γ (G)=χ (G).

Theorem 3 may be generalized as follows.

Theorem 5.

Let f be a function such that kf(k)≤2k−2 for all \(k\in \mathbb {N}\). f -GREEDY EDGE-COLOURING is co-NP-Complete.

Proof.

f -GREEDY EDGE-COLOURING is clearly in co-NP, because a greedy edge-colouring of a graph G with more than f(Δ(G)) colours is a certificate that Γ (G)>f(Δ(G)).

We now prove the co-NP-completeness by reduction from 3-EDGE-COLOU- RABILITY OF CUBIC GRAPHS.

Let H be a cubic graph on n vertices w 1,…,w n , and let G be the graph defined as in the proof of Theorem 3. Set p=f(n+3)−(n+3). Then 0≤pn+1. For 1≤ip, let T i be the tree with vertex set {a i ,b i ,c i ,t i }{a i, j ,b i, j ,c i, j ,s i, j ,t i, j 1≤jn−1} and edge set \(\{a_{i}t_{i}, b_{i}t_{i}, c_{i}t_{i}\} \cup \bigcup _{j=1}^{n-1} \{a_{i,j}t_{i,j}, b_{i,j}t_{i,j}, c_{i,j} t_{\textit {ij}}, t_{i,j}s_{i,j}, s_{i,j}t_{i}\}\). Let G be a graph obtained from the disjoint union of G and the T i by adding the edge u n t i for all 1≤ip. See Fig. 2.

Fig. 2
figure 2

The graph G obtained from a cubic graph H

Observe that Δ(G )=n+3 and the vertices of degree n+3 are v, t 1,…,t p and u n when p=n+1. Moreover, every edge is adjacent to at most n+3+p, so Γ (G)≤n+3+p+1=f(Δ(G )+1. The co-NP-completeness of f -GREEDY EDGE-COLOURING follows directly from the following claim.

Claim 5.1.

χ (H) = 3 if and only if Γ (G )=f(Δ(G ))+1.

() Suppose that there exists a 3-edge-colouring ϕ of H. Let us extend ϕ into a greedy edge-colouring of G with f(Δ(G ))+1=n+p+4 colours. We first extend it into a greedy (n+4)-colouring of G as we did in the proof of Theorem 3. In particular, we have ϕ(u n w n )=4 and ϕ(u n v)=n+4. For all 1≤ip and all 1≤jn−1, we set ϕ(t i a i )=1, ϕ(t i b i )=2, ϕ(t i c i )=3, ϕ(t i, j a i, j )=1, ϕ(t i, j b i, j )=2, ϕ(t i, j c i, j )=3, ϕ(t i, j s i, j )=j+3, and ϕ(t i u n )=n+4+i. Then it is straightforward to check that ϕ is a greedy (n+p+4)-edge-colouring of G .

() Suppose that G admits a greedy (n+p+4)-edge-colouring ϕ. For all 1≤ip, there is an edge e i coloured n+4+i. This edge must have to be adjacent to at least n+3+i edges by Property (P). So all the e i must be in F={v u n }{u n t i 1≤ip}. Now, the edge e p is adjacent to an edge e 0 coloured n+4. This edge is adjacent to at least n+4 edges: one of each colour in {1,…,n+3} and e p . Hence, e 0 also has to be in F. Since |F|=p+1, all the edges in F are coloured with distinct labels in {n+4,…,n+p+4}.

Now applying the same reasoning as in the proof of Theorem 3, we derive that the restriction to ϕ to H is a 3-edge-colouring.

Greedy edge-colouring of caterpillars

In this section, we show a polynomial-time algorithm solving GREEDY EDGE-COLOURING for caterpillars. A caterpillar is a tree such that the deletion of all leaves results in a path, called backbone. A star is a trivial caterpillar.

We first show that the Grundy index of a caterpillar T is at most Δ(T)+1, and so it is either Δ(T) or Δ(T)+1. Then we give a polynomial-time algorithm that computes the Grundy index of a caterpillar.

Grundy index of a caterpillar

Lemma 6.

Let T be a caterpillar and v a vertex in its backbone such that d(v)≥3. In every greedy edge-colouring of T, the colours 1,…,d(v)−2 appear on the edges incident to v.

Proof.

By the contrapositive. Let c be an edge-colouring of T. Suppose that a colour α{1,…,d(v)−2} is not assigned to any edge incident to v. Then, since all the edges incident to v have different colours, at least three colours strictly greater than d(v)−2 appear on three edges incidents to v. One of these colours, say β, must appear on an edge e incident with a leaf. But e is uniquely adjacent to edges incident to v. So e is adjacent to no edge-coloured α. Since αd(v)−2<β, the edge-colouring c is not greedy.

Lemma 7.

Let c be a greedy edge-colouring of a caterpillar T and v an interior vertex in the backbone of T. If two edges e 1 and e 2 incident to v receive colours greater than d(v)−1, then e 1 and e 2 are two edges of the backbone and the edges incident to v and leaves are coloured 1,…,d(v)−2.

Proof.

Suppose by way of contradiction that one of these two edges, say e 1, is incident to a leaf. Then e 1 is adjacent to d(v)−1 other edges, and one of them, namely e 2, is assigned a colour greater than d(v)−1. Thus, e 1 is adjacent to at most d(v)−2 edges whose colour is less or equal to d(v)−1. So, there is a colour α in {1,…,d(v)−1} such that no edge adjacent to e 1 is coloured α. This contradicts the fact that c is greedy. Hence, e 1 and e 2 are edges of the backbone.

Now by Lemma 6, there must be edges incident to v of each colour in {1,…,d(v)−2}. So the d(v)−2 edges distinct form e 1 and e 2, which are the edges linking v and leaves are coloured must be coloured in {1,…,d(v)−2}.

Now by Lemma 6, there must be edges incident to v of each colour in {1,…,d(v)−2}. So the d(v)−2 edges distinct form e 1 and e 2, which are the edges linking v and leaves are coloured must be coloured in {1,…,d(v)−2}.

Now by Lemma 6, there must be edges incident to v of each colour in {1,…,d(v)−2}. So the d(v)−2 edges distinct form e 1 and e 2, which are the edges linking v and leaves are coloured must be coloured in {1,…,d(v)−2}.

Theorem 8.

If T is a caterpillar, then Γ (T)≤Δ(T)+1.

Proof.

Set Δ(T)=Δ. Suppose by way of contradiction that it is possible to greedily colour T with Δ+2 colours. Let e be an edge-coloured Δ+2. It must be adjacent to at least Δ+1 edges, one of each colour 1,…,Δ+1. Thus, the edge e is in the backbone. According to Lemma 7, the edges e 1 and e 2 adjacent to e with colours Δ and Δ+1 are in the backbone. Furthermore, all the edges adjacent to e which are neither e 1 nor e 2 are coloured in {1,…,Δ−2}. Hence, e is adjacent to no edge-coloured Δ−1, a contradiction.

Theorem 8 is tight since there are caterpillars T whose Grundy index is greater than their maximum degree. For example, consider the caterpillar C k with backbone (t, u, v, w) for which all the vertices t have degree k−1, and v and w degree k. An edge-colouring in which the k−2 edges incident to t and a leaf are coloured with 1,…, k−2, the k−1 edges incident to w and a leaf with 1,…,k−1, the k−2 edges incident to v and a leaf with 1,…,k−2, the edge tu with k−1, the edge vw with k and the edge uv with k+1 is greedy. See Fig. 3 for k=5.

Fig. 3
figure 3

The caterpillar C 5 and a greedy edge-colouring with 6 colours

Finding the Grundy index of a caterpillar

Theorem 8 implies that the Grundy index of a caterpillar T is either Δ(T) or Δ(T)+1. Hence, determining the Grundy index of a caterpillar is equivalent to solve MINIMUM GREEDY EDGE-COLOURING for it. The aim of this subsection is to prove that it can be done in a linear time.

Theorem 9.

Determining the Grundy index of a caterpillar T can be done in O(|V(T)|).

In order to prove this theorem, we first give some definitions and lemmas. Let T be a caterpillar with backbone P=(v 1,v 2,…,v n ), v 1v n . The first edge of P is v 1 v 2. For any edge e=v i v i+1P, removing e from T gives two caterpillars \(T^{-}_{e}\) and \(T^{+}_{e}\), the first one containing v i and the second one containing v i+1. For convenience, the backbone of \(T^{-}_{e}\) is P (e)=(v i ,v i−1,…,v 1) and the backbone of \(T^{+}_{e}\) is \(P^{+}_{e}=(v_{i}, v_{i+1}, \dots, v_{n})\). Hence, the first edge of \(T^{-}_{e}\) is (v i ,v i−1) and the first edge of T +(e) are (v i+1,v i+2). However, if the degree of v i is 2 in T, (v i ,v i−1) is not an edge in the backbone, the case in which we say that the first edge is null. The same happens if the degree of v i+1 is 2 or if \(T^{-}_{e}\) or T +(e) are stars.

Lemma 10.

Let T be a caterpillar of the maximum degree Δ with backbone P=(v 1,…,v n ) with a length at least 2. Then Γ (T)=Δ+1 if and only if there is an edge e=v i v i+1E(P) such that

  • one end-vertex of e has degree Δ, and

  • one of the two caterpillars \(T^{-}_{e}\) and \(T^{+}_{e}\) has a greedy edge-colouring such that the first edge of its backbone is coloured Δ and the other has a greedy edge-colouring such that its first edge of its backbone is coloured Δ−1. If the value of the first edge of \(T^{-}_{e}\) (similarly for \(T^{+}_{e}\)) is null, its first vertex is required to have degree Δ in the early case (edge-coloured Δ) and Δ−1 in the later.

Proof.

Assume that T has a greedy (Δ+1)-edge-colouring. Let e be an edge-coloured Δ+1. By Lemma 7, e is in the backbone and incident to a vertex of degree Δ, proving (1). Moreover, the edge e is adjacent to an edge e 1 coloured Δ and another one e 2 labelled Δ−1. The greedy edge-colourings induced on \(T^{-}_{e}\) and \(T^{+}_{e}\) satisfy (2). Suppose, w.l.o.g, \(T^{-}_{e}\) contains e 1. If the first edge of \(T^{-}_{e}\) is not null, then it is easy to see it is e 1, since by Lemma 7, e 1 must also be in the backbone of T. If the first edge of \(T^{-}_{e}\) is null than d(v i )=2 and the only way e 1=v i v i−1 be coloured Δ is if d(v i−1), the first vertex of \(T^{-}_{e}\), has degree Δ. The analysis for \(T^{+}_{e}\) contains e 2 is analogue, observing that in this case, \(T^{+}_{e}\) can be a star.

Conversely, assume that there is an edge eE(P) satisfying (1) and (2). Let ϕ and ϕ + be the greedy edge-colourings of \(T^{-}_{e}\) and \(T^{+}_{e}\), respectively as in (2). Let ϕ be the edge-colouring of T defined by ϕ(e)=Δ+1, ϕ(f)=ϕ (f) for all \(f\in T^{-}_{e}\) and ϕ(f)=ϕ +(f) for all \(f\in T^{+}_{e}\). We claim that ϕ is a greedy edge-colouring. Clearly, since ϕ and ϕ + are greedy, it suffices to prove that e is adjacent to an edge of every colour i in {1,…,Δ}. Since ϕ + and ϕ satisfy (2), then e is adjacent to an edge-labelled Δ and an edge-labelled Δ−1. Now, e is incident to a vertex v of degree Δ. This vertex is incident to e and an edge f with a colour greater than Δ−2 in the greedy edge-colouring of T f in \(\{T^{+}_{e}, T^{-}_{e}\}\). So, the Δ−2 edges incident to v which are not e nor f have all one colour in 1,…,Δ−2. Hence, e is adjacent to an edge of every colourin {1,…,Δ}.

Lemma 11.

Let T be a caterpillar with backbone P of length at least 2 and first edge e=u v. Then T has a greedy edge-colouring such that e is coloured k if and only if one of the following holds:

  • d(u)≥k or d(v)≥k

  • d(u)=k−1 and \(T^{+}_{e}\) admits a greedy edge-colouring such that the first edge of \(P^{+}_{e}\) is coloured k−1.

Proof.

Let e=u v with u the first vertex of P. Assume first that T has a greedy edge-colouring such that e is coloured k and that e is incident to no vertex of degree k. Then the edges incident to u must be coloured by 1,…,d(u)−1 and the edges incident to u and a leaf are coloured by 1,…d(v)−2. Hence, the edge adjacent to e and coloured k−1 must be the first edge of \(P^{+}_{e}\) is coloured k−1 by Property (P). So the edge adjacent to e and coloured k−2 must be incident to u, and thus d(u)−1≥k−2, that is d(u)≥k−1.

Assume now that (1) holds. Let x be a vertex in {u,v} with degree at least k. One can colour all the edges incident to x with 1,…,d(v) such that e is coloured k and then extend this edge-colouring greedily to obtain the desired greedy edge-colouring of T.

Finally, assume that (2) holds. Let ϕ be a greedy edge-colouring of \(T^{+}_{e}\) such that the first edge of \(P^{+}_{e}\) is coloured k−1. One can extend it by assigning k to e, 1,…,k−2 to the k−2 edges incident to u and leaves and 1,…,d(v)−2 to the edges incident to v. It is routine to check that this a a greedy edge-colouring of T.

Proof of Theorem 9.

Theorem 8 and Lemma 10 imply that Algorithm 1 return the Grundy index of T provided that we have a subroutine FirstEdge(T, P, k) that returns ‘yes’ if a caterpillar T with backbone P admits a greedy edge-colouring such that the first edge of P is coloured k.

Such a subroutine FirstEdge may be obtained by Algorithm 2 according to Lemma 11.

Let us now examine the complexity of Algorithm 1. Let us first observe that FirstEdge(T, P, k) makes a constant number of operations before calling FirstEdge(Tu, Pu, k−1). Hence, an easy induction show that it makes O(k) operations in total.

Algorithm 1 first computes (line 1) the degrees of all the v i , which can be done in time O(|V(T)|) and then takes the maximum of all these values which can also be done in time O(|V(T)|).

In a second phase (line 2 to 8), for each edge eP which is incident to a vertex of degree Δ, Algorithm 1 makes at most four calls of FirstEdge with last parameter Δ−1 or Δ. Hence, for each eP it makes O(Δ) operations, according to the execution time of Algorithm 2. Let S be the set of vertices of degree Δ. The number of edges of P incident to a vertex of degree Δ is at most 2|S|. But every vertex in S is adjacent to at least Δ−2 leaves. Hence, |V(T)|≥|S|+(Δ−2)|S|, so |S|≤|V(T)|/(Δ−1). Hence, in this second phase, the algorithm makes at most \(O\left (2\times \frac {|V(T)|}{\Delta -1} \Delta \right) = O(|V(T)|)\) operations.

Thus, in total, Algorithm 2 makes O(|V(T)|) operations.

References

  1. Asté M, Havet F, Linhares-Sales C (2010) Grundy number and products of graphs. Discret Math 310(9): 1482–1490.

    Article  MATH  Google Scholar 

  2. Garey MR, Johnson DS (1979) Computers and intractability. A guide to the theory of NP-completeness. A Series of Books in the Mathematical Sciences, San Francisco, California.

  3. Havet F, Sampaio L (2010) On the Grundy number of a graph In: Proceedings of the International Symposium on Parameterized and Exact Computation(IPEC), Lecture Notes on Computer science, 6478.. Springer, Berlin Heidelberg.

    Google Scholar 

  4. Holyer I (1981) The NP-completeness of edge-coloring. SIAM J Comput 2: 225–231.

    Article  Google Scholar 

  5. Lund C, Yannakakis M (1994) On the hardness of approximating minimization problems. J. Assoc. Comput. Mach. 41(5): 960–981.

    Article  MathSciNet  MATH  Google Scholar 

  6. Zaker M (2006) Results on the Grundy chromatic number of graphs. Discrete Math 306(23): 3166–3173.

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

This study is partly supported by CAPES/Brazil, Fortaleza, Brazil.

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to A. Karolinna Maia.

Additional information

Competing interests

The authors declare that they have no competing interests.

Authors’ contributions

The authors discussed the problem and the solutions proposed all together, and also the three helped to write in each section. All authors read and approved the final manuscript.

Rights and permissions

Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Havet, F., Maia, A.K. & Yu, ML. Complexity of greedy edge-colouring. J Braz Comput Soc 21, 18 (2015). https://doi.org/10.1186/s13173-015-0036-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1186/s13173-015-0036-x

Keywords