A sufficient condition for equitable edge-colourings of simple graphs

A sufficient condition for equitable edge-colourings of simple graphs

Discrete Mathematics North-Holland 179 128 (1994) 179-201 A sufficient condition for equitable edge-colourings of simple graphs A.J.W. Hilton* Depa...

1MB Sizes 3 Downloads 52 Views

Discrete Mathematics North-Holland

179

128 (1994) 179-201

A sufficient condition for equitable edge-colourings of simple graphs A.J.W. Hilton* Department

of Mathematics.

University of Reading, Whiteknights, Reading RG6 ZAX, UK

D. de Werra Dkpartement de Mathematiques, Ecole Polytechnique Fidhrale de Lausanne. CH-1015, Lausanne, Switzerland Received 9 April 1991 Revised 5 May 1992

Abstract An edge-colouring of a graph G is equitable if, for each vertex colour incident with v differs from the number of edges of any one. We show that if k > 2 and k,j’d(o) (Vue F’(G)) and G is a edge-colouring with k colours. This result is also extended to simple graphs.

v of G, the number of edges of any one other colour incident with u by at most simple graph, then G has an equitable one about I-regular edge-colourings of

1. Introduction

In this paper, graphs will be finite and simple, so they will have no loops or multiple edges. Given a graph G and WV(G), let do(u) (or d(u)) denote the degree of u. An edge-colouring of G is an assignment of colours to the edges of G. Given an edgecolouring of G with k colours cl, . . . , ck, for UEV(G), let Ci(U) denote the set of edges incident with u coloured ci. Call an edge-colouring of G with k colours, cr, . . . , ck, equitable if, for each DEV(G), IIci(a)l-Icj(a)l1<1

(l
and nearly equitable if, for each DEV(G),

IICi(~)l-I~j(~)ll<2 (l
University

of Reading,

Morgantown,

Science B.V. All rights reserved

P.O. Box 220,

WV 26506, USA.

180

A.J. W. Hilton. D. de Werra

Theorem 1.1. Let G be a simple graph and let k> 2.Zfk,j’d(v) (VVE V(G)) then G has an equitable edge-colouring with k colours. (Note: k$d means that k does not divide d.)

If k = A(G) + 1, where A(G) is the maximum degree in G, then Theorem 1.1 reduces to Vizing’s theorem [17]. If k= 6(G)- 1, where 6(G) is the minimum degree in G, then Theorem 1.1 implies Gupta’s theorem [lo] (apply Theorem 1.1 to the graph obtained from G by adjoining a pendant edge to each vertex 2,for which kid,(v)). We first proved Theorem 1.1 over ten years ago, and the result was quoted by Berge [3]. Our original paper concerned multigraphs and remains unpublished, and, as it seems that it really was rather too indigestible as well as not being error-free, we decided to write this present simplified version with a view to possibly publishing a multigraph version later. We remark that somewhat similar theorems have been proved for vertex colourings; Hajnal and Szemeredi Cl 11 showed that if kaA(G)+ 1 then G has a proper vertex colouring with k colours in which the size of the vertex-colour classes differ by at most one, and Meyer [16] and Bollobas and Guy [S] improved this (by having lower values of k) for trees. A number of further papers which are closely related in one way or another to the contents of this paper are given in the references.

2. A useful lemma

A cycle is a connected graph in which each vertex has even degree; a cycle is even, or odd, according as to whether the number of edges is even, or odd, respectively. An edge-colouring with two colours will be called a bicolouring. We shall use the following well-known lemma. We include the short proof for the sake of completeness. Lemma 2.1. Let G be connected. It has an equitable bicolouring ifand only ifit is not an odd cycle. Moreover, ifG is an odd cycle and vOe V(G), then there is a bicolouring with colours cl and c2 such that IIcl(vo)l-lc2(v0)ll=z ~~c~(v)~-I~~(~)II=O

for v#uo.

Proof. If G is an odd cycle, then it has an Eulerian cycle with an odd number of edges. We obtain the bicolouring by colouring the edges alternately c1 and c2, starting at vo. If G is an even cycle, the same method yields a bicolouring with I)c1(v)I- 1c2(v) )I= 0 for all VEV(G). If G is not a cycle, then we can pair off the vertices of odd degree, and join the two vertices of each pair by an extra edge. The graph G + so formed is a cycle. Provided we start with an extra edge, the argument above yields a bicolouring of G+ which, when restricted to G, is equitable. 0

181

Edge-colourings of simple graphs

3. A generalization Given a graph associated

of Theorem 1.1. G and a vertex v in V(G), and given k, we define two parameters

with d(v). We let

Note that

dV)#b(u) *

k/I’d(u) o

ka(v)+ 1
1

and that, in an equitable edge-colouring of G, each colour occurs on either a(v) or b(v) edges incident with G. In the proof of Theorem 1.1, if a subgraph H of G, consisting of the edges coloured with two colours, say cl and c2, satisfies 2a(v) b(x), then we can usually recolour H with c1 and c2 so that

However, by Lemma 2.1, when H is connected this is not possible if and only if H is an odd cycle. Thus, such subgraphs present particular difficulties for us. We call a connected subgraph H of G with IE(H)I odd and, for each UE V(H), dH(v)E{2u(v), 2b(v)}, an obstruction (to an equitable colouring). Clearly, any obstruction is an odd cycle. We shall prove the following generalization of Theorem 1.1. Theorem 3.1. Let G be a simple graph and let ka2. Suppose that in every obstruction there is a vertex v such that, for each neighbour y of v lying in an obstruction,

