List edge-colorings of series-parallel graphs

Martin Juvan^{∗} Department of Mathematics, University of Ljubljana 1111 Ljubljana, Slovenia

                    martin.juvan@fmf.uni-lj.si

Bojan Mohar^{∗} Department of Mathematics, University of Ljubljana 1111 Ljubljana, Slovenia

                      bojan.mohar@uni-lj.si

Robin Thomas^{†}

School of Mathematics, Georgia Institute of Technology Atlanta, GA, 30332

                      thomas@math.gatech.edu

Abstract

It is proved that for every integer k ≥ 3, for every (simple) series-parallel graph G with maximum degree at most k, and for every collection (L(e) : e ∈ E(G)) of sets, each of size at least k, there exists a proper edge-coloring of G such that for every edge e ∈ E(G), the color of e belongs to L(e).

Submitted: February 25, 1999; Accepted: September 17, 1999.

Mathematical Subject Classification: 05C15.

1 Introduction

List colorings are a generalization of usual colorings that recently attracted considerable attention, cf. [1, 8, 9, 11]. Originally, list colorings were introduced by Vizing [12] and Erdős, Rubin, and Taylor [6] in the seventies. The definition of a list edge-coloring is as follows. Let G be a multigraph. An edge-list assignment L: E(G) → P(N) is a function that assigns to each edge e of G a set (or a list) L(e) of admissible colors. A function λ: E(G) → N is an L-edge-coloring if λ(e) ∈ L(e) for every e ∈ E(G), and λ(e) ≠ λ(f) for every pair of adjacent edges e, f ∈ E(G). A graph G is kedge-choosable if it has an L-edge-coloring for every edge-list assignment L such that |L(e)| ≥ k for each e ∈ E(G).

∗Supported in part by the Ministry of Science and Technology of Slovenia, Research Project J1-0502-0101-98. Part of the work was done while the author was visiting Georgia Institute of Technology.

†Partially supported by NSF under Grant No. DMS-9623031 and by NSA under Grant No. MDA904-98-1-0517.

Our work is motivated by the following conjecture, which apparently first appeared in [3], but was considered by many other researchers (see [8, Problem 12.20]).

Conjecture 1.1 Every graph G is k-edge-choosable, where k is the chromatic index of G.

Conjecture 1.1 holds for bipartite multigraphs by a result of Galvin [7], for 3regular planar graphs as noticed by Jaeger and Tarsi (unpublished), and for d-regular d-edge-colorable planar multigraphs by a result of Ellingham and Goddyn [5].

Conjecture 1.1 is regarded as very difficult. For instance, even the special case of complete bipartite graphs K_{n,n}, formerly known as Dinitz’ conjecture, was open from 1978 until Galvin’s result mentioned above. In light of that it seems reasonable to study special classes of graphs, in the hope of either finding a counterexample, or gaining more insight. The purpose of this paper is to show that Conjecture 1.1 holds for series-parallel graphs, thus eliminating one natural class of possible counterexamples. The proof can be used to design a linear time algorithm to list-edge color series-parallel graphs.

2 Two lemmas

A graph is series-parallel if it has no subgraph isomorphic to a subdivision of K_{4}. It is well-known [4] that every (simple) series-parallel graph has a vertex of degree at most two.

Lemma 2.1 Every non-null series-parallel graph G has one of the following:

(a) a vertex of degree at most one,

(b) two distinct vertices of degree two with the same neighbors,

(c) two distinct vertices u, v and two not necessarily distinct vertices w, z ∈ V (G)\{u, v} such that the neighbors of v are u and w, and every neighbor of u is equal to v, w, or z, or

(d) five distinct vertices v_{1}, v_{2}, u_{1}, u_{2}, w such that the neighbors of w are u_{1}, u_{2}, v_{1}, v_{2}, and for i = 1, 2 the neighbors of v_{i} are w and u_{i}.

Proof. We proceed by induction on the number of vertices. Let G be a non-null series-parallel graph, and assume that the result holds for all graphs on fewer vertices. We may assume that G does not satisfy (a), (b), or (c). Thus G has no two adjacent vertices of degree two. By suppressing all vertices of degree two (that is, contracting one of the incident edges) we obtain a series-parallel multigraph without vertices of degree two or less. Therefore, this multigraph is not simple. Since G does not satisfy (b), this implies that G has a vertex of degree two that belongs to a cycle of length three. Let G′ be obtained from G by deleting all vertices of degree two that belong to a cycle of length three. First notice that if G′ has a vertex of degree less than two, then the result holds for G (cases (a), (b), or case (c) with w = z). Similarly, if G′ has a vertex of degree two that does not have degree two in G, then the result holds (one of the cases (b)–(d) occurs). Thus we may assume that G′ has minimum degree at least two, and every vertex of degree two in G′ has degree two in G. By induction, (b), (c), or (d) holds for G′, but it is easy to see that then one of (b), (c), or (d) holds for G.

When case (d) of Lemma 2.1 occurs, the graph from Figure 1 has to be colored. The existence of an appropriate coloring is guaranteed by the following lemma.

