ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 9 (2015) 267-277
Odd edge coloring of graphs
Borut Luzar
Faculty of Information Studies, 8000 Novo mesto, Slovenia
and
Institute of Mathematics, Physics and Mechanics, 1000 Ljubljana, Slovenia
Mirko Petrusevski
Department of Mathematics and Informatics, Faculty of Mechanical Engineering, Skopje, Republic of Macedonia
Received 24 November 2013, accepted 1 October 2014, published online 11 January 2015
An edge coloring of a graph G is said to be an odd edge coloring if for each vertex v of G and each color c, the vertex v uses the color c an odd number of times or does not use it at all. In [5], Pyber proved that 4 colors suffice for an odd edge coloring of any simple graph. Recently, some results on this type of colorings of (multi)graphs were successfully applied in solving a problem of facial parity edge coloring [3, 2]. In this paper we present additional results, namely we prove that 6 colors suffice for an odd edge coloring of any loopless connected (multi)graph, provide examples showing that this upper bound is sharp and characterize the family of loopless connected (multi)graphs for which the bound 6 is achieved. We also pose several open problems.
Keywords: Edge coloring, odd subgraph, Shannon triangle. Math. Subj. Class.: 05C15
E-mail addresses: borut.luzar@gmail.com (Borut Lužar), mirko.petrushevski@gmail.com (Mirko Petruševski), skrekovski@gmail.com (Riste Škrekovski)
Riste Škrekovski
Institute of Mathematics, Physics and Mechanics, 1000 Ljubljana, Slovenia
and
Faculty of Information Studies, 8000 Novo mesto, Slovenia
and
University of Primorska, FAMNIT, 6000 Koper, Slovenia
Abstract
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
268
Ars Math. Contemp. 9 (2015) 165-186
1	Introduction
Throughout the article we mainly follow the terminology and notation used in [1]. A graph is denoted by G = (V(G), E(G)), where V(G) is the vertex set and E(G) is the edge set. A graph G is always regarded as being finite (i.e. having finite number of vertices n(G), and finite number of edges m(G)) with loops and multiple edges allowed. The parameters n(G) and m(G) are usually called order and size of G, respectively. Whenever n(G) = 1 we say that G is trivial and whenever m(G) =0 we say that G is empty. For X C V(G) U E(G), the subgraph obtained by removing the vertices and edges from the set X is denoted by G - X. We refer to the vertices having even (resp. odd) degree as even (resp. odd) vertices. A graph is called even (resp. odd) whenever all of its vertices are even (resp. odd).
An odd edge coloring of G is a (not necessarily proper) edge coloring such that each color class induces an odd subgraph of G. An odd edge coloring of G using at most k colors is referred to as an odd k-edge-coloring, and we say that G is odd k-edge-colorable. If G admits an odd edge coloring, the odd chromatic index xO (G) is defined to be the minimum integer k for which G is odd k-edge-colorable.
By definition, each loop at a vertex v colored with c contributes 2 to the count of appearances of c at v. Thus, it is obvious that a necessary and sufficient condition for the existence of an odd edge coloring of G is the absence of vertices incident only to loops. Apart from this, the presence of loops does not influence the existence nor changes the value of the index x'(G). Therefore, we choose to restrict our attention to loopless connected graphs throughout the article.
As a notion, odd edge coloring was first introduced by Pyber in his survey on graph coverings [5] as an edge decomposition of a graph into (edge disjoint) odd subgraphs. Such decompositions represent a counterpart to decompositions into even subgraphs, which were mainly used while proving various flow problems (see e.g. [6]).
In the mentioned work, Pyber considered simple graphs and proved the following result.
Theorem 1.1 (Pyber, 1991). For every simple graph G, it holds that
X'o(G) < 4 .
He also remarked that the upper bound is realized by a wheel on four spokes W4 and asked whether there is an infinite family of connected graphs for which this bound is achieved. In 2006, Mitrai [4] presented such a construction, taking an even number of copies of W4 and an additional vertex v. Choosing an arbitrary edge from the wheel, he removed the same edge from every copy and connected its two end-vertices with v (see Fig. 1). From xO(W4) = 4 readily follows that the obtained graph has xO equal to 4.
A generalization of Theorem 1.1 was successfully applied in solving a problem of facial parity edge colorings in [2], and its improvement in [3]. In this paper, an analogous result to Theorem 1.1 is proved for loopless graphs. Namely, in Theorem 11 we prove that 6 colors suffice for an odd edge coloring of any loopless connected graph, and characterize the family of loopless connected graphs needing 6 colors.
2	Preliminary results
It is an easy matter to characterize the graphs having xO < 1: namely, xO(G) =0 if and only if G is empty, while xO(G) = 1 if and only if G is nonempty and the subgraph of G
B. Luzar et al.: Odd edge coloring of graphs
269
Figure 1: A graph with odd chromatic index equal to 4.
induced by its non-isolated vertices is odd. The following result was initially stated in [5], but for the sake of completeness we present it here with a proof.
Proposition 2.1. For every forest F, it holds that xO(F) < 2.
Proof. It is enough to prove this for an arbitrary tree T. If T is trivial or odd, then x' (T) < 1, so suppose this is not the case. We construct an odd 2-edge-coloring of T. Take an even vertex r as the root of T. To begin with, color the edges incident to r by using the color 1 for all but one such edge, and color this remaining edge by the color 2.
Continue by coloring the incident edges to each vertex v which has one incident edge already colored as follows:
•	if v has even degree in T, then we complete the coloring of its incident edges by coloring them in the other color (if color 1 was used for the already colored edge, then we use color 2 for the remaining edges, and vice versa);
•	if v has odd degree in T, then we complete the coloring of its incident edges by coloring them with the same color as the already colored edge.
Since there are no cycles in T, every vertex u = r eventually is in a position to have exactly one of its incident edges colored. Namely, consider the vertices along the unique ru-path in T and suppose the opposite, i.e. suppose there exist at least one vertex on this path that never gets in the stated position. Choose the first such vertex after r (denote it by w) on the tracing of this path. Thus, the predecessor of w gets in the stated position. But this implies that w also gets in position, a contradiction.
Therefore, the above procedure produces an odd 2-edge-coloring of T.	□
Let G be a graph and T be an even-sized subset of V(G). Following [1], a spanning subgraph H of G is said to be a T-join if dH (v) is odd for all v G T and even for all v G V(G)\T. For example, if P is an xy-path in G, the spanning subgraph of G with edge set E(P) is an {x, y}-join. Note that by removing (resp. adding) a cycle (as an edge set) from (resp. to) a T-join we again obtain a T-join. Thus, whenever a T-join exists, there also exists such a forest (resp. coforest).
A classical result about T-joins (see [1]) is that whenever G is connected, there exists a T-join for every even-sized subset T of V(G). Consider a connected graph G of even order, and let T be the set of its even vertices. The handshake lemma assures that T has even size, hence there exists a T-join H. By putting K := G - E(H) we obtain an odd factor of G, i.e. a spanning odd subgraph. Note that if the T-join H was chosen to be a forest, then the obtained odd factor K satisfies the following statement.
270
Ars Math. Contemp. 9 (2015) 165-186
Proposition 2.2. Given a connected graph G of even order, there exists an odd factor K of G such that G — E(K) is a forest.
3 Tight upper bound for x'o
In this section, through a number of propositions we derive the main result of the paper, a general tight upper bound xO < 6 with a characterization of the loopless connected graphs for which the bound is achieved.
Proposition 3.1. Given a loopless connected graph G of even order, it holds that
X'o(G) < 3 . If furthermore G is even, then xO(G) < 2.
Proof. By Proposition 2.2, we can take an odd factor K of G such that G — E(K) is a forest denoted by F. From Proposition 2.1 we infer that
XO(G) < XO(F)+ XO(K) < 2 + 1 = 3 . If in addition G is even, then F is a spanning odd forest of G, giving
XO(G) < XO(F)+ XO(K) < 1 + 1 = 2, which completes the proof.	□
Let G be a loopless graph. By a bouquet of parallel edges in G we refer to a subset of E(G) consisting of all the edges linking a pair of adjacent vertices.
Figure 2: A loopless graph (left) and its reduction (right).
The reduction red(G) of a loopless graph G is defined to be a spanning subgraph of G obtained by the following change at every bouquet of parallel edges: remove maximum possible even number of edges without altering the adjacency relation in V(G) (see Fig. 2 for an example). Obviously, up to isomorphism, each loopless graph has a unique reduction. We say that a loopless graph G is reduced whenever its multiplicity is at most 2, i.e. when G = red(G).
It was already remarked in [2] that an odd k-edge-coloring of its reduction readily provides an odd k-edge-coloring of any loopless graph G, since the removed edges between
B. Luzar et al.: Odd edge coloring of graphs
271
any two adjacent vertices may all adopt one arbitrary color used on the remaining edges between them in red(G). Hence,
xO(G) < xO(red(G)).	(3.1)
Remark 1. Regarding the inequality (3.1), suppose that a graph G satisfies xO(G) < x'(red(G)). In respect of the reduced graph red(G), assume G is minimal such graph in terms of size. Consider an arbitrary optimal odd edge coloring of G. Then, by the minimality of G, on each bouquet of parallel edges no color appears more than once, unless possibly on a bouquet of size 2. In other words, in every optimal odd edge coloring, on any bouquet of parallel edges in G that reduces in size for red(G), no color is repeated. Hence, whenever the inequality (3.1) is strict, it holds that x'(red(G)) > 4.
A loopless graph G on three pairwise adjacent vertices is referred to as a Shannon triangle. Denote the sizes of its bouquets of parallel edges by p, q, r in non-increasing order. We say that the considered Shannon triangle is of type (p, q, r). In particular, whenever p, q, r are even, we speak of a Shannon triangle of even type. Observe that there are exactly four different types of reduced Shannon triangles and only one of them is of even type (depicted in Fig. 3).
Next, we prove that (3.1) is always an equality for the case of Shannon triangles. Furthermore, we prove that the reduced Shannon triangles of different types attain odd edge chromatic indices for all integer values between 3 and 6.
Proposition 3.2. Given a Shannon triangle G, let (p, q, r) be the type of red(G). Then
xO(G) = xO (red(G)) = p + q + r.	(3.2)
Figure 3: The four types of Shannon triangles with odd chromatic indices 3, 4, 5, and 6, respectively. The last one is of even type.
Proof. Observe that in an arbitrary odd edge coloring of a Shannon triangle, no color appears altogether an even number of times on any bouquet. Namely, denote the vertices of the triangle by u, v, and w and suppose that on the edges between u and v some color, say 1, appears in total an even number of times. This implies that 1 appears overall an odd number of times on each of the remaining two bouquets. Thus, 1 appears an even number of times at the vertex w, a contradiction.
This clearly implies that no color is repeated in an arbitrary odd edge coloring of a reduced Shannon triangle. Hence the second equality in (3.2) is established.
272
Ars Math. Contemp. 9 (2015) 165-186
Next, we prove the first equality. Suppose there exists a Shannon triangle G for which xO(G) < xO(red(G)). In respect of the reduced graph red(G), assume G is minimal such graph in terms of size. Then, Remark 1 and the above observation imply that no color is repeated in an optimal odd edge coloring of G. This readily gives xO(G) > xO(red(G)), a contradiction.
□
In the following, we give several other propositions leading to the main theorem of this article, but first we introduce some additional notation. Let v be a vertex of a reduced graph G and Sv be the subgraph of G induced by the set of edges incident to v, i.e. Sv := G[E(v)]. Each pair of parallel edges from this subgraph is said to be a petal of v. Each edge of a petal is referred to as a petal edge of v. The other edges incident to v are called leaf edges of v. Denote by p(v) and l(v) the number of petals and number of leaf edges of v, respectively.
Proposition 3.3. If a connected reduced graph G has a non-cutvertex v for which either p(v) is odd or l(v) = 0, then xO(G) < 5.
Proof. By Proposition 3.1, we may assume n(G) is odd. Suppose v is a non-cutvertex of G such that either p(v) is odd or l(v) = 0. We consider the four possible cases according to the parities of p(v) and l(v):
(i) p(v) is odd and l(v) is even. By Proposition 3.1, there exists an odd 3-edge-coloring ^ of G - v with color set {1, 2, 3}. We extend ^ to G by using two additional colors 4 and 5: color by 4 each leaf edge of v and precisely one petal edge from each petal of v; color by 5 the remaining petal edges of v. We obtain an odd 5-edge-coloring of G.
(ii) p(v) is odd and l(v) is odd. Let e be a leaf edge of v. Let F be a forest in G - v (as in the proof of Proposition 3.1), and add v together with the leaf edge e to F. We obtain a forest F' in the subgraph G' := G - (E(v)\e). Since two colors suffice for an odd edge coloring of F' and the edge set E(G')\E(F') induces an odd subgraph of G', by using a third color for the edges from E(G')\E(F') we obtain an odd 3-edge-coloring ^ of G'. We extend ^ to an odd 5-edge-coloring of G as in (i).
(iii)	p(v) is even and l(v) is odd. In this case, we use a similar approach as in (ii), but take a petal edge of v as the edge e, instead. Again, we finish as in (i).
(iv)	p(v) is even and l(v) is even and positive. Let ^ be an odd 3-edge-coloring of G — v with color set {1, 2, 3}. Extend ^ to G by coloring with 4 one leaf edge of v and precisely one petal edge of each petal of v, and moreover, by coloring with 5 all the remaining uncolored edges incident to v. We obtain an odd 5-edge-coloring of G.
□
Whenever l(v) = 0, we refer to Sv as the orchid at v. According to the parity of p(v), we distinguish between even and odd orchids.
A graph obtained from a path of length k > 1 in which every edge is replaced by two parallel edges is called an open k-necklace. Observe that every open k-necklace is an even graph of order k +1. Similarly, a graph obtained from a cycle of length k > 2 in which every edge is replaced by two parallel edges is called a closed k-necklace. Every closed k-necklace is an even graph of order k.
B. Luzar et al.: Odd edge coloring of graphs
273
Proposition 3.4. The odd chromatic index of an open k-necklace G satisfies
x0(G)
2 if k is odd, 4 if k is even.
Proof. Assume k is odd. Since G needs at least two colors for an odd edge coloring, Proposition 3.1 implies x0(G) = 2. We construct a particular odd 2-edge-coloring of G that we will use in Proposition 8. Fix one of the two natural orders for the bouquets of parallel edges of G, and color as follows:
1)	for the edges of the first, third, fifth,..., k-th such bouquet use each of the colors 1 and 2 once;
2)	for the edges of the second, fourth, sixth,..., (k - 1)-st such bouquet use the color 1 twice.
Assume now k is even. First we establish the inequality x'0(G) < 4 by constructing an odd 4-edge-coloring of G. Again, by fixing one of the two natural orders for the bouquets of G: on the edges of the first (k - 1) bouquets apply the odd 2-edge-coloring of 1) and 2); for the edges of the k-th bouquet use each of the colors 3 and 4 once.
Second we prove x0(G) = 4. Suppose x0(G) < 4 and consider an optimal odd edge coloring of G. Fix one of the two natural orders for the bouquets of G. Obviously, the first bouquet is dichromatic, i.e. two colors are used for its edges. Hence, x0(G) < 4 implies that the second bouquet is monochromatic. But then the third bouquet is dichromatic, etc. We deduce that the k-th bouquet is monochromatic. This is a contradiction, hence
Proof. Assume k is even. Since G needs at least two colors for an odd edge coloring, Proposition 3.1 implies xO(G) = 2.
Assume next k is odd and k > 5. First we prove xO(G) < 4 by constructing an odd 4-edge-coloring of G. Remove a vertex v from G to obtain the open (k — 2)-necklace G — v. Use the odd 2-edge-coloring of G — v constructed in Proposition 3.4 with a single change of color: for one edge from the last bouquet instead of using the color 2 use the color 3. Now color the edges of the orchid at v:
•	for the uncolored petal of v "neighboring" a bouquet from G — v colored by 1 and 2, use the color 2 for both edges;
•	for the remaining uncolored petal of v use the colors 2 and 4 once each.
Now, suppose xO(G) < 4 and consider an optimal odd edge coloring of G. Obviously, at each vertex the orchid is dichromatic with three of its edges having the same color. Thus, any two consecutive bouquets in G are such that one is monochromatic and the other is
x0(G) = 4.
□
Proposition 3.5. The odd chromatic index of a closed k-necklace G satisfies
274
Ars Math. Contemp. 9 (2015) 165-186
dichromatic. Hence, precisely half of the k bouquets in G are monochromatic. This is a contradiction with the parity of k.
Finally, note that for k = 3, the closed k-necklace G is the Shannon triangle of type (2,2, 2) and thus xO(G) = 6 (see Proposition 3.2).
□
We are now in a position to prove our main result for loopless 2-connected graphs.
Proposition 3.6. Let G be a loopless 2-connected graph which is not isomorphic to a Shannon triangle of even type. Then xO(G) < 5.
Proof. By Proposition 3.1, inequality (3.1) and Proposition 3.3, we may assume that G has odd order n and is a 2-connected reduced graph with an even orchid at every vertex. Denote by v a vertex of maximum degree in G. If the orchid Sv has precisely two petals, then G is a closed n-necklace with n > 5 (namely, if n =3 then G would be the Shannon triangle of type (2,2, 2)). Hence, in this case Proposition 3.5 implies xO(G) = 4.
So, we may assume Sv has at least four petals. Consider the graph G - v and denote by mi, u2, • • •, u2s the neighbors of v in G. By Proposition 3.1, we have xO(G - v) = 2. Consider an initial odd 2-edge-coloring of G - v with color set {1,2} such that the edges of the spanning odd forest F constructed in the proof of Proposition 3.1 are colored by 1.
Denote by M the collection of maximal paths in F that have non-empty intersection with the set {u1; u2,..., u2s}. Note that every member of M is non-trivial and has both end-vertices among the leaves of F. We distinguish between the following three cases:
(i)	At least one P G M does not have both end-vertices in the set {m1, u2,..., u2s}. Start
a tracing of one such path P from an end-vertex not belonging to {m1, u2 ,..., u2s}. Let u be the first vertex from V(P) n {u1, u2,..., u2s} met on this tracing, and denote by P0 the traced subpath of P. Beginning at the edge incident to u, recolor the edges of P0 by the colors 3 and 4, alternatingly. Color the petal edges of v in the following way: use the color 4 for one vu-edge, while using the color 1 for all the remaining petal edges incident to v. Thus, we obtain an odd 4-edge-coloring of G.
(ii)	Each member of M has both end-vertices in the set {u1, u2,..., u2s} and there is
such a path P G M of length at least 2. Denote by u and « the end-vertices of P. We recolor the edges of P by using the colors 3,4 and 5 as follows: the edge incident to uj is recolored by 3 and the edge incident to « is recolored by 4. The other edges along P are recolored in such a way to obtain a proper edge coloring of P, which is clearly achievable. Color the petal edges of v in the following way:
•	use color 4 for both vuj-edges;
•	use color 4 for one vuj-edge;
•	use color 1 for the remaining petal edges of v.
Thus, we obtain an odd 5-edge-coloring of G.
(iii)	Each member of M has both end-vertices in the set {u1, u2,..., u2s} and there is no such path of length at least 2. In this case, the edges of F incident to at least one of the vertices u1; u2,..., u2s form a matching on the set {u1; u2,..., u2s}. Without loss of generality, suppose this matches u2i-1 with u2j, for every i G {1,2,..., s}. From the initial odd 2-edge-coloring of G - v, we obtain an odd 5-edge-coloring of G as follows:
B. Luzar et al.: Odd edge coloring of graphs
275
•	recolor the edge u1u2 in F with the color 5;
•	use both the colors 1 and 4 once for the petal vu-edges;
•	use both the colors 3 and 4 once for each of the petals vu2, vu3,..., vu2s_1;
•	use both the colors 3 and 5 once for the petal vu2s -edges (here we make use of the fact that s > 2).
This establishes the inequality xO(G) < 5, which completes the proof of the statement.
□
3
2
Figure 4: An odd 4-edge-coloring.
Next we prove that 5 colors suffice for an odd edge coloring of any loopless connected graph which is not a block.
Proposition 3.7. If G is a loopless graph of connectivity k =1, then xO(G) < 5.
Proof. We may restrict to reduced graphs of connectivity k = 1. Suppose the statement is not valid, and let G be a minimal counterexample in terms of the number of blocks. By Propositions 3.1 and 3.3, G has odd order and is a connected reduced graph with an even orchid at every non-cutvertex. Observe that n(G) > 4 (for otherwise k = 1 implies
m(G) < 4).
Choose an end-block B of G, with s being the relevant cut-vertex, such that the graph G' := G - V(B - s) satisfies the inequality xO(G') < 5. Namely, if the graph G has more than two blocks then we merely choose B to be an arbitrary end-block of G: since G' is of connectivity 1 and has one block less than G, the choice of G assures that xO (G') < 5. And, if G has only two blocks, Proposition 3.6 and Fig. 4 assure that at least one of these two blocks will do: G cannot be the odd 4-edge-colorable graph depicted in Fig. 4.
Observe that B is an even graph having odd order. Namely, every v e V (B)\{s} has an even orchid Sv. Hence, the same is true for the vertex s in B, proving that B is an even graph. Regarding the order, an even n(B) would imply that n(G') is also even and hence the inequalities xO(B) < 2 and xO(G') < 3 would yield the bound xO(G) < 5, which is a contradiction.
So, B - s is an even graph of even order. Take an odd factor K of B - s and color the edges from B - s by using the color 1 for E(K) and the color 2 for E(B - s - E(K)). Extend this to an edge coloring of B by using the color 1 for each edge incident to s in B. Use an odd 5-edge-coloring of G' with color set {1, 2,..., 5} such that the color 1 is used for at least one edge incident to s in G'. These two edge colorings of B and G' together constitute an odd 5-edge-coloring of G. This is in contradiction with the choice of G, which completes the proof of the statement.
□
276
Ars Math. Contemp. 9 (2015) 165-186
By now, we have assembled all the parts for a proof of the main theorem in this article. It characterizes the Shannon triangles of even type as the only loopless connected graphs needing the maximum 6 colors for an odd edge coloring.
Theorem 3.8. For every loopless connected graph G, it holds that
x'o(G) < 6.
Equality is achieved only for the Shannon triangles of even type.
Proof. Straightforward from Propositions 3.6 and 3.7.	□
4 Concluding remarks and further work
Based on several additional observations, we propose three conjectures. Conjecture 4.1. For every loopless graph G, it holds that
xO(G)= xO(red(G)).	(4.1)
From Remark 1, we infer that Conjecture 4.1 is true whenever xO(red(G)) < 3 and Theorem 3.8 assures its validity whenever xO(red(G)) = 6. Furthermore, Propositions 3.4 and 3.5 imply that whenever red(G) is a necklace (open or closed), (4.1) stands. Namely, it is readily deduced from Remark 1 that if xO(red(G)) < 4 and every bouquet of red(G) has size 2, then the equality (4.1) is fulfilled.
In regard to Proposition 3.6, we propose the following
Conjecture 4.2. For every loopless 2-connected graph G whose reduction is neither the Shannon triangle of type (2,2,1) nor of type (2,2,2), it holds that
xO(G) < 4.
Furthermore, we believe that an even stronger statement is true. Namely, we propose that the bound in Theorem 3.8 could be further reduced, by excluding the graphs whose reductions are isomorphic to the Shannon triangle of type (2,2,1).
Conjecture 4.3. For every loopless connected graph G whose reduction is neither the Shannon triangle of type (2,2,1) nor of type (2,2,2), it holds that
xO(G) < 4.
Assuming the validity of Conjecture 3, note that any possible counterexample G to Conjecture 4.1 must satisfy xO(G) = 3 and xO(red(G)) = 4.
Another direction for further work is to provide an answer to the following open problem.
Problem 4.4. Characterize the loopless graphs which are odd 2-edge-colorable.
Acknowledgements. We thank the anonymous referees for helpful comments. This work is partially supported by ARRS Program P1-0383.
B. Luzar et al.: Odd edge coloring of graphs
277
References
[1]	J. A. Bondy and U. S. R. Murty, Graph Theory, Graduate Texts in mathematics, Springer, New York 244, 2008.
[2]	J. Czap, S. Jendrol', F. Kardos and R. Sottk, Facial parity edge colouring of plane pseudo-graphs, Disc. Math. 312 (2012), 2735-2740.
[3]	B. Luzar and R. Skrekovski, Improved bound on facial parity edge coloring, Discrete Math. 313 (2013), 2218-2222.
[4]	T. Mdtrai, Covering the edges of a graph by three odd subgraphs, J. Graph Theory 53 (2006), 75-82.
[5]	L. Pyber, Covering the edges of a graph by..., Graphs and Numbers, Colloq. Math. Soc. Jdnos Bolyai 60 (1991), 583-610.
[6]	P. D. Seymour, Nowhere-zero 6-flows, J. Comb Theory Ser. B 30 (1981), 130-135.