《图论》课程教学资源（书籍文献）A Kaleidoscopic View of Graph Colorings

12 2 Binomial Edge Colorings This brings up the following the following conjecture We saw in Figs.2.3 and 2.4 that there is a k-binomial-colorable graph for k (2,3.4).Much more can be said. Theorem 2.2.2 ([27)).For every integer k 2,there exists a proper k-binomial- colorable graph. 2-binomial-colorable a prope er 3-bin nial-coorabe graph.As eroer (+1)binom e graph fo By the induction hypothesis,there exists a proper k-binomial-colorable graph H for some integer k 3.Let c be a proper k-binomial coloring of H.Express V(H) as v.v2.....v such that the following hold: (l)Forl≤i≤j≤2，degu:≤degv (If degdegand precedes lexicographically,thenij So.for the graph G in Figs.2.3 and 2.4.the vertices of G are labeled as shown in Fg25. Next,we construct a proper (k+1)-binomial-colorable graph G.Let H'be another copy of the graph H where the vertex vi(1 i<2)in H is labeled v in H'and where the proper edge colorings of H and H'are identical.Therefore,for each element S of([k)),exactly two vertices are assigned the color S.one in H and one in H'.Let G be the graph obtained from H and H'by adding 2-1 edges,namely the edgesforwhere the coloris assigned to each of these 2-1 edges. Since no two of these 2-edges are adjacent,this (k+1)-edge coloring 路25Ac ② 3 ② 27 23% 3 13) ①吃

12 2 Binomial Edge Colorings This brings up the following the following conjecture. Conjecture 2.2.1. If G is a k-binomial graph for some integer k  2 that does not contain K2 as a component, then G has a proper binomial coloring using colors from the set Œk. We saw in Figs. 2.3 and 2.4 that there is a k-binomial-colorable graph for k 2 f2; 3; 4g. Much more can be said. Theorem 2.2.2 ([27]). For every integer k  2, there exists a proper k-binomial￾colorable graph. Proof. We proceed by induction on k. We have already seen that there exists a proper 2-binomial-colorable graph and a proper 3-binomial-colorable graph. Assume that there exists a proper k-binomial-colorable graph for some integer k  3. We show that there exists a proper .k C 1/-binomial-colorable graph. By the induction hypothesis, there exists a proper k-binomial-colorable graph H for some integer k  3. Let c be a proper k-binomial coloring of H. Express V.H/ as fv1; v2;:::;v2k g such that the following hold: (1) For 1  i  j  2k, deg vi  deg vj. (2) If deg vi D deg vj and c0 .vi/ precedes c0 .vj/ lexicographically, then i < j. So, for the graph G3 in Figs. 2.3 and 2.4, the vertices of G3 are labeled as shown in Fig. 2.5. Next, we construct a proper .k C 1/-binomial-colorable graph G. Let H0 be another copy of the graph H where the vertex vi (1  i  2k) in H is labeled v0 i in H0 and where the proper edge colorings of H and H0 are identical. Therefore, for each element S of P.Œk/, exactly two vertices are assigned the color S, one in H and one in H0 . Let G be the graph obtained from H and H0 by adding 2k1 edges, namely the edges v2i1v0 2i for 1  i  2k1, where the color kC1 is assigned to each of these 2k1 edges. Since no two of these 2k1 edges are adjacent, this .kC1/-edge coloring Fig. 2.5 A labeled proper 3-binomial-colorable graph ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... .... .................. .. ... ... .............................................. ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... .... .................. .. ... ... .............................................. ... ... ... .... .................. .. ... ... .............................................. ... ... ... .... .................. .. ... ... .............................................. ... ... ... .... .................. .. ... ... .............................................. ... ... ... .... ........ .. .. .. .. .. .......... ... .. ... ... ............................................. ............................. ............................. ........................... .......................... 123 1 1 3 13 0/ v2 v6 2 12 2 3 3 v4 v8 1 2 23 v7 v5 v3 v1

2.2 Proper -Binomial-Colorable Graphs 13 n⊙ ⊙ n⊙ 4 ⊙ 2① ⊙5 ⊙ ⊙5 s② ②5 ② ② ③ ③ ③ ⊙4 s② ⊙5 s② 4 回6 %© ⑧©6 %⊙ 06 n②⑧ ⊙4 ,⑧ 4 因片 ② ②⑧6 @ 因6 Fig.2.6 Illustrating a step of the proof of Theorem 2.2.2 Furthermore,for each element Sof).exactly one vertex of G colored and exactly one vertex is colored S.that is.for each elemen S'of([k+1]),exactly one vertex of G is colored S'.This is illustrated in Fig.2.6 fork =3. The number of vertices of degree r in G for 0 <r <k is therefore the sum of the number (of vertices of degree r-I in H and the number (of vertices of degree r in H.Since ()Θ-月 it follows that G has (vertices of degree r.Therefore,G is a proper (k+1)- binomial-colorable graph.By the Principle of Mathematical Induction.there exists aproper-noml-ora for every integer2

2.2 Proper k-Binomial-Colorable Graphs 13 ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... .. .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... ... .. .. .... .................. .. .. ..... ... ......................................................... ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... ... .. .. .... ................... .. .. ..... ... ........................................................ ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... ... .. .. .... .................. .. .. ..... ... ......................................................... ... ... ... .. .. .. .... .................. .. .. ..... ... ......................................................... ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... .. .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... ... .. .. .... ................... .. .. ..... ... ........................................................ ... ... ... .. .. .. .... ................... .. .. ..... ... ........................................................ ... ... ... ... .. .. .... ................... .. .. ..... ... ........................................................ ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... .............................................................................................................................................................................................. .............................................................................................................................................................................................. .................................................................................................................................................................................................. ................................................................................................................................................................................................. 0/ 1 2 1 2 3 12 12 13 13 23 23 123 123 123 23 23 13 13 12 12 3 v 2 v 3 v 4 v 5 v 6 v 7 4 4 4 4 v1 v2 v3 v4 v5 v6 v7 v8 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v1 v4 v5 v6 v7 v8 v 8 v 1 0/ 0/ v 1 0/ v2 1 1 v3 2 2 3 3 123 Fig. 2.6 Illustrating a step of the proof of Theorem 2.2.2 of G is proper. Furthermore, for each element S of P.Œk/, exactly one vertex of G is colored S and exactly one vertex is colored S [ fk C 1g, that is, for each element S0 of P.Œk C 1/, exactly one vertex of G is colored S0 . This is illustrated in Fig. 2.6 for k D 3. The number of vertices of degree r in G for 0  r  k is therefore the sum of the number  k r1  of vertices of degree r 1 in H and the number k r  of vertices of degree r in H0 . Since k r 1 ! C k r ! D k C 1 r ! ; it follows that G has kC1 r  vertices of degree r. Therefore, G is a proper .k C 1/- binomial-colorable graph. By the Principle of Mathematical Induction, there exists a proper k-binomial-colorable graph for every integer k  2. ut

14 2 Binomial Edge Colorings 2.3 Unrestricted k-Binomial-Colorable Graphs As mentioned in Chap.1,edge colorings of graphs were introduced by Tait when he pamo1o2 a82 planar graphs to generate 4-region coloring of these graphs he firs theoretical paper on graph theory occurred in an 1891 article of Petersen [59].also dealing with regular graphs.Proceeding in this manner,we now consider the concept of binomial colorings as applied to regular graphs.Consequently,these graphs can contain no isolated vertices.In this case,we therefore no longer restrict our attention to proper edge colorings. nonempty graphG(agraph with edges)isa functionc:E(G→S=={L,2. k for ositive integerk ach that olored the same.An unrestricted ede coloringe) n part cular t edges G is a k-binomial coloring of G if the induced vertex coloring c':V(G)(). where c'(v)is the set of colors of the edges incident with v,satisfies the condition {c(u):veV(G}=*(k刚=(-{ AGis atricted k-binomial-colorablegrp (or simplya k-binomial- einterested in,for a fixed integer2.the existence of an r-regular Necessarily.rk and n2-1.These concepts were introduced and studied in [27].We begin with the following result. Theorem 2.3.1 ([271).For each integer k z 2,there exists a k-regular k-binomial colorable graph of order 2. Proof.We show,in fact,for each integer k 2.that the k-regular k-cube G=Op sting V(G=U片-oV.For0≤e≤k,let Ve={v1,,2,Uh} where the ()vertices in each set Ve are listed so that their labels are in reverse lexicographical order.For example,fork=3,it follows that %={0.1}.={11,12,1.3.3={2.1,22,23.V={3,1} where a1=(0,0.0),1.1=(1,0,0).1.2=(0,1,0.1.3=(0,0,1). 21=(1,1,0).2.2=(1,01).23=(0,1,1),31=(1,1,1)

14 2 Binomial Edge Colorings 2.3 Unrestricted k-Binomial-Colorable Graphs As mentioned in Chap. 1, edge colorings of graphs were introduced by Tait when he used proper 3-edge colorings (later called Tait colorings) of 3-regular bridgeless planar graphs to generate 4-region colorings of these graphs. In fact, the first theoretical paper on graph theory occurred in an 1891 article of Petersen [59], also dealing with regular graphs. Proceeding in this manner, we now consider the concept of binomial colorings as applied to regular graphs. Consequently, these graphs can contain no isolated vertices. In this case, we therefore no longer restrict our attention to proper edge colorings. An unrestricted edge coloring of a nonempty graph G (a graph with edges) is a function c W E.G/ ! S D Œk D f1; 2; : : : ; kg for some positive integer k such that no condition is placed on c. In particular, two adjacent edges may or may not be colored the same. An unrestricted edge coloring c W E.G/ ! Œk, k  2, of a graph G is a k-binomial coloring of G if the induced vertex coloring c0 W V.G/ ! P.Œk/, where c0 .v/ is the set of colors of the edges incident with v, satisfies the condition fc0 .v/ W v 2 V.G/g D P.Œk/ D P.Œk/ f;g: A graph G is an unrestricted k-binomial-colorable graph (or simply a k-binomial￾colorable graph) in this case if G has an (unrestricted) k-binomial-coloring. Here, we are interested in, for a fixed integer k  2, the existence of an r-regular k-binomial-colorable graph of order n, where r and/or n is as small as possible. Necessarily, r  k and n  2k 1. These concepts were introduced and studied in [27]. We begin with the following result. Theorem 2.3.1 ([27]). For each integer k  2, there exists a k-regular k-binomial￾colorable graph of order 2k. Proof. We show, in fact, for each integer k  2, that the k-regular k-cube G D Qk of order 2k is a k-binomial-colorable graph. The vertices of G can be labeled by the set of k-bit sequences. For each integer ` with 0  `  k, let V` be the set consisting of the k `  vertices of G whose k-bit labels have exactly ` terms equal to 1. Thus, V.G/ D Sk `D0 V`. For 0  `  k, let V` D n v`;1; v`;2;:::;v`;.k `/ o ; where the k `  vertices in each set V` are listed so that their labels are in reverse lexicographical order. For example, for k D 3, it follows that V0 D fv0;1g; V1 D fv1;1; v1;2; v1;3g; V2 D fv2;1; v2;2; v2;3g; V3 D fv3;1g; where v0;1 D .0; 0; 0/; v1;1 D .1; 0; 0/; v1;2 D .0; 1; 0/; v1;3 D .0; 0; 1/; v2;1 D .1; 1; 0/; v2;2 D .1; 0; 1/; v2;3 D .0; 1; 1/; v3;1 D .1; 1; 1/:

2.3 Unrestricted k-Binomial-Colorable Graphs 15 Since two adjacent inGifand only if the labels in exactly one position,it follows that one of uand belongs to Vi and the other belongs to Vi+for some i(0≤i≤k-l),sayu∈Vi and v∈V+l.So,every term having the value 1 for u also has the value I for v. It remains to show that G has an unrestricted edge coloring c:E(G)[k]such that fc'(v):vE V(G)=(k).First,define c(vo.v1)ifor i=1,2..... =k. Then c(vo.)=[k].Next,define c(e)=ifor each edge e;incident with vi and so c(u)={for1≤i≤k. Assume,for a fixed integer j with 2 s j sk-1 and for all integers i with 2 sis j.that all edges joining a vertex in Vi-and a vertex in Vi have been assigned colors by the coloring cso that(v-l,l≤t≤(，，is the subset of[W in which s ec'(v)if and only if the sth coordinate of v L is 1.Furthermore assume that this is the case forc(ya)as well,where1≤t≤.taking into to the ces in V Next,letx∈andyev+such that xy∈E(G.The lab els ofx and y therefore differ in exactly one coordinate.Let x (xi.x2.....x)and y =(y1.y2.....y&). where then exactly j of the coordinates of x have the value 1,exactly j+I of the coordinates of y have the value I and there is a unique integer r with 1 <r<k such that x,=0 and y,=1.If p is the largest integer,I <p sk.such that p<r and xp =yp 1,then define c(xy)=p.If r 1 or rx 2 and xi =yi =0 for ,then p is the largest integer for which1.The coloring c is illustrated in Fig.2.7 fork 4 where each k-bit (r..)is denoted by 12 ains to show that for each vertex+wherejk-1,the inducec let x E Vj.Thenx (xi.x2.....x)and exactly j of the terms xi.x2.....x are 1. Suppose that these j terms arexm,xm.....x where 1 s m <n2 <...nj.Then the set of colors of the edges joining x with the vertices in V is (m.n2.. 。.n Since the color of any edge joining x and a vertex y =(v. ...v)E Vi is some integer n for which=y =1.it follows that (x)=m.n. Next,let y=01,2)∈+1 and exactly j+I of the terms yi.y2.....y are 1.Suppose that these j+1 terms are y,y ,where1≤m1<m2<…<myti≤k.By the defining property of c,each edge joining y and a vertex in V;is colored with some integer in 5m1,2 We now show that6 w each m wi油1i≤j+1e and a that is colored mi by c.Let x=01,2,ym,m+1-1,,y)

2.3 Unrestricted k-Binomial-Colorable Graphs 15 Since two vertices u and v are adjacent in G if and only if the labels of u and v differ in exactly one position, it follows that one of u and v belongs to Vi and the other belongs to ViC1 for some i (0  i  k 1), say u 2 Vi and v 2 ViC1. So, every term having the value 1 for u also has the value 1 for v. It remains to show that G has an unrestricted edge coloring c W E.G/ ! Œk such that fc0 .v/ W v 2 V.G/g D P.Œk/. First, define c.v0;1v1;i/ D i for i D 1; 2; : : : ; k 1 ! D k: Then c0 .v0;1/ D Œk. Next, define c.ei/ D i for each edge ei incident with v1;i and so c0 .v1;i/ D fig for 1  i  k. Assume, for a fixed integer j with 2  j  k 1 and for all integers i with 2  i  j, that all edges joining a vertex in Vi1 and a vertex in Vi have been assigned colors by the coloring c so that c0 .vi1;t/, 1  t   k i1  , is the subset of Œk in which s 2 c0 .vi1;t/ if and only if the sth coordinate of vi1;t is 1. Furthermore, assume that this is the case for c0 .vj;t/ as well, where 1  t  k j  , taking into consideration only those edges joining vj;t to the vertices in Vj1. Next, let x 2 Vj and y 2 VjC1 such that xy 2 E.G/. The labels of x and y therefore differ in exactly one coordinate. Let x D .x1; x2;:::; xk/ and y D .y1; y2;:::; yk/, where then exactly j of the coordinates of x have the value 1, exactly j C 1 of the coordinates of y have the value 1 and there is a unique integer r with 1  r  k such that xr D 0 and yr D 1. If p is the largest integer, 1  p  k, such that p < r and xp D yp D 1, then define c.xy/ D p. If r D 1 or r  2 and xi D yi D 0 for 1  i  r 1, then p is the largest integer for which xp D yp D 1. The coloring c is illustrated in Fig. 2.7 for k D 4 where each k-bit .x1; x2;:::; xk/ is denoted by x1x2 ::: xk. It remains to show that for each vertex in Vj [ VjC1 where j  k 1, the induced color of the vertex consists of the subscripts of those terms having value 1. First, let x 2 Vj. Then x D .x1; x2;:::; xk/ and exactly j of the terms x1; x2;:::; xk are 1. Suppose that these j terms are xn1 ; xn2 ;:::; xnj where 1  n1 < n2 <  < nj. Then the set of colors of the edges joining x with the vertices in Vj1 is fn1; n2;:::; njg. Since the color of any edge joining x and a vertex y D .y1; y2;:::; yk/ 2 VjC1 is some integer nt for which xnt D ynt D 1, it follows that c0 .x/ D fn1; n2;:::; njg. Next, let y D .y1; y2;:::; yk/ 2 VjC1 and exactly j C 1 of the terms y1; y2;:::; yk are 1. Suppose that these j C 1 terms are ym1 ; ym2 ;:::; ymjC1 , where 1  m1 < m2 <  < mjC1  k. By the defining property of c, each edge joining y and a vertex in Vj is colored with some integer in fm1; m2;:::; mjC1g. We now show that for each mi with 1  i  j C 1, there is an edge joining y and a vertex x 2 Vj that is colored mi by c. Let x D .y1; y2;:::; ymi ;:::; ymiC1 1; : : : ; yk/:

16 2 Binomial Edge Colorings 4=1111 3 31=1110 101 101 4=0111 2 1 3 1010 1001 0110 2.1=1100 01 =1000 0100 010 ,=0001 61=0000 Fig.2.7 Illustrating the coloring c in the proof of Theorem 2.3.1 for k =4 Then x has exactly j terms having value I and so x E Vj.The labels of x and differ in exactly one position,namely the mi+ith position,where+=ym+-1 Since mi is the largest integer such thatxm =y=1.it follows that c(xy)= m.Hence,c'(y)={m1.m2.....m+),taking into consideration only those edges joining y to the vertices in V.Therefore,c is a k-binomial coloring of G and so G is a k-binomial-colorable graph. The following is a consequence of the proof of Theorem 2.3.1. Proof.Let Gbe the graph of order2-1obtained from the graphdescribec in the proof of Theorem 2.3.1 by adding the k/2 edges v-1.v-1+for each odd integer i with 1 s i sk-1.Let c be the coloring of O defined in the proof of Theorem 2.3.1.Note that for each odd integer i with 1 s i sk-1,the sets c'(v-1.)and c'(v-1+1)are both (k-1)-element subsets of the k-element set 因and so le'(v of G by c l≥k-2≥2.Now efine the edgec c(e)if E(O and c"(v -10 For )the sincHeneeinomial colon of Cand so -binomial uced colorable graph

16 2 Binomial Edge Colorings ... ... .................... ... ... .................... ... ... ....... ... ............. ... ..................... ... ... .................... ... ... .................... ... ... .................... ... ... .................... ... ... ........ .... ............. ......... .............. ... ... ..................... ... ........ ............. ... ... .... . ................ ...... ........... ... ... ..................... ... ... ..................... ................................................................................................................... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .................................................................................................................................... ................................................................................................................... .......................................................................................... ................................................................................................................................................................................................................................................................................................. ......................................................................................................................... .................................................................................................................................................................................................................................................................................................... .......... .......................................................................................... ......................................................................................................................................................................................................................................................................................... ... . . . . . ...................................................................................... ............................................................................................................................................................................................................................................................................................. ........................................................................................... .......................................................................................... .... ......................................................................................... ......................................................................................................................................................................................................................................................................................... . ...................................................................................... .. ... ......... .................................................................................................................................................................................................................................................................................................. ........................................................................................................................................................................................................................................................................................... ........................ . ..... ........................................................................................................................................................................................................................................................................... ............................................................................................................................................................................................................................................................................................. ... ... ... ........................................................................................... .................................................................................................................. ........................................................................................................................................ ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .................................................................................................................... .................................................................................................................................................................................................................................................................................................. 3 1010 0101 v1,4 = 0001 1011 v3,4 = 0111 2 1 4 v0,1 = 0000 v4,1 = 1111 v1,1 = 1000 0100 0010 1001 0110 v3,1 = 1110 1101 1 4 2 2 2 3 3 3 2 3 4 1 4 1 1 4 2 2 1 3 1 1 3 3 4 2 4 4 v v 2,6 = 0011 2,1 = 1100 Fig. 2.7 Illustrating the coloring c in the proof of Theorem 2.3.1 for k D 4 Then x has exactly j terms having value 1 and so x 2 Vj. The labels of x and y differ in exactly one position, namely the miC1th position, where xmiC1 D ymiC1 1. Since mi is the largest integer such that xmi D ymi D 1, it follows that c.xy/ D mi. Hence, c0 .y/ D fm1; m2;:::; mjC1g, taking into consideration only those edges joining y to the vertices in Vj. Therefore, c is a k-binomial coloring of G and so G is a k-binomial-colorable graph. ut The following is a consequence of the proof of Theorem 2.3.1. Corollary 2.3.2 ([27]). For each even integer k  4, there exists a k-regular k-binomial-colorable graph of order 2k 1. Proof. Let G be the graph of order 2k1 obtained from the graph Qkvk;1 described in the proof of Theorem 2.3.1 by adding the k=2 edges vk1;ivk1;iC1 for each odd integer i with 1  i  k 1. Let c be the coloring of Qk defined in the proof of Theorem 2.3.1. Note that for each odd integer i with 1  i  k 1, the sets c0 .vk1;i/ and c0 .vk1;iC1/ are both .k 1/-element subsets of the k-element set Œk and so jc0 .vk1;i/ \ c0 .vk1;iC1/j  k 2  2. Now define the edge coloring c of G by c.e/ D c.e/ if e 2 E.Qk vk;1/ and c.vk1;ivk1;iC1/ D si where si 2 c0 .vk1;i/ \ c0 .vk1;iC1/. For each v 2 V.G/, the vertex color of v induced by c is in fact c0 .v/. Hence, c is a k-binomial coloring of G and so G is a k-binomial￾colorable graph. ut