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]).