2022/02/08 by Mengke Qi, Xin Zhang, Qi, Mengke +1
Computer Science · #05C10 #05C15 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2202.03738
openalex publication_date 2022/02/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An incidence of a graph G is a vertex-edge pair (v,e) such that v is incidence with e. A conflict-free incidence coloring of a graph is a coloring of the incidences in such a way that two incidences (u,e) and (v,f) get distinct colors if and only if they conflict each other, i.e.,(i) u=v, (ii) uv is e or f, or (iii) there is a vertex w such that uw=e and vw=f. The minimum number of colors used among all conflict-free incidence colorings of a graph is the conflict-free incidence chromatic number. A graph is outer-1-planar if it can be drawn in the plane so that vertices are on the outer-boundary and each edge is crossed at most once. In this paper, we show that the conflict-free incidence chromatic number of an outer-1-planar graph with maximum degree Δ is either 2Δ or 2Δ+1 unless the graph is a cycle on three vertices, and moreover, all outer-1-planar graphs with conflict-free incidence chromatic number 2Δ or 2Δ+1 are completely characterized. An efficient algorithm for constructing an optimal conflict-free incidence coloring of a connected outer-1-planar graph is given.