Chapter 2 Binomial Edge Colorings colorings of interest In one inst nce,the color of a vertex was defined as the set of colors of the edges incident with the vertex,with the goal to minimize the number of colors so that the resulting coloring is vertex-distinguishing.In this chapter,we consider edge colorings that result in the same vertex coloring,but with a different goal in mind.Here,for a fixed number k of edge colors 1.2.....k,we wish to determine graphs of minimum order having the operty that for every subset S of 因=1,2 there is a vertex whose color is S. 2.1 Strong Edge Colorings A vertex coloring of a graph G is vertex-distinguishing if no two vertices of G are assigned the same color.An edge coloring c of a graph G has been referred to as a strong edge coloring of G if c is a proper edge coloring that induces a vertex- ach ve ertex v of G the set of colors of the Such an e vertex-distinguis two vertice of Gare colored the two vertices are assigned t same set.Consequently,for every two vertices of G,there is an edge inci dent witl one of these two vertices whose color is not assigned to any edge incident with the other vertex.The minimum positive integer k for which G has a strong k-edge coloring has been called the strong chromatic index of G,denoted by (G).Since every strong edge coloring of a nonempty graph G is a proper edge coloring of G it follows that A(G)<'(G)<.(G).The concent of s ong edge colorings of ndently Ai et al.[1].Ce et al.[13].Horna s and d Sch The terms strong edge coloring and strong chromatic index were introduced in [,32). ©The Author2016 > P.Zhang,A Kaleid scopic View of Graph Colorings.SpringerBriefs n Mathematics. D0110.1007978-3-319-30518-9_2
Chapter 2 Binomial Edge Colorings In [76], a number of edge colorings were described that gave rise to various vertex colorings of interest. In one instance, the color of a vertex was defined as the set of colors of the edges incident with the vertex, with the goal to minimize the number of colors so that the resulting coloring is vertex-distinguishing. In this chapter, we consider edge colorings that result in the same vertex coloring, but with a different goal in mind. Here, for a fixed number k of edge colors 1; 2; : : : ; k, we wish to determine graphs of minimum order having the property that for every subset S of Œk D f1; 2; : : : ; kg, there is a vertex whose color is S. 2.1 Strong Edge Colorings A vertex coloring of a graph G is vertex-distinguishing if no two vertices of G are assigned the same color. An edge coloring c of a graph G has been referred to as a strong edge coloring of G if c is a proper edge coloring that induces a vertexdistinguishing coloring which assigns to each vertex v of G the set of colors of the edges incident with v. Such an edge coloring is also called vertex-distinguishing. Since no two vertices of G are colored the same, no two vertices are assigned the same set. Consequently, for every two vertices of G, there is an edge incident with one of these two vertices whose color is not assigned to any edge incident with the other vertex. The minimum positive integer k for which G has a strong k-edge coloring has been called the strong chromatic index of G, denoted by 0 s.G/. Since every strong edge coloring of a nonempty graph G is a proper edge coloring of G, it follows that .G/ 0 .G/ 0 s.G/. The concept of strong edge colorings of graphs was introduced independently by Aigner et al. [1], Cerný et al. [ ˇ 13], Hornᡠand Soták [46, 47] and Burris and Schelp [12]. The terms strong edge coloring and strong chromatic index were introduced in [12, 32]. © The Author 2016 P. Zhang, A Kaleidoscopic View of Graph Colorings, SpringerBriefs in Mathematics, DOI 10.1007/978-3-319-30518-9_2 7
8 2 Binomial Edge Colorings 2 04 Fig.2.1 A strong 5-edge coloring of a graph G In order to illustrate this type of edge coloring,we determine the strong chromatic index of the graph G of Fig.2.1.Since '(G)=3,it follows that (G)>3. However,(G)3 since any proper 3-edge coloring of G must assign the color (1.2.3)to every vertex of deg 3.More er,if (G)=3,then since the order of G is 7 the seven ve ed with the sets of (1.2.3 s the seve npt mum degree of G is 8(G)=2.no vertex f G car be coloredr).Furthermore.)4for suppose that there isa strong 4-edge coloring c of G.We may assume that c(vw)=1.Since c is a proper edge coloring.none of the edges uv,i.vx and wx can be colored 1.Hence,two of these four edges must be assigned the same color and the remaining two edges must be assigned different colors,say uv and wx are colored 2.Thus,all of the vertices u.v.w andx are assigned a color that is a 3-element set containing 2.This,however. plies that two of these vertices are colored the same.which is ssible Hence G 5.The of G in Fig.2.1 sho X(G) whe e the.b and a,b.c are denoted by a.ab,abc,respectively,witl a<b<C. The argument used to verify that the strong chromatic index of the graph G o Fig.2.1 is 5 suggests a more general observation.If a graph G has strong chromatic index k,say,then the induced color assigned to a vertex of degree r is one of the r-element subsets of1.2.... Observation 2.1.1.Ifag of degree r(≤r≤A(G) Although A(G)+1 is an upper bound for (G)by Vizing's Theorem,A(G)+ is not an upper bound for (G).as the graph of Fig.2.1 shows.In fact,there is no constant c such that (G)<A(G)+c for every graph G since,for example,if n=()+1,then x(C)≥t+2=A(C)+t by Observation 2.1.1.The following sharp upper bound for the strong chromati index was obtained by Bazgan.Harkat-Benhamdine.Li and Woiniak,verifying a conjecture by Burris and Schelp(see [5))
8 2 Binomial Edge Colorings ... .. ........ .................. ... .. ........ .................. ... .. ........ .................. ... .. ........ .................. ... .. ........ .................. ... .. ........ .................. ... .. ........ .................. ... ... ... .. .. ...... .............. .. .. ... ... ................................................ ... ... ... .. .. ...... ............. .. .. ... ... ................................................ ... ... ... .. .. ...... ............. .. .. ... ... ................................................ ... ... ... .. .... ......... ............ ..... .. ... ... ....................................................... ... ... ... .. .... ........ ............. ..... .. ... ... ....................................................... ... ... ... .. .... ......... ............ ..... ..... ... ...................................................... ... ... ... .. .... ........ ............. ..... .. ... ... ....................................................... ............................. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .............................. ................................ ..................................................................................... ..................................................................................... ......................... .......................... ............................................................................................ ............................................................................... ................................................................................. ..................... .. .. .. .. .. .. .. .. .. .. u x w v z t y G : 1 123 145 13 12 23 3 2 1 1 2 3 5 4 125 134 Fig. 2.1 A strong 5-edge coloring of a graph G In order to illustrate this type of edge coloring, we determine the strong chromatic index of the graph G of Fig. 2.1. Since 0 .G/ D 3, it follows that 0 s.G/ 3. However, 0 s.G/ ¤ 3 since any proper 3-edge coloring of G must assign the color f1; 2; 3g to every vertex of degree 3. Moreover, if 0 s.G/ D 3, then since the order of G is 7 the seven vertices of G would have to be colored with the seven nonempty sets of f1; 2; 3g. Since the minimum degree of G is ı.G/ D 2, no vertex of G can be colored f1g, f2g or f3g. Furthermore, 0 s.G/ ¤ 4, for suppose that there is a strong 4-edge coloring c of G. We may assume that c.vw/ D 1. Since c is a proper edge coloring, none of the edges uv; uw; vx and wx can be colored 1. Hence, two of these four edges must be assigned the same color and the remaining two edges must be assigned different colors, say uv and wx are colored 2. Thus, all of the vertices u; v;w and x are assigned a color that is a 3-element set containing 2. This, however, implies that two of these vertices are colored the same, which is impossible. Hence, 0 s.G/ 5. The strong 5-edge coloring of G in Fig. 2.1 shows that 0 s.G/ D 5. where the sets fag, fa; bg and fa; b; cg are denoted by a, ab, abc, respectively, with a < b < c. The argument used to verify that the strong chromatic index of the graph G of Fig. 2.1 is 5 suggests a more general observation. If a graph G has strong chromatic index k, say, then the induced color assigned to a vertex of degree r is one of the r-element subsets of f1; 2; : : : ; kg. Observation 2.1.1. If a graph G of order at least 3 contains more than k r vertices of degree r .1 r .G// for some positive integer k, then 0 s.G/ k C 1. Although .G/C1 is an upper bound for 0 .G/ by Vizing’s Theorem, .G/C1 is not an upper bound for 0 s.G/, as the graph of Fig. 2.1 shows. In fact, there is no constant c such that 0 s.G/ .G/ C c for every graph G since, for example, if n D `C1 2 C 1, then 0 s.Cn/ ` C 2 D .Cn/ C ` by Observation 2.1.1. The following sharp upper bound for the strong chromatic index was obtained by Bazgan, Harkat-Benhamdine, Li and Wo´zniak, verifying a conjecture by Burris and Schelp (see [5]).
2.Proper k-Binomial-Colorable Graphs 9 Theorem2.l.2.If G is a connected graph of order n≥3，thenx(G≤n+l. This topic has also been discussed in many research papers(see[1,6.12,13.15. 32,46.47,76].for example). 2.2 Proper k-Binomial-Colorable Graphs ≤2 since there are 2*subse thermore.f)ad G has order 2,then Gmust exactly (vertices of degree r for every integer r with 0<r<k.For example,the graph G of order 16=24 in Fig.2.2 has (vertices of degree r for every integerr with 0<r<4.The ner 4-edge color t():vEV(G) g of Gin Fig.2.2 has the property that For an integerk≥2，a oma graph sontaining(vertic of degree r for each integer r with 0r<k.(There is no 1-binomial graph.)Thus such a graph G has order and size -2食- A graph G is a binomial graph if G is a k-binomial graph for some integerk2 These concepts were introduced and studied in [27]. ⊙2 ④ 、3 3© 1 @,⊙ G 1234 ④人4 2 234 3③ 3④ 4 Fig.2.2 A graph of order 16 with strong chromatic index 4
2.2 Proper k-Binomial-Colorable Graphs 9 Theorem 2.1.2. If G is a connected graph of order n 3, then 0 s.G/ n C 1. This topic has also been discussed in many research papers (see [1, 6, 12, 13, 15, 32, 46, 47, 76], for example). 2.2 Proper k-Binomial-Colorable Graphs If G is a graph of order n with strong chromatic index k, then n 2k since there are 2k subsets of Œk. Furthermore, if 0 s.G/ D k and G has order 2k, then G must contain exactly k r vertices of degree r for every integer r with 0 r k. For example, the graph G of order 16 D 24 in Fig. 2.2 has 4 r vertices of degree r for every integer r with 0 r 4. The proper 4-edge coloring of G in Fig. 2.2 has the property that fc0 .v/ W v 2 V.G/g D P.Œ4/ and so 0 s.G/ D 4. For an integer k 2, a k-binomial graph is a graph containing k r vertices of degree r for each integer r with 0 r k. (There is no 1-binomial graph.) Thus, such a graph G has order n D X k rD0 k r ! D 2k and size m D 1 2 X k rD0 r k r ! D k2k2 : A graph G is a binomial graph if G is a k-binomial graph for some integer k 2. These concepts were introduced and studied in [27]. ... ... ... .... .... .............................. ..... ..... .............................................................. ... ... ... .. .. .. .... .................. .. .. .. ... ... ... ... ...................................................... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... ... .. .. .... .................. .. .. .. ... ... ... . ...................................................... ... ... ... .. .... ......... ............. ..... .. ... ... ......................................................... ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... ... .. .. .... .................. .. .. .. ... ... ... ..... ...................................................... ... ... .. ..... ..................... .. .. ... ... ... ....................................................... ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ......................... .......................... .......................... .. .. .. .. .. .. .. .. .. .. .. .. .. ........................... ......................... ........................... ........................... ................................................. ................................................. ................................................... .................................................. 1234 1 2 3 4 1 4 1 3 2 2 1 3 4 4 3 23 34 234 123 134 124 12 2 2 3 13 24 1 4 14 G : 0/ Fig. 2.2 A graph of order 16 with strong chromatic index 4
10 2 Binomial Edge Colorings Fig.2.3 Eight k-binomial graphs for 2.3 人 G2 G6 G a 0 The unique 2-binomial graph Go and the seven 3-binomial graphs G-Gare ial hs Sinc be ue equer graphGis 3.2.2.2.1.1.1.0.its e sub oh of G not c ntaining t 1S0 ed vertex.I If H is a tree.then subdividing each edge of Ki.3 once,(2)subdividing one edge of Ki.3 twice and one edge once and (3)subdividing one edge of K1.3 three times.Thus,there are three such 3-binomial graphs.If H is not a tree,then H must be disconnected where each component contains at least two vertices.Since the maximum size of such a graph having three components is 5.it follows that has exactly two components one of order,say nd the other of order 7-.where 25.Since the size H is 6 and m size of the omponents is (-1)+(6-()=5. t be a tree and the othe a unicyclic graph (and so contain exactly one cycle).Because H has three end-vertices,H does not contain a 5 cycle.If the unicyclic component of H is a 3-cycle,then G is G4.If the unicyclic component of H is not a 3-cycle but contains a 3-cycle,then (a)this component has order 4 or 5,(b)the vertex of degree 3 lies on the 3-cycle in H and (c)the acyclic component of H is either P:or P2.If the acyclic component is P3,then G is Gs: while if the acyclic component is P2,then G is G6.If H has a 4-cycle,then G is G. nial-colo oring of a graph Gisa proper edge coloring c:E(G)→[因={1,2，，k such that the induced vertex coloring c:V(G→9()
10 2 Binomial Edge Colorings Fig. 2.3 Eight k-binomial graphs for k D 2; 3 ... ... .................... ... ... .................... ... ... .................... ... ... .................... ... ... .................... ... ... .................... ... ... .................... ... ... .................... ... ... .................... ... ... ..................... ... ... .................... ... ... .................... ... ... ..................... ... ... .................... ... ... .................... ... ... .................... ... ... .................... ... ... ....... ..... ............. ...... ............... ... ... .................... ... ... .................... ... ... ..................... ... ... ..................... ... ... ..................... ... ... ..................... ... ... .................... ... ... .................... ... ... .................... ... ... ..................... ... ... .................... ... ... ................... ... ... ..................... ... ... .................... ... ... .................... ... ... .................... ... ... .................... ... ... .................... ... ... .................... ... ... .................... ... ... .................... ... ... .................... ... ... .................... ... ... .................... ... ... .................... ... ... ................... ... ... ..................... ... ... .................... ... ... ................... ... ... .................... ... ... .................... ... ... ................... ... ... .................... ... ... .................... ... ... ....... . ............. ... ......... .. .............. ... ....... ............... ... ... ...... . ............. ... ......... .............. ... ... .................... ... ... ..................... .................. .. .. .. .. .. .. .. .. ... .............. .. .. .. .. .. .. ... ................. .. .. .. .. .. .. .. ... ................... .. .. .. .. .. .. .. .. .. ... ................. ................... .................. .. .. .. .. .. .. .. ... ............... .............. .. .. .. .. .. .. ... .. .. .. .. .. ..... ................. ................. G1 G2 G3 G4 G5 G6 : G7 : G0 The unique 2-binomial graph G0 and the seven 3-binomial graphs G1 G7 are shown in Fig. 2.3. Let’s see why G1 G7 are the only 3-binomial graphs. Since the degree sequence of a 3-binomial graph G is 3; 2; 2; 2; 1; 1; 1; 0, its size is 6. Let H be the subgraph of G not containing the isolated vertex. If H is a tree, then H must be obtained by three subdivisions of K1;3. This can be done in three ways: (1) subdividing each edge of K1;3 once, (2) subdividing one edge of K1;3 twice and one edge once and (3) subdividing one edge of K1;3 three times. Thus, there are three such 3-binomial graphs. If H is not a tree, then H must be disconnected where each component contains at least two vertices. Since the maximum size of such a graph having three components is 5, it follows that H has exactly two components, one of order `, say, and the other of order 7 `, where 2 ` 5. Since the size of H is 6 and the minimum size of the two components is .` 1/ C .6 `/ D 5, one component of H must be a tree and the other a unicyclic graph (and so contains exactly one cycle). Because H has three end-vertices, H does not contain a 5- cycle. If the unicyclic component of H is a 3-cycle, then G is G4. If the unicyclic component of H is not a 3-cycle but contains a 3-cycle, then (a) this component has order 4 or 5, (b) the vertex of degree 3 lies on the 3-cycle in H and (c) the acyclic component of H is either P3 or P2. If the acyclic component is P3, then G is G5; while if the acyclic component is P2, then G is G6. If H has a 4-cycle, then G is G7. For an integer k 2, a proper k-binomial-coloring of a graph G is a proper edge coloring c W E.G/ ! Œk D f1; 2; : : : ; kg such that the induced vertex coloring c0 W V.G/ ! P.Œk/;
2.Proper k-Binomial-Colorable Graphs where c(v)is the set of colors of the edges incident with v.is both vertex- distinguishing and satisfies the condition that {c(u):veV(G)}=9( A graph G admitting a proper k-binomial-coloring is a proper k-binomial-colorable kbinoobegaphifGisap Necessarily,proper -binomial-colorable graph is a kbinomial graph pro er k-bin ble fo ble graph.A proprC,ings nom ial-coloring of each of these graphs is shown in Fig.2.4.Since no graph containing K2 as a component can be a proper binomial-colorable graph,the graphs G6 and G7(in Figs.2.3 and 2.4) are not proper binomial-colorable graphs.Furthermore,the graph of Fig.2.2 is a proper 4-binomial-colorable graph.Note that for each integerk>2,in a proper k-binomial-coloring of a k-binomial graph,each color in is assigned to exactly 2-2 edges. ① ⊙ ① ② /2 ⑧ ⊙ 123 @2⊙ 1 Go G: G2: G3: 23 2 2 ⑥ ③ ⊙ (③ O ⊙ o 12 3 @A ① ⊙ G4: Gs: ③ ③ 01@2@ ⑦ O Fig.2.4 Six proper binomial-colorable graphs
2.2 Proper k-Binomial-Colorable Graphs 11 where c0 .v/ is the set of colors of the edges incident with v, is both vertexdistinguishing and satisfies the condition that fc0 .v/ W v 2 V.G/g D P.Œk/: A graph G admitting a proper k-binomial-coloring is a proper k-binomial-colorable graph. Necessarily, a proper k-binomial-colorable graph is a k-binomial graph. A graph G is a proper binomial-colorable graph if G is a proper k-binomialcolorable for some integer k. Each of the graphs G0; G1;:::; G5 in Fig. 2.3 is a proper binomial-colorable graph. A proper 3-binomial-coloring of each of these graphs is shown in Fig. 2.4. Since no graph containing K2 as a component can be a proper binomial-colorable graph, the graphs G6 and G7 (in Figs. 2.3 and 2.4) are not proper binomial-colorable graphs. Furthermore, the graph of Fig. 2.2 is a proper 4-binomial-colorable graph. Note that for each integer k 2, in a proper k-binomial-coloring of a k-binomial graph, each color in Œk is assigned to exactly 2k2 edges. 23 12 13 123 123 13 23 12 12 123 12 23 13 0/ 0/ 0/ 0/ 0/ 13 23 13 12 23 123 / 0 ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... .... ................... .. ... ... .............................................. ... ... ... .... .................... .. ... ... .............................................. ... ... ... .... ................... .. ... ... .............................................. ... ... ... .... .................... .. ... ... .............................................. ... ... ... .... .................... .. ... ... .............................................. ... ... ... .... .................... .. ... ... .............................................. ... ... ... .... .................... .. ... ... .............................................. ... ... ... .... .................... .. ... ... .............................................. ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... .... .................... .. ... ... .............................................. ... ... ... .... .................... .. ... ... .............................................. ... ... ... .... .................... .. ... ... .............................................. ... ... ... .... .................... .. ... ... .............................................. ... ... ... .... ................... .. ... ... .............................................. ... ... ... .... .................... .. ... ... .............................................. ... ... ... .... .................... .. ... ... .............................................. ... ... ... .... .................... .. ... ... .............................................. ... ... ... .... .................... .. ... ... .............................................. ... ... ... .... .................... .. ... ... .............................................. ... ... ... ... .. .. .... ................... .. .. ..... ... ........................................................ ... ... ... .... .................... .. ... ... .............................................. ... ... ... .... ................... .. ... ... .............................................. ... ... ... .... ................... .. ... ... .............................................. ... ... ... .... .................... .. ... ... .............................................. ... ... ... .... ................... .. ... ... .............................................. ... ... ... .. .. ....... ........... .. .. ... ... .............................................. ... ... ... .... .................... .. ... ... .............................................. ... ... ... .. .. ....... ........... .. .. ... ... .............................................. ... ... ... .... .................... .. ... ... .............................................. ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... .... .................... .. ... ... .............................................. ... ... ... .... ................... .. ... ... .............................................. ... ... ... .... .................... .. ... ... .............................................. ... ... ... .... .................... .. ... ... .............................................. ... ... ... .... .................... .. ... ... .............................................. ... ... ... .... .................... .. ... ... .............................................. ... ... ... .... .................... .. ... ... .............................................. ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... .... .................... .. ... ... .............................................. ... ... ... .... .................... .. ... ... .............................................. ... ... ... .. .. ....... ........... .. .. ... ... .............................................. ... ... ... .... ................... .. ... ... .............................................. ... ... ... .... ................... .. ... ... .............................................. .................................. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ......................... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .... ......................... .. .. .. .. .. .. .. .. .. .. ........................ ......................... ...................... ...................... ................... ....................... 3 1 2 3 3 2 2 3 3 1 3 1 2 1 1 1 2 2 1 1 2 2 G0 : G1 : G2 : G3 : 1 2 2 1 2 3 1 3 3 3 3 3 1 2 1 1 2 1 2 2 3 2 2 1 1 3 3 G4 : G5 : 123 12 Fig. 2.4 Six proper binomial-colorable graphs