Search

Abstract: Let be a proper edge coloring of a graph . The set of colors of edges incident to a vertex is called the color set of and denoted by . The coloring is vertex-distinguishing if for any two distinct vertices . A -strong edge coloring of a graph is a proper edge coloring that distinguishes any two distinct vertices and with distance . The minimum number of colors of a -strong edge coloring of graph is called -strong chromatic index of and denoted by . We present some general results on -strong edge colorings of circulant graphs. We determine exact values of the -strong chromatic index for circulant graphs for and , we also prove that the difference between the -strong chromatic index and its trivial lower bound can be arbitrarily large. [Copyright &y& Elsevier]

A cyclic coloring of a plane graph G is a coloring of its vertices such that vertices incident with the same face have distinct colors. The minimum number of colors in a cyclic coloring of a plane graph G is its cyclic chromatic number χ c (G). Let Δ ∗ (G) be the maximum face degree of a graph G. In this note we show that to prove the Cyclic Coloring Conjecture of Borodin from 1984, saying that every connected plane graph G has χ c (G) ≤ ⌊ 3 2 Δ ∗ (G) ⌋ , it is enough to do it for subdivisions of simple 3-connected plane graphs. We have discovered four new different upper bounds on χ c (G) for graphs G from this restricted family; three bounds of them are tight. As corollaries, we have shown that the conjecture holds for subdivisions of plane triangulations, simple 3-connected plane quadrangulations, and simple 3-connected plane pentagulations with an even maximum face degree, for regular subdivisions of simple 3-connected plane graphs of maximum degree at least 10, and for subdivisions of simple 3-connected plane graphs having the maximum face degree large enough in comparison with the number of vertices of their longest paths consisting only of vertices of degree two. [ABSTRACT FROM AUTHOR]