graph theory
6.1.3 (a) Show that if G is bipartite, then G has a A-regular bipartite supergraph. (b) Using (a) and exercise 5.2.3a, give an alternative proof of theorem 6.1. 5.2.3 For k>0, show that (a) every k-regular bipartite graph is 1-factorable; (b)* every 2k-regular graph is 2-factorable. (J. Petersen) 6.1 EDGE CHROMATIC NUMBER A k-edge colouring of a loopless graph G is an assignment of k colours, 1, 2, ..., k, to the edges of G. The colouring & is proper if no two adjacent edges have the same colour. Alternatively, a k-edge colouring can be thought of as a partition (E., E2, ..., Ex) of E, where E denotes the (possibly empty) subset of E assigned colour i. A proper k-edge colouring is then a k-edge colouring (E., E2, ..., Ex) in which each subset E is a matching. The graph of figure 6.1 has the proper 4-edge colouring ({a, s}, {b, e}, {c, f}, {d}). G is k-edge colourable if G has a proper k-edge-colouring. Trivially, every loopless graph G is e-edge-colourable, and if G is k-edge-colourable, then G is also l-edge-colourable for every l>k. The edge chromatic number x'(G), of a loopless graph G, is the minimum k for which G is k-edge- colourable. G is k-edge-chromatic if x'(G)=k. It can be readily verified that the graph of figure 6.1 has no proper 3-edge colouring. This graph is therefore 4-edge-chromatic. Clearly, in any proper edge colouring, the edges incident with any one vertex must be assigned different colours. It follows that X'2A (6.1) Referring to the example of figure 6.1, we see that inequality (6.1) may be strict. However, we shall show that, in the case when G is bipartite, x'= A. The following simple lemma is basic to our proof. We say that colour i is represented at vertex v if some edge incident with v has colour i. Lemma 6.1.1 Let G be a connected graph that is not an odd cycle. Then 9 Figure 6.1 Lemma 6.1 Let G be a connected graph that is not an odd cycle. Then Figure 6.1 92 Graph Theory with Applications G has a 2-edge colouring in which both colours are represented at each vertex of degree at least two. Proof We may clearly assume that G is nontrivial. Suppose, first, that G is eulerian. If G is an even cycle, the proper 2-edge colouring of G has the required property. Otherwise, G has a vertex te of degree at least four. Let ... 6. be an Euler tour of G, and set E.-{eli odd) and Es={eli even) (6.2) Then the 2-edge colouring (E., E.) of G has the required property, since cach vertex of G is an internal vertex of of...De. If G is not culerian, construct a new graph G* by adding a new vertex and joining it to each vertex of odd degree in G. Clearly G is culerian. Let BoC,B... Debe an Euler tour of G and define E, and E, as in (6.2). It is then easily verified that the 2-edge colouring (ENE,E,NE) of G has the required property D Given a k-edge colouring of G we shall denote by c(u) the number of distinct colours represented at v. Clearly, we always have (6.3) Moreover, is a proper k-edge colouring it and only if equality holds in (6.3) for all vertices of G. We shall call a k-edge colouring an improvement on ex> cm where c'(o) is the number of distinct colours represented at vin the colouring e'. An optimal k-edge colouring is one which cannot be im- proved. Lemma 6.1.2 Let-(E.Em..., E.) be an optimal k-edge colouring of G. If there is a vertex w in G and colours i and such that i is not represented at u and is represented at least twice at then the component of G[EUE) that contains w is an odd cycle. Proof Let u be a vertex that satisfies the hypothesis of the lemma, and denote by H the component of G[EUE) containing u. Suppose that His not an odd cycle. Then, by lemma 6.1.1, H has a 2-edge colouring in which both colours are represented at each vertex of degree at least two in H. When we recolour the edges of H with colours i and in this way, we obtain a new k-edge colouring (E, ES,..., E) of G. Denoting by c'(u) the number of distinct colours at v in the colouring, we have c"(u) = c(u)+1
