Search

A 1-planar graph is a graph that can be drawn in the Euclidean plane such that each edge crosses at most one edge. An independent crossing (IC)-planar graph is a 1-planar graph satisfying the condition that two pairs of crossing edges have no common end-vertices. It is shown in this paper that every IC-planar graph is 6-choosable. [ABSTRACT FROM AUTHOR]

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]