Star Chromatic Index of 1-Planar Graphs

Abstract

Many symmetric properties are well-explored in graph theory, especially in graph coloring, such as symmetric graphs defined by the automorphism groups, symmetric drawing of planar graphs, and symmetric functions which are used to count the number of specific colorings of a graph. This paper is devoted to studying the star edge coloring of 1-planar graphs. The star chromatic index χst′(G) of a graph G is defined as the smallest k for which the edges of G can be colored by using k colors so that no two adjacent edges get the same color and no bichromatic paths or cycles of length four are produced. A graph G is called 1-planar if it can be drawn in the plane such that each edge crosses at most one other edge. In this paper, we prove that every 1-planar graph G satisfies χst′(G)≤7.75Δ+166; and moreover χst′(G)≤⌊1.5Δ⌋+500 if G contains no 4-cycles, and χst′(G)≤2.75Δ+116 if G is 3-connected, or optimal, or NIC-planar.

Keywords

• star edge coloring
• strong edge coloring
• 1-planar graph
• edge-partition