Search

An adjacent vertex distinguishing coloring of a graph G is a proper edge coloring of G such that any pair of adjacent vertices admits different sets of colors. The minimum number of colors needed for such a coloring of G is denoted by χ'a(G). In this paper, we show that if G is a planar graph with maximum degree Δ ≥ 16, then Δ ≤ χ'a(G) ≤ Δ + 1, and χ'a(G) = Δ+1 if and only if G contains two adjacent vertices of maximum degree. [ABSTRACT FROM AUTHOR]

A plane graph G is entirely κ-colorable if V (G) ∪ E(G) ∪ F(G) can be colored with κ colors such that any two adjacent or incident elements receive different colors. In 1993, Borodin proved that every plane graph G with maximum degree Δ ≥ 12 is entirely (Δ + 2)-colorable. In this paper, we improve this result by showing that every plane graph G with Δ ≥ 9 is entirely (Δ + 2)-colorable. [ABSTRACT FROM AUTHOR]