Conflict-free Incidence Coloring of Outer-1-planar Graphs  

作　　者：Meng-ke QI Xin ZHANG 

机构地区：[1]School of Mathematics and Statistics,Xidian University,Xi’an 710071,China

出　　处：《Acta Mathematicae Applicatae Sinica》2024年第4期929-942,共14页应用数学学报（英文版）

基　　金：supported by the Research Funds for the Central Universities(No.QTZX22053);the National Natural Science Foundation of China(No.11871055)。

摘　　要：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.

关 键 词：outer-1-planar graph incidence coloring combinatorial algorithm channel assignment problem 

分 类 号：O157.5[理学—数学]