Figure 1: A special graph with the numbers of remaining colors.

Lemma 2.2 Let G be the graph from Figure 1 and let L be an edge-list assignment for G such that |L(e)| ≥ 2 if e is incident with u_{1} or u_{2}, and |L(e)| ≥ 4 otherwise. Then G admits an L-edge-coloring.

Proof. Suppose first that there is a color c ∈ L(v_{1}u_{1}) ∩ L(u_{2}w). Color v_{1}u_{1}, u_{2}w by c and u_{1}w, v_{2}u_{2} arbitrarily. Since v_{1}w retains at least two admissible colors, the coloring can be extended to G. So, assume that L(v_{1}u_{1}) ∩ L(u_{2}w) = ∅. Suppose now that there is a color c ∈ L(u_{1}w) such that |L(v_{1}u_{1})\{c}| ≥ 2. Color u_{1}w by c and u_{2}w, v_{2}u_{2} arbitrarily. Since v_{1}u_{1} still has at least 2 admissible colors, we can choose the color for v_{1}u_{1} such that v_{1}w and v_{2}w are left with distinct admissible colors. By symmetry, the remaining case is L(v_{1}u_{1}) = L(u_{1}w), L(u_{2}w) = L(v_{2}u_{2}), and hence L(u_{1}w) ∩ L(u_{2}w) = ∅. In this case it is easy to check that at least three of the four L-colorings of v_{1}u_{1}, u_{1}w, u_{2}w, v_{2}u_{2} can be extended to G.

3 List edge-colorings of series-parallel graphs

The following theorem is the main result of the paper.

Theorem 3.1 Let k ≥ 3 be an integer, and let G be a series-parallel graph with maximum degree at most k. Then G is k-edge-choosable.

Proof. We proceed by induction on |V (G)| + |E(G)|. The theorem clearly holds for the null graph, and so let G be a series-parallel graph with at least one vertex, and let L be an edge-list assignment with |L(e)| ≥ k for every edge e ∈ E(G). By Lemma 2.1 one of (a)–(d) of that lemma holds. If (a) holds, then the theorem follows by induction applied to the graph G − v, where v is a vertex of G of degree at most one. Assume next that (b) holds, and let u_{1}, u_{3} be two vertices of degree two in G with the same neighbors, say u_{2} and u_{4}. Then {u_{1}, u_{2}, u_{3}, u_{4}} is the vertex-set of a 4-cycle C in G. Let G′ be obtained from G by deleting the edges of C. Then G′ has an L-edge-coloring by the induction hypothesis, and this L-edge-coloring can be extended to an L-edge-coloring of G, because every edge of C is incident with at most k − 2 edges of G′.

If (d) of Lemma 2.1 holds, then let G′ be the graph obtained from G by deleting the vertices v_{1}, v_{2}, and w. Then G′ has an L-edge-coloring by the induction hypothesis, and this L-edge-coloring extends to an L-edge-coloring of G by Lemma 2.2.

Thus we may assume that (c) of Lemma 2.1 holds, and let u, v, w, z be as in that condition. If G has an edge e with both ends of degree two, then the theorem holds by the induction hypothesis applied to the graph G − e, because e is incident with at most two edges of G − e. Thus we may assume that w has degree at least three, and that u has degree exactly three. Hence the neighbors of u are v, w, and z, where z ≠ w.

If L(vw)∩L(uv) has at most one element, or if k > 3, then every L-edge-coloring of G−v extends to an L-edge-coloring of G, as is easily seen. Thus we may assume that L(vw) ∩ L(uv) has at least two elements, and that k = 3. Let z′ be the neighbor of w other than v and u. Let S, α, and β be such that |S| = 2, α, β ∉ S, S ∪{α} ⊆ L(vw), S ∪ {β} ⊆ L(vu), and let G′′ be the graph obtained from G − v by contracting the edge uw. If α = β, or α ∉ L(wz′), or β ∉ L(uz), then every L-edge-coloring of G′′ extends to an L-edge-coloring of G. Since G′′ has at least one L-edge-coloring by the induction hypothesis, we deduce that the theorem holds.

We may therefore assume that α ≠ β, α ∈ L(wz′), and β ∈ L(uz). We claim that G−v−uw has an L-edge-coloring λ such that either λ(wz′) ≠ α, or λ(uz) ≠ β. If z = z′, then this follows from the induction hypothesis applied to G−v −u−w, and so we may assume that z ≠ z′. Let γ be a new color that does not appear in any of the lists, and let L′ be the edge-list assignment of G′′ defined by L′(wz′) = (L(wz′)\{α})∪{γ}, L′(uz) = (L(uz)\{β}) ∪ {γ}, and L′(e) = L(e) for all other edges e ∈ E(G′′). The graph G′′ has an L′-edge-coloring by the induction hypothesis. If the color of the edge wz′ is γ, we change it to a color from L(wz′) that is distinct from the colors of the (at most two) edges of G − v − uw incident with wz′, and we proceed similarly if the color of the edge uz is γ. This way we obtain the desired L-edge-coloring λ of G − v − uw. Such an L-edge-coloring extends to an L-edge-coloring of G, as desired.

