Strong edge colorings of graphs

✍ Scribed by Odile Favaron; Hao Li; R.H. Schelp

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 349 KB
• Volume: 159
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(95)00102-3

✦ Synopsis

Let x'(G), called the strong coloring number of G, denote the minimum number of colors for which there is a proper edge coloring of a graph G in which no two of its vertices is incident to edges colored with the same set of colors. It is shown that Z'~(G) ~< Fcn], ½ < c ~ 1, whenever A(G) is appropriately bounded as a function of n, where n is the order of G. This result is in the direction of the conjecture that Z's(G) ~< n + 1 for each graph G with no isolated edges and at most one isolated vertex.

All the graphs G = (V,E) we consider are undirected and simple of order I VI = n with no isolated edges and at most one isolated vertex. Throughout ni will denote the number of vertices in G of degree i. The degree in G of a vertex u is denoted by dG(u) or by d(u) when there is no ambiguity, and the maximum and minimum degrees by A (G) and 6(G) respectively.

For an edge ab, a vertex v in G and an edge coloring F of G, let F(G) be the set of colors, F(ab) the color of ab, and F(v) the set of colors of the edges incident to v.

An edge coloring is proper if each pair of adjacent edges have different colors, vertex distinguishing if F(u) ¢ F(v) for all u ~ v, and stron9 if it is both proper and vertex distinguishing. The stron9 colorin 9 number z~(G) is the minimum number of colors required for a strong edge coloring of the graph G.

In the strong coloring number is introduced and investigated. In these references it is conjectured that if j is the minimum integer such that (~)>/ni