GRAPH THEORY - PART 4

4 Colourings 4.1 Edge colourings Colourings of edges and vertices of a graph G are useful, when one is interested in classifying relations between objects. There are two sides of colourings. In the general case, a graph with a colouring is G given, and we study the properties of this pair . This is the situation, e.g., in G = (G; ) transportation networks with bus and train links, where the colour (buss, train) of an edge tells the nature of a link. In the chromatic theory, G is first given and then we search for a colouring that the satisfies required properties. One of the important properties of colourings is ‘properness’. In a proper colouring adjacent edges or vertices are coloured differently. Edge chromatic number DEFINITION. A -edge colouring of a graph is an assignment of colours G : E ! [1; k ℄ kk G to its edges. We write G to indicate that G has the edge colouring . A vertex and a colour are incident with each other, if for some v 2 G i 2 [1; k ℄ (v u) = i . If is not incident with a colour , then is available for . i vv u 2 E v 2 G i G Thecolouring isproper,if notwoadjacent edges obtain the same colour: (e ) = (e )1 2 for adjacent and . e e 1 2 The edge chromatic number 0 (G) of G is defined as 0 there exists a proper -edge colouring of k Gg : (G) = minfk j A -edge colouring can be thought of as a partition of , where k EfE ; E ; : : : ; E g 1 2 G k . Note that it is possible that for some . We adopt a simplified i E = ;E = fe j (e) = ig i i notation G [i ; i ; : : : ; i ℄ = G[E [ E [ [ E ℄ 1 2 t i i i t 1 2 for the subgraph of consisting of those edges that have a colour , , ..., or . That is, the G i ii 1 2 t edges having other colours are removed. Lemma 4.1. Each colour set E in a proper k -edge colouring is a matching. Moreover, for i each graph G, (G) 0 (G) " . G Proof. This is clear. ut 4.1 Edge colourings 44 Example 4.1. The three numbers in Lemma 4.1 can be equal. This happens, for instance, when G = K is a star. But often the inequalities are strict. 1;n A star, and a graph with 0 . (G) = 4 Optimal colourings We show that for bipartite graphs the lower bound is always optimal: 0 (G) = (G) . Lemma 4.2. Let be a connected graph that is not an odd cycle. Then there exists a 2-edge G colouring (that need not be proper), in which both colours are incident with each vertex with v . d (v ) 2 G Proof. Assume that G is nontrivial; otherwise, the claim is trivial. (1) Suppose first that is eulerian. If is an even cycle, then a 2-edge colouring exists G G as required. Otherwise, since now d (v ) is even for all v , G has a vertex v with d (v ) 4 . G 1 G 1 Let be an Euler tour of , where (and ). Define v = v G e = v ve e : : : e 1 2 t i i i +1 t+1 1 ( 1; (e ) = i 2; if is odd i ; if is even i : Hence the ends of the edges for are incident with both colours. All vertices are e i 2 [2; t 1℄ i among these ends. The condition d (v ) 4 guarantees this for v . Hence the claim holds in G 1 1 the eulerian case. (2) Suppose then that G is not eulerian. We define a new graph G by adding a vertex v 0 0 to and connecting to each of odd degree. G v 2 G v 0 In G 0 every vertex has even degree including v (by 0 the handshaking lemma), and hence is eulerian. Let G 0 be an eulerian tour of , where . e = v v Ge e : : : e 0 1 t 0 i i i +1 By the previous case, there is a required colouring of G 0 as above. Now, restricted to is a colouring of as G E G required by the claim, since each vertex with odd degree v i is entered and departed at least once in the tour d (v ) 3 G i by an edge of the original graph G: e e . i 1 i 1 2 2 1 v 0 tu 1 2 DEFINITION. For a -edge colouring of , let k G is incident with (v ) = jfi j v i 2 [1; k ℄gj : A -edge colouring is an improvement of , if k 4.1 Edge colourings 45 X X (v ) > (v ) : v 2G v 2G Also, is optimal, if it cannot be improved. Notice that we always have , and if is proper, then , and (v ) d (v ) (v ) = d (v ) G G in this case is optimal. Thus an improvement of a colouring is a change towards a proper colouring. Note also that a graph always has an optimal -edge colouring, but it need not k G have any proper k -edge colourings. The next lemma is obvious. Lemma 4.3. An edge colouring of is proper if and only if for all vertices G (v ) = d (v ) G . v 2 G Lemma 4.4. Let be an optimal -edge colouring of , and let . Suppose that the k G v 2 G colour i is available for v ,and the colour j isincident with v at least twice. Thenthe connected component H of G [i; j ℄ that contains v , is an odd cycle. Proof. Suppose the connected component is not an odd cycle. By Lemma 4.2, has a H H 2-edge colouring , in which both and are incident with each vertex with x i j : E ! fi; j g H . (We have renamed the colours and to and .) We obtain a recolouring of 2 jd (x) 2 i1 H as follows: G ( (e); if e 2 E ;H (e) = if e 2= E : (e); H Since (by the assumption on the colour ) and in both colours and are j j id (v ) 2 H now incident with v , (v ) = (v ) + 1 . Furthermore, by the construction of , we have for all . Therefore P (u) > P (u) , which contradicts the (u) (u) u = v u2G u2G optimality of . Hence H is an odd cycle. tu Theorem 4.1 (KÖNIG (1916)). If is bipartite, then 0 . G (G) = (G) Proof. Let be an optimal -edge colouring of a bipartite , where . If there = (G) G were a with , then by Lemma 4.4, would contain an odd cycle. But a G (v ) < d (v ) v 2 G G bipartite graph does not contain such cycles. Therefore, for all vertices v , (v ) = d (v ) . By G Lemma 4.3, is a proper colouring, and 0 as required. = (G) ut Vizing’s theorem In general we can have 0 as one of our examples did show. The following (G) > (G) important theorem, due to VIZING, shows that the edge chromatic number of agraph G misses by at most one colour. (G) Theorem 4.2 (VIZING (1964)). For any graph G, (G) 0 (G) (G) + 1 . Proof. Let . We need only to show that 0 . Suppose on the contrary = (G) (G) + 1 that 0 , and let be an optimal -edge colouring of . ( + 1) G (G) > + 1 4.1 Edge colourings 46 We have (trivially) 0 for all , and so u 2 G d (u) < + 1 < (G) G Claim 1. For each u 2 G, there exists an available colour b (u) for u . Moreover, by the counter hypothesis, is not a proper colouring, and hence there exists a with , and hence a colour that is incident with at least twice, say v 2 G v i (v ) < d (v ) G 1 (v u ) = i = (v x) : (4.1) 1 1 Claim 2. There is a sequence of vertices u ; u ; : : : such that 1 2 ... - tailieumienphi.vn