It has been suggested that Conjecture 1.1 might hold for multigraphs as well. However, our proof works only for simple graphs; the corresponding problem for multigraphs seems to be much harder. For a multigraph G let

Γ(G) = max\{\frac{2|E(G[U])|}{|U| − 1} | U ⊆ V (G), |U| ≥ 3 and |U| odd\} .

Seymour [10] proved that if G is a series-parallel multigraph, and k is an integer with Δ(G) ≤ k and Γ(G) ≤ k, then G is k-edge-colorable. If conjecture 1.1 holds for multigraphs, then G is in fact k-edge-choosable, but we were unable to prove that.

The methods of this paper can be used to prove a slightly stronger result: Let G be a series-parallel multigraph such that each vertex v has at most one neighbor which is joined to v by more than one edge. If k ≥ max{Δ(G), 3}, and L is an edge-list assignment for G such that |L(e)| ≥ k for every edge e ∈ E(G) and |L(e)| ≥ k + 1 for every edge e ∈ E(G) that is parallel to another edge of G, then G has an L-edge-coloring.

The proof of Theorem 3.1 can be converted to a linear-time algorithm, as follows. Let G be a graph. We say that a vertex v_{1} ∈ V (G) is special if one of the following conditions holds:

(a) the degree of v_{1} is at most one,

(b) the vertex v_{1} has degree two, and it has the same neighbors as some other vertex of degree two,

(c) there exist vertices u ∈ V (G)\{v_{1}} and w, z ∈ V (G)\{u, v_{1}} such that the neighbors of v_{1} are u and w, and every neighbor of u is equal to v_{1}, w, or z, or

(d) there exist four distinct vertices v_{2}, u_{1}, u_{2}, w ∈ V (G)\{v_{1}} such that the neighbors of w are u_{1}, u_{2}, v_{1}, v_{2}, and for i = 1, 2 the neighbors of v_{i} are w and u_{i}.

Thus Lemma 2.1 implies that every series-parallel graph has a special vertex.

Now let G be a series-parallel graph on n vertices with maximum degree Δ. Given a vertex v ∈ V (G), we can test in time O(Δ) whether v is special. In particular, all special vertices can be found in time O(Δn). The proof of Theorem 3.1 can be converted into a recursive procedure. By maintaining a stack of all special vertices, we can find a set of vertices as in Lemma 2.1 in constant time at each step. Using those vertices, we adjust the graph accordingly (following the cases in the proof of Theorem 3.1), update the stack, and apply the algorithm recursively to the smaller graph. This can be done in time O(Δ). The resulting coloring can be converted into a coloring of the original graph in time O(Δ). Overall, this gives:

Proposition 3.2 There is an algorithm that given a series-parallel graph G on n vertices with maximum degree Δ and an edge-list assignment L such that |L(e)| ≥ Δ for all e ∈ E(G) finds an L-edge-coloring of G in time O(Δn).

Let us remark that the total size of the lists is at least Δn, and so our algorithm is indeed linear in the size of the input. A linear time algorithm for ordinary edgecolorings of series-parallel multigraphs is described in [13].

References

[1] N. Alon, Restricted colorings of graphs, in “Surveys in combinatorics,” Cambridge Univ. Press, Cambridge, 1993, pp. 1–33.

[2] N. Alon, M. Tarsi, Colorings and orientations of graphs, Combinatorica 12 (1992) 125–134.

[3] B. Bollobás, A. J. Harris, List colorings of graphs, Graphs and Combinatorics 1 (1985), 115–127.

[4] J. Duffin, Topology of series-parallel networks, J. Math. Anal. Appl. 10 (1965) 303–318.

[5] M. N. Ellingham, L. Goddyn, List edge colourings of some 1-factorable multigraphs, Combinatorica 16 (1996) 343–352.

[6] P. Erdős, A. L. Rubin, H. Taylor, Choosability in graphs, Congr. Numer. 26 (1980) 125–157.

[7] F. Galvin, The list chromatic index of a bipartite multigraph, J. Combin. Theory Ser. B 63 (1995) 153–158.

[8] T. R. Jensen, B. Toft, Graph Coloring Problems, Wiley, New York, 1995.

[9] J. Kratochvil, Z. Tuza, M. Voigt, New trends in the theory of graph colorings: Choosability and list coloring, preprint, 1998.

[10] P. D. Seymour, Colouring series-parallel graphs, Combinatorica 10 (1990) 379– 392.

[11] Z. Tuza, Graph colorings with local constraints – a survey, Discuss. Math. Graph Theory 17 (1997) 161–228.

[12] V. G. Vizing, Coloring the vertices of a graph in prescribed colors (in Russian), Diskret. Anal. 29 (1976) 3–10.

[13] X. Zhou, H. Suzuki, T. Nishizeki, A linear algorithm for edge-coloring seriesparallel multigraphs, J. Algorithms 20 (1996) 174–201.