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 vertex￾distinguishing 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