ku(y)+16d(y)gkb(y)-1, then G has an equitable edge-colouring with k colours. We remark that the condition ku(y) + 1
182

A.J. W. Hilton, D. de Werra

B

A

Fig. 1.

Corollary 3.2. Let G be a simple graph. Suppose that in every odd circuit there is a vertex v such that, for every neighbour y of v lying in an odd circuit, d(y) < A(G), then G is class 1.

In Fig. 1 the graph A has to be class 1 because of Corollary 3.2. The rather similar graph B is class 2. Theorem 3.1 has the following further corollary, which is of course easy to prove directly. Corollary 3.3 (de Werra [lS]). Let G be a simple bipartite graph and let ka2. G has an equitable edge-colouring with k colours.

Then

Let the k-core of G be the subgraph of G induced by the vertices of G such that kjd(v). Hoffman and Rodger [lS] have referred to the A(G)-core of G as the core of G. Theorem 1.1 can also be strengthened in the following way, different from Theorem 3.1. Theorem 3.4. Let G be a simple graph and let k 3 2. If the k-core of G is a set of isolated vertices, then G has an equitable edge-colouring with k colours.

We prove Theorem 3.4 in Section 6. Theorem 1.1 also has the following corollary. Corollary 3.5. Let G be a simple graph and let k 22. G with k colours such that, for each VE V(G),

There is an edge-colouring of

~~tc1(v)~-~rc2(v)~~=2 for at most one pair {rc1,rc2} of colours, and

(1) IIK(v)I-IIc*(v)I(<~

for all pairs (K,K*}#{K~,K~} ofcolours.

183

Edge-colouringsof simplegraphs

Proof. From G construct a graph G, by adjoining a pendant edge to each vertex v with de(a)-O(mod k). Then apply Theorem 1.1 to G1. The corresponding edgecolouring of G clearly satisfies (1). 0 In fact, Corollary 3.5 is equivalent to Theorem 1.1. We have shown that Theorem 1.1 implies Corollary 3.5. To see that Corollary 3.5 implies Theorem 1.1, suppose that G satisfies the condition that k$d(v) for all VEV(G) and is edge-coloured so that (1) is satisfied. For each VEV(G), since k$d(v), it is not possible to have I I ICY(v)l -I Q(V)\ I = 2 for one pair {K~,K~} of colours unless some second pair {K~,ICY}# {K~,K*} satisfies

IIM4I-l~4(~)I1=2

also.

4. Some further preliminary lemmas Some of the lemmas given below can be found, for instance, in [19]; we prove them here in order to make this paper self-contained. Let G be a graph and let k>2. If G is given an edge-colouring with k colours cl, . . . 3ck, then for VEV(G) and 1 d i < k, let

ICi(V)I-b(V)~ a(v)-ICi(U)I),

ai(V)=max(O,

E(U)=max oi(V) and l$iSk

C(V)=

i

ai(

i=l

If G is edge-coloured and c(and p are two of the colours used, and if VEV(G), then let G(v; c(,p) be the component containing v of the subgraph of G induced by the edges coloured o! and fi. Lemma 4.1. Let G be a simple graph and let k > 2. Suppose G is given an edge-colouring with k colours c l>...yck. vertex v. then

max

lgicjbk

E’(~)
where

E’

If11CI(VO)1--IB(VO)11>2f or some pair CY,j of colours and some in which

G has an edge-colouring IIci(vo)l-lcj(vo)ll~2 a’(v)
(VVE

(SO that &‘(vo)6 l), and

I’(G)),

and u’ denote the values of E and a in the second edge-colouring.

Proof. We apply Lemma 2.1 to the subgraph G(vo; CI,/I) in such a way that we obtain

ll~(~o)l-IB(~o)ll62, fJ”(V)Gm and

E”(V) < E(V)

(VVE

V(G)),

where a” and E“ denote the functions g and E after this recolouring. Repeating this as necessary for different pairs of colours, we ultimately obtain

II~i(Vo)l-l~~(~~)ll~2 (l
184

A.J. W. Hilton, D. de Werra

(which implies E’(u,,)< l), E’(u)
for all

UE

V(G).

q

Lemma 4.2. Let G be a simple graph and let k 2 2. Suppose G is given an edge-colouring with k colours. Then G has a nearly equitable edge-colouring with k colours such that E’(V)<&(U), &‘(U)
E’

O’(V)
and o’ denote the values of

E

O’= v(G)),

and o in the second edge-colouring.

Proof. We apply Lemma 4.1 successively obtained

to different vertices of G until we ultimately

and s’(U)
E’(U)<

1

and

a’(u)
0

We use Lemma 4.2 in the proof of Theorem 3.1 (but not in the proof of Theorem 6.1) and, with a slightly different interpretation, in the proof of Theorem 7.1. Lemma 4.1 is only used to prove Lemma 4.2. Lemma 4.3. Let G be a simple graph, let ka 2, and let uoe V(G). Suppose G is given a nearly equitable edge-colouring with k colours with a(uo) > 0. Let a and p be colours with either ~cc(vo)l>b(uo)>~/?(uo)~ or la(uo)l>a(uo)>~~(uo)~. If G(uo;a,B) is not an obstruction in which 1a(u)1= IB(u)lf or each vertex u # uo, then there is a nearly equitable edge-colouring with k colours, obtained by recolouring G(u,;a, B), in which a’(vo)
G(u,;~,fl)

[email protected](v)1=Ifi(v)l

with c1 and /I so that the edge-

for UEV’(G(U~; a, p)), u#ur,

for an

Clearly in case (i), we obtain an edge-colouring with g’(uo) < a(uo), a’(u) < O(U)for all UE V(G), u # vo, and E’(U)
Edge-colourings of simple graphs

185

the connected subgraph coloured cr,y containing v2 after this latter recolouring. We can then apply Lemma 2.1 to G(vz; CC, y) in such a way that after a further recolouring we have

in the first case, or I4vz)l=w72)+

19 IP(

= Ir(v2)l

=W2)

in the second. We then have a’(vO)
5. Exchange chains In order to ‘improve’ the colouring of an edge-coloured graph, we shall use the concept of an exchange chain. An (a, /I)-exchange chain K of G is a sequence (uo, el, vl, e2, . . . , v,_ 1,e,, v,) of vertices and edges of G in which (i) for 1 /l(vo)J; similarly, if p denotes the colour of e, and ,ii denotes the other colour, then I,~(v~)l>lfi(v~)l. If a(vo) > p(vo) an (a, p)-exchange chain can be ‘grown’ (i.e. constructed one edge at a time). The final vertex v, may be the same as the initial vertex uo. From our point of view, if e, is coloured a and Ia(vo) 12 Ij3(vo)l + 2 then in general interchanging the colours in K improves the colouring. However, if Icr(uo)I = Ij?(vo) I + 2 and v. = u, then no improvement is brought about by interchanging the colours. It is clear, however, that an interchange of colours in an exchange chain never ‘makes the colouring worse’.

6. Proof of Theorems 3.1 and 3.4. To prove Theorem 3.1, we first prove the following theorem.

186

A.J. W. Hilton, D. de Werra

Theorem 6.1 Let G be a simple graph and let k 2 2. Suppose G is given a nearly equitable edge colouring (so that E(U)< 1 (VUE V(G))). Suppose that,for some XE V(G), E(X)= 1. If; for each neighbour y of x lying on an obstruction, ka(y)+

1
1,

then G can be recoloured to give a nearly equitable edge-colouring with k colours with .$(x)=0, E’(u)
3.1 is a consequence

of Lemma 2.1 (and is also

less informative than Lemma 2.1). We do not therefore need to consider in Theorem 6.1, but include it here nevertheless for completeness.

the case k = 2

Proof. When k =2 no neighbour y of x lies on an obstruction, for if it did then d(y) = ka( y) or kb( y), and so d(y) would not satisfy the inequality. It follows that the component of G containing x is not an obstruction. Therefore, by Lemma 2.1, it has an equitable edge-colouring with two colours, so it can be recoloured with two colours with s’(u)=0 and o’(u)=0 (VUEI/(G)). Now suppose that k> 3. Our immediate object is to find a nearly equitable recolouring of G such that E’(X)<&(X), a’(x) < a(x) and E’(u) 1). Suppose that the following have been defined (see Fig. 2). (i) Distinct vertices y,, . . . ,yi_ 1. jOiIlS X t0 (ii) Distinct edges eo, . . . ,ei_l; for O 1, the obstruction Hi-l is, at (iv) Obstructions Ho, . . . , the start of the ith stage, coloured climl and p with ej

and

ICri-l(U)l=lfi(“)I (VUEV(Hi-I)).

Yj.

187

Edge-colourings of simple graphs

[lai-I(x)I

-

IPCx)l

+ 21

Fig. 2.

In Hi_ r, x is joined to yi _ 1 and yi _ 2 if i 2 2, to y. and at least one other vertex if i = 1. (v) If the present values of e and E are denoted by (T* and E*, the original by o and E, respectively, then ~*(u)
and

E*(U)<&(U)

(VUEV(G)).

We choose cli SO that ICri(yi_l)l#lai_,(yi-l)l. Then clearly ai#ai-i ai-l(yi-l)=fi(yi-r) (by (iv)) it follows that tii#p. Note that since yi_l obstruction Hi- 1 it follows by hypothesis that

and, since lies on the

Consequently, kXd(yi_ i), SO it is possible to choose such an ai. Notice that if Cli=ap then yp#yi-l. for some p~{l, . . . ,i-2}, If G has an edge coloured ui incident with x then let ei be such an edge, and let yi be the vertex at the other end of ei. If yi is not defined at this point, then Mx)I=IP(x)I=0-

188

A.J. W. Hilton. D. de Werra

We now take one of three distinct courses of action. There are three ‘bad cases’, B,,B2, and B3 which play an important role here (they are described below). We summarize now the courses of action. Course 1: If a 0, . . . , Cli are distinct and one of B1, BP, B3 applies, then the algorithm may terminate or we may have to iterate the procedure described above and find Ui+ 1. Course 2: If UiE{aO, . . . , ct_ 1> and one of B1, Bz and B3 applies, then we finish the proof directly by finding an improved colouring. Course 3: If none of B,, Bz, and B3 apply, then we again finish the proof directly by finding an improved colouring. Note that in each of the previous stages one of the ‘bad cases’ will have arisen; otherwise, our procedure would have terminated. Courses 1 and 2 involve a detailed examination of these ‘bad cases’. Before describing these ‘bad cases’ in detail, we first need to discuss a certain kind of exchange chain. If lai(yi-l)l>lcri-1(yi-,)( and lai-1(X)I>ICLi(X)I,we let K be an (ai, ai- &exchange chain starting at yi_ I (with an edge coloured ai) such that one of the following is true: (A) K does not stop at x or yi-1 and does not contain ei-1, (B) K consists of ei_ 1 together with an odd cycle on yi_ r (the odd cycle does not contain x or ei _ 1), (C) K ends at x with an edge f (coloured ai_ 1) distinct from ei- 1, and K does not use f?i-1. The existence of K is justified by the following lemma, which is very similar to a lemma proved by Fournier. Lemma 6.3 (Fournier

[7]). There is an exchange chain K satisfying one of(A), (B)

or (C). Proof. Let K be an (ai, ai_ ,)-exchange chain starting at yi_ I with an edge coloured Cli.

One possibility is (1) K does not stop at x or yi_ 1 and does not contain et_ 1. This is case (A). Another possibility is (2) K stops at x and does not contain ei_ 1. The last edge must be coloured ai_ 1, so this is case (C). Another possibility is (3) K stops at yi_1 and does not contain x or ei- 1. In this case the last edge must be coloured ai, so K is an odd cycle on yi _ r. Then we redefine K by adjoining ei_ 1 (as the final edge). This is now case (B). Another possibility is (4) K stops at yi- 1, does contain x, but does not contain ei_ 1. As in (3) the last edge must be coloured ai, so K is an odd cycle containing x and yi-1. But in this case we can redefine K so that it starts at yi_ 1 and stops at x with an edge coloured Cli-I (we might have to take the last part of the odd cycle in the reverse direction as the redefined K). This is then case (C) again.

189

Edge-colourings of simple graphs

Table

1 B2

B1

B,

lai(x)l=lai-,(x)l-l=IB(x)l+l Mh-dl =lai-lb+d--l

=IB(Yi-III--1

l~i~~i-~~l=l~i-~~~i-~~l+~=lP~~i-~~l+~ K satisfies (B); also, after interchan-

K satisfies (C)

ging the colours in K, every maximal (ai_ Ir @-exchange chain starting at x with an ai_ 1 edge stops at yi_ 1 (necessarily with an edge coloured a,-l)

These are all the possibilities in which ci- I is excluded. So now suppose that ci- 1 is included. If ei_ 1 is traversed in the direction yi_ 1-+x then K can be stopped at x and we have case (B) again. If ei_1 is traversed in the direction x--+Y~_~then the trail starting at yi _ 1, with e i _ 1 as the final edge, is an even cycle K *. In this case we remove K* temporarily from G, and in the new graph redefine K. The edge ei_ I is no longer in the graph so only cases (l), (2), or (3) can arise. Now restore K * to G. Cases (l), and (2) are cases (A) and (C), respectively. Case (3) yields case (B) as it did above. This concludes the proof of Fournier’s lemma. 0 We now describe these ‘bad cases’ as they arise in the ith stage after ai, ei and yi have been found (or after ai has been found if ei and yi are not defined), but before any other manipulations are carried out. They are given in Table 1. If B1 applies, we can recolour ei_ 1 with Cli(it was previously coloured Cli_1). If B, or B3 apply, we can interchange on K. If we do recolour ei_ 1 when B1 applies, or interchange on K when Bz or B3 apply, then we let Hi = G(x; Cli,fl) (this graph being defined with respect to the graph G as it now is coloured, that is to say, after the recolouring or interchange just described). We now describe in detail the three courses of action. Course 1: x0, . . . , CLiare distinct, and one of B1, Bz and B3 applies. Course la: B1 applies. In this case we recolour the edge ei-i with cli. Before recolouring we had Itli~x~I~lcli-l~x~I~l~IP~x~l+l~

Icri(Yi-l)l=lcli-l(Yi-~)l-l

and after recolouring we have IGli-l(x)l=ltli(X)l--l=lP(X)I+l,

lai-l(Yi-,)l=lai(Yi-,)I-l

and SO the values of D(X),E(X),a(yi_1) and E(yi_1) do not change. If Hi is not an odd cycle, then we recolour Hi by Lemma 2.1 so that Icri(x)l=IP(x)l

190

A.J. W. Hilton. D. de Werra

and, for each vertex w in Hi, w #x,

We then have that a’(x) < a(x), E’(X)< E(X),and a’(u) < a(o) and E’(U)< E(U)(VUEV(G)\ {x}), and so the colouring is improved. If Hi is an odd cycle, but there is a vertex w of Hi other than x at which ICri(w)l# and by Lemma 2.1, Hi can be recoloured so that IP(w then Ibi(w)I-IBWII=Z Itli(w)l-lP(w)I=2 and I~i(“)I=IP(u)I

(VuEV(Hi),

uZw);

we then have that lcr,(x)l = )p(x)\ = Ict- 1(x)1. Then again the colouring is improved. On the other hand, if Hi is an odd cycle and, for each UEV(Hi), u #x, we have Iai I = I /3(u)I, then it is an obstruction and conditions (i)-(v) are satisfied with i instead of i - 1 (Note that ai 1, so yi and ei are defined). We then move on to the (i+ 1)th stage. Course lb: Bz applies. In this case, we interchange the colours on K. Before interchanging we had lai~x~I~lai-~~x~l~l~IB~x~l+l~

Icri-I(Yi-I)l=lai(Yi-I)l-l

and after interchanging on K we have l~i-~~X~I~lai~x~l~l~IB~X~I+l~

lai(Yi-I)l=lai-l(Yi-I)l-l

and so the values of a(x) and a(yi-1) do not change. The situation is illustrated in Fig. 3. The procedure we adopt is that described already in Course la. Course lc: B3 applies. In this case, we interchange the colours on K. Before interchanging we had

and after interchanging on K we have

so the values of a(x) and a(yi _ 1) do not change. The situation is illustrated in Fig. 4. The procedure we adopt is again that described already in Course la. Course 2: CliE{tle, . . . , ui- 1} and one of B1, B2 and B3 applies in the ith stage. Then Ui occurs exactly once in the sequence {a,,, . . . , ai-1).Letcci=a,forsomep,O~p
191

Edge-colourings of simple graphs Before

Yi \

\

\

\

\

I I / I / I

,’ /

/

ai-

After

Yi Qi

Fig. 3.

HP is an obstruction (and so is an odd cycle); at the start of stage p+ 1 it was coloured clP and /I with 1a&)[ = I/3(x)1 + 2. After eP was recoloured clP+r, we had lap(x) I= 1j?(x) I + 1; we also see that HP\{e,} is still a graph coloured up and j? containing x and y,. In stages p + 2, . . . , i- 1 the edges coloured up and /I remain unchanged. During the ith stage, ei- I is coloured tli( = a,), SO lap(x I j?(x)1 + 2 again. Hi contains (HP\{eP1)u{ei-r). y,h as odd degree in Hi, so Hi is not an odd cycle, and thus can be recoloured according to Lemma 2.1. Then IaP(x) I = IB(x) I and the edge-colouring is improved. Course 2b: Br applied in the (p+ 1)th stage and Bz or B3 in the ith stage.

192

A.J. W. Hilton, D. de Werra

Before

X

Qi-l

After

Qi-1

Fig. 4.

At the start of the (p+ 1)th stage l~p(~)l=l~P+l

(41+1=IB(~)l+2

and

and HP is an odd cycle coloured alternately two more edges coloured CQ,than coloured

la,+l(~)I=l~p(~)l+1=IB(~)l+2 and there is an (up, /3)-exchange chain up-edge, ending at y, with a j-edge.

I~,~Y,~I=IB~Y~~I=I~,+~~Y,~I+~

up and /3, except for x at which there are /I?.At the end of the (p+ 1)th stage,

and X (namely

I~,+~~y,~l=IB~yp~l=l~p~yp~l+~~ H,\{e,})

starting

at x with an

Edge-colourings of simple graphs

193

At the start of the ith stage,

Icr~~Yi-~~l~lcci-~~Yi-~~l+l~IP~Yi-~~l+l and ei_1 is coloured ai_1. We interchange on X. Then we have

We now consider G(x; txP,Cli_ 1). This subgraph includes yi _ 1 which has odd degree in it. Therefore, we can obtain an improved colouring by applying Lemma 2.1 to it. Course 2c: Bz applied in the (p+ 1)th stage and B, in the ith stage. At the start of the (p+ l)-stage we have I~p(x)I=I~p+l Wl+1=IPW+2 and la,+,(Y,)l=I~,(Y,)l+l=IB(Y,)l+1 and at the end of the (p+ 1)th stage we have I~,+l(~)I=I~p(~)I+1=IP(~)l+2 and

also there is an (cl,,,&exchange chain X starting at x with an up-edge and finishing at y, with an UP-edge.Between the end of the (p + 1)th stage and the start of the ith stage, the edges coloured ~1,and /I remain the same. At the start of the ith stage X remains as described above and lai-1(x)I=Iap(x)l+1=IB(x)l+2 and lai-l(Yi-,)l=IB(Yi-,)l=la,(Yi-l)l+l. We interchange on X. Then Icli-1(x)I=IB(x)I+1=Iccp(x)l+2 and IS(

= b,(Yp)l+ 1.

Now consider the subgraph G(x; up, ai_1). This graph includes yi_l which has odd degree in it, so we can recolour by Lemma 2.1 and obtain an improved colouring. Course 2d: B2 applied in the (p+ 1)th stage and Bz or B3 in the ith stage.

194

A.J. W. Hilton, D. de Werra

This is the same as Course 2c except for the detail that, in this course, at the start of the ith stage we have lai-l(Yi-,)l=IP(Yi-,)l=lcr,(Yi-,)l-l. Course 2e: B3 applied in the (p+ l)th stage and B, in the ith stage. At the start of the (p+ 1)th stage we have I~pG4I=I~p+I(41+1=IB(41+2 and I~p+~~Yp~l=I”p~Yp~I+~=IP~Yp~I+~ and at the end of the (p+ 1)th stage we have I~,+l(X)l=l~p(X)I+f=IB(X)I+2 and IqY,)I=lql+l

(Y, N+1=IB(Yp)l+l

and the edge eP joining x to y, is still coloured CQ,.Between the end of the (p+ 1)th stage and the start of the ith stage, the edges coloured up and /I remain the same. At the start of the ith stage we have

We recolour the edge et-1 with a,. Then we have

The subgraph G(x; a,,, fi) contains the vertex y,, which has odd degree in it. Therefore, we can recolour it by Lemma 2.1 and obtain an improved colouring. Course 2f: B3 applied in the (p+ 1)th stage and Bz or B3 in the ith stage. The details of the (p+ 1)th stage are the same as in Course 2e. At the start of the ith stage we have

and the edge eP is still coloured a,,. We recolour the edge eP with /I. Then we have lai- 1(x)1 = I p(x)1 + 1 = Ict,(x)l+2. The subgraph G(x; CQ,,Ui_ 1) contains yi- 1 which has odd degree in it. By Lemma 2.1 we can recolour it and obtain an improved colouring.

195

Edge-colourings of simple graphs

Course 3: None of B1, B2 and B3 apply in the ith stage. Course 3a: At the start of the ith stage,

in this case, if Icri(x)j =0 then yi and ei are not defined. Course 3a(i): l~i(yi-,)l=l~i-~(yi-,)l+l. G( x; Cli, Cli_ i) is not an odd cycle since yi_ 1 has odd degree in it and so G(x; ai, cli- r) may be recoloured give an improved colouring of G. Course 3a(ii): ICri(yi_1)1=(Cri_1(yi_1)1+2.

The subgraph

by Lemma

2.1 to

G/(X; ai, ai_1) contains

x and yi_ i, so it is not in this case an odd cycle with Iai( = IOZ_1(u)l for all but one vertex u. Therefore, by Lemma 2.1, it can be recoloured to give an improved colouring. Course 3a(iii): Icri(yi_,)l=lai_1(yi_l)l (=Ip(yi_l)l). By the choice of Cli, this case does not occur. Course 3b: At the start of the ith stage,

Course 3b(i): IcCi(yi_l)llai_,(yi_l)( (=IB(yi_l)l). Let J be an (Gli,B)-exchange chain starting at yi- 1 with an a,-edge. Let w be the vertex at the other end of J. Course 3b(iil): w=x. Then the final edge of J is coloured Cli. We interchange colours on J. Then

Icri-l(X)I=l~i(x)l+l=I~(x)l+l and either I~(yi-,)l=l~i-~(yi-,)l+l=l~i(yi-,)(+l or

Course 3b(ii2): w # x and w # odd degree in the subgraph G(x; an improved colouring of G. Course 3b(ii3): w =yi_ 1. Then colours on J. We consider two

yi _ 1. We interchange the colours on J. Then yi _ 1 has cci_ r, /I), so we can recolour G(x; cl;- 1, /I) and obtain the final edge of J is coloured tli. We interchange the cases, depending on the original value of ICt(yi_ 1)l -

IB(Yi-111. Course 3b(ii3a): Then we have

At the start of the ith stage, Icri(yi_ 1)1- (B(yi_ 1)l = 2.

196

A.J. W. Hilton, D. de Werra

SinceIcri-,(x)l=IB(x)I+2andIB(yi-1)1=Iai-l(yi-l)l+2,itfollowsfromLemma2.l that, if G(x; C(i_r, fl) is not an odd cycle, then it can be recoloured so that Icr~~X~I~lai-~~x~l+l~l~~X~l+l and

and the colouring is improved, and if G(x; @i-r, /I) is an odd cycle then it can be recoloured so that

and again the colouring is improved. Course 3b(ii3b): At the start ofthe ith stage, lai(yi_,)( -I B(yi- 1)l = 1. Then we have

If G(yi-l; cli, /l) contains x then, since yi-1 has odd degree in this graph, we can recolour it by Lemma 2.1 and obtain an improved colouring. If G(yi_ i; Cli,/I) does not contain x then we can equitably colour it in such a way that we obtain

whilst leaving the colours at x untouched. But then in the graph G(x; ai_l, B) the vertex yi_i has odd degree, so it may be recoloured by Lemma 2.1, and then the colouring of G will be improved. Course 3b(iii): lai(yi-,)l=lai-l(yi_,)I (=IB(yi-l)l). By the choice of tli this case does not occur. Course 3c: At the start of the ith stage,

Course 3c(i): lai(yi-,)l=lai_l(yi_,)1+2

(=Ip(yi_1)1+2). We first recolour the edgeei-i withp.ThenwehaveIcri-1(X)I=ICII(X)I=(B(X)Iandlai(yi_1)l=IB(yi_,)l+1 =lai-l(yi-l)l+3.Thevertexyi_lnowhasodddegreeinthegraphG(yi_l;cri,cri_~), so it is not an odd cycle and so, by Lemma 2.1, it can be recoloured giving an improved colouring of G. Course 3c(ii): ICri(yi_l)l=lCri_l(yi_,)l--2 (=Ij?(yi_1)1-2). We first recolour the edge ei_1 with Ui. Then we have lai(x)l=lai_1(X)I+l=IB(X)l+2 and Ip(yi-1)1= ICri(yi_,)l+l=l”i_1(yi_,)l+l. The vertex yi_1 has odd degree in the subgraph G(x; Cli,8) and so it may be recoloured by Lemma 2.1, yielding an improved colouring of G. Course 3c(iii): lai(yi-,)l=lcri-l(yi-l)l (=Ip(yi-1)[). By the choice of Ui this case does not occur.

of simple graphs

197

(=Ifi(yi_r)l).

This is the bad case Bi,

Course ~c(v): (ai(yi_l)(=lai_l(yi_l)l+l (=IB(yi_i)l+l). exchange chain K starting at yi- 1 (with an edge coloured

Consider the (tli,ai_l)ai) such that one of (A), (B)

Edge-colourings

COURSE3c(iv): ICri(yi_,)(=l~i-l(yi_,)l-l which is excluded from Course 3.

and (C) is true. We consider three subcourses. Course 3c(vA): (A) applies. First interchange

the colours

on K. Then we have

lai-l(Yi-l)l=lai(Yi-l)l+l=IP(Yi-,)l+1. After that replace ai- 1 on ei- 1 by /?. Then we have

I~i-~(~)I=l~i(~)I=IP(~)I,

and

IS(Yi-l)l=lai-1(Yi-l)l+1=lai(Yi-1)I+1, and the colouring is improved. Course 3c(vB). (B) applies. In this case we first interchange we have

the colours

on K. Then

Iai(X)I=Iai-~(X)I+1=IP(X)l+2 and

and the edge ei _ I is coloured ai. Since we have supposed that the bad case B2 does not apply, there is a maximal (ai_ 1, /I)-exchange chain X starting at x which does not end at yi- i. Note that, since X is a maximal (ai_ 1, /I)-exchange chain, and since Ial- 1(x)l = 1/l(x)1 + 1, X cannot end at x. Interchange on X. Then we have

The vertex yi_ 1 now has odd degree in G(x; tli_ 1, ai) and so it can be recoloured by Lemma 2.1 to give an improved colouring of G. Course 3c(vC): (C) applies. In fact, this is the bad case BJ, which is excluded from Course 3. Thus in all cases we obtain an improved colouring. Repeating this process a finite number of times will lead to the required colouring of G. This concludes the proof of Theorem 6.1. Cl Theorems

3.1 and 3.4 can now be proved

fairly easily using Theorem

6.1.

Proof of Theorem 3.1. Suppose that G is given a nearly equitable edge-colouring with k colours; such an edge-colouring exists by Lemma 4.2. Then E(V)< 1 for each DE V(G). Suppose there is a vertex 2 such that a(X)=max isibk ai(ji)=l. Let a and /I be two colours such that a(X)=/?(X)+ 2. Consider G(%; a, 8). If this is not an odd cycle, then,

198

A.J. W. Hilton, D. de Werra

by Lemma 2.1, G(ji-; a, B) can be recoloured

in such a way that the colouring

is

improved, i.e. E’(u)
Proof of Theorem 3.4. First form a graph G’ by introducing a new vertex u’ for each vertex u of the k-core, and joining u’ to u by an edge. If the number of vertices of the k-core is divisible by k, then also add a pendant edge at u’. Then k$d’(u) for each UE V(G’), where d’(u) denotes the degree in the graph G’ of u. By Theorem 1.1, G’ has an equitable edge-colouring. Therefore, G has a k-edge colouring which is equitable at each vertex u not in the k-core, and is nearly equitable at the vertices of the k-core. 0 Now apply Theorem 6.1 to the vertices of the k-core in succession.

7. I-regular colourings The concept of an Z-regular colouring [ 191 is a generalization of that of an equitable edge-colouring, and also of various other types of edge-colouring. Given k (the number of colours we use to colour E(G) with), for each UE V(G) we choose an interval Z(u) of nonnegative integers and require that L d(u)/k J and r d(u)/k 1 are both members of Z(u). The number u(u) is now defined to be the smallest integer in Z(u), and b(u) is the

Edge-colourings of simple graphs

199

largest integer in I(u) if Z(u) is bounded, and otherwise b(u)= co. If the colours are Cl,..., ck, then an I-regular colouring of G is an edge- colouring such that 1Ci(V)1EI(v) for each iE{l, . . . . k} and each UEI’(G). With a(u) and b(u) having this more general definition, an obstruction to an I-regular colouring of G with cl, . . . , ck is a connected subgraph H of G with IE(H)I odd and, for each UEV(H), &(u)E{~~(u), 2b(u)}. With this more general definition of an obstruction, and the more general definitions of a(u) and b(u), we have the following generalization of Theorem 3.1. Theorem 7.1. Let G be a simple graph and let k 2 2. Suppose that in any obstruction (to an I-regular colouring) there is a vertex u such that, for each neighbour y of u lying in an obstruction, ka(y)+l
Remark. Since the edge-colouring in Theorem 7.1 is nearly equitable, we can in fact assume that a(u) >L d(u)/k J- 1 and b(u)<1 d(u)/k 1+ 1 for all UEV(G). At any vertex u for which there is equality in both cases here, any nearly equitable edge-colouring satisfies the I-regular requirement. Therefore, in the proof any initial nearly equitable edge-colouring need only be improved at vertices for which at least one of the inequalities is strict, i.e. at least one of a and b have the usual meaning that ~(~)=Ld(u)/k] and b(u)=rd(u)/kl. Proof of Theorem 7.1. The proof is the same as that given for Theorem 3.1, with a(u), b(u) and obstruction now having the more general meanings. As Theorem 3.1 depends on Theorem 6.1, and so also on Lemmas 4.1-4.3 the new meanings of the word obstruction and of the symbols a(u) and b(u) have to be taken in all of these; this also entails modifying the meaning of the symbols E(U)and a(u), as they are defined in terms of a(u) and b(u). The proofs carry over verbatim. The only place in the proof of Theorem 3.1 where a slight modification is needed is the sentence marked by an (M) in the proof of Theorem 3.1. This should be replaced by: (M’) If G(Z; ~1,/I) is an odd cycle but is not an obstruction, then, since the edge-colouring is nearly equitable, it follows that for some vertex u of G(Z; a, B), either

or

min{b@)l, IB(4I}=44-1.

0

A simpler version of Theorem 7.1 is the following theorem.

200

A.J. W. Hilton, D. de Werra

Theorem 7.2. Let G be a simple graph and let k>2. Suppose that ka(u) + 1
For the next theorem, note that if a(v)=b(u) then Z(u)=(a(u)} Theorem 7.3. Let G be a simple graph and let k>2.

and kid(u).

Let the vertices of G for which

a(u)= b(u) be mutually nonadjacent, and suppose that, zfa(o)# b(u), then ka(v)+ 1
1

for each vertex v of G’, where d’(u) is the degree in G’ of u, a’(u) =

a(u)

i0

if WV(G), if VEV(G’)\V(G),

and b’(o)=

0) b(u)+1 1 co

By Theorem

if UEV(G) and a(o) # b(u), if UEV(G) and a(u)=b(v), if Z,EV(G’)\V(G).

7.2, G’ has an I’-regular

colouring

with k-colours, where I’(u)=

[a’(u), b’(u)] for all LXV(G). This colouring restricted to G is nearly equitable and is I-regular except possibly at the vertices v with a(v) = b(u). We now apply Theorem 6.1 to the vertices u with a(v)=b(u) in succession. 0

A good edge-colouring with k colours is one with the property that, for each UEV(G), if d(u) < k then each colour occurs on at most one edge incident with u, and if d(u) > k then each colour occurs on at least one edge incident with U. Good edge colourings have been studied by Fournier [7] in particular. If we let I(u) = [0, l] when d(u) < k and Z(v)= [l, co] when d(u) 2 k, then an I-regular colouring is a good colouring. In this case, an obstruction to a good colouring is an odd circuit (i.e. a connected regular subgraph of degree 2 with an odd number of edges). In this case, Theorem 7.1 reduces to the following corollary. Corollary 7.4. Let G be a simple graph, and let k> 2. Zf in each odd circuit, there is a vertex v such that, for each neighbour y of v lying on an odd circuit, d(y) # k, then G has a good edge-colouring with k colours. Similarly Theorem following corollary.

7.3 reduces, by redefining I(r) to be {l} if d(u)= k, to the

Edge-colourings of simple graphs

201

Corollary 7.5. Let G be a simple graph and let k > 2. Let the vertices v of G with d(v) = k be mutually nonadjacent. Then G has a good k-colouring with k colours. Remark 7.6. For all the results given in this paper, one could further observe that the

colourings can be equalized in the sense that all colour classes have almost the same number of edges.

Acknowledgment

We would like to thank the referee for reading this so closely, and for his many helpful comments.

References [l] [2] [3] [4] [S] [6] [7] [S] [9] [lo] [11]

[12] [13] [14] [15] [I63 [17] [18] [19]

L.D. Andersen, On edge-colourings of graphs, Math. Stand. 40 (1977) 161-175. L.D. Andersen, Lower bounds on the cover index of a graph, Discrete Math. 25 (1979) 199-210. C. Berge, Graphs and Hypergraphs (North-Holland, Amsterdam, 1973). C. Berge, Note sur les bonnes colorations dun hypergraphe, Cahiers du CERO 15 (1973) 219-223. B. Bollobas and R.K. Guy, Equitable and proportional coloring of trees, J. Combin. Theory Ser. B 34 (1983) 177-186. J.-C. Fournier, Coloration des ardtes dun graphe, Cahiers du CERO 15 (1973) 311-314. J.-C. Fournier, Mithode et theoreme general de coloration des ardtes dun graphe, J. de Math. pures et appliquees 56 (1977) 437-453. M.K. Goldberg, Remark on the chromatic class of a multigraph (in Russian), VyEisl. Mat. i VyEisl. Tehn. (Kharkov) 5 (1974) 128-130. R.P. Gupta, A theorem on the cover index of an s-graph, Notices Amer. Math. Sot. 13 (1966) 714. R.P. Gupta, On decompositions of a multigraph into spanning subgraphs, Bull. Amer. Math. Sot. 80 (1974) 500-502. A. Hajnal and E. Szemertdi, Proof of a conjecture of Erdiis, in: P. Erdiis, A. Renyi and V.T. Sos, eds., Combinatorial Theory and its Applications II, Colloq. Math. Sot. J. Bolyai, Vol. 4 (North-Holland, Amsterdam, 1970) 60-623. S.L. Hakimi and 0. Kariv, A generalization of edge-coloring of graphs, J. Graph Theory 10 (1986) 139-154. A.J.W. Hilton, An improved upper bound for the chromatic index of a multigraph, Ars Combin. 3 (1977) 277-286. A.J.W. Hilton, Colouring the edges of a multigraph so that each vertex has at most j, or at least j, edges of each colour on it, J. London Math. Sot. (2), 12 (1975) 123-128. D.G. Hoffman and C.A. Rodger, Class one graphs, J. Combin. Theory Ser. B 44 (1988) 372-376. Walter Meyer, Equitable coloring, Amer. Math. Monthly 80 (1973) 920-922. V.G. Vizing, On an estimate of the chromatic class of a p-graph (Russian), Diskret. Analiz. 3 (1964) 25-30. D. de Werra, Equitable colorations of graphs, Revue franpaise d’Informatique et de Recherche Operationelle, R-3 (1971) 3-8. D. de Werra, Obstructions for regular colorings, J. Combin. Theory Ser. B 32 (1982) 326-335.