论文标题
稀疏图的适当无冲突着色
Proper conflict-free coloring of sparse graphs
论文作者
论文摘要
图形的{\ IT适当的无冲突$ c $ - 颜色}是适当的$ c $ - 颜色，因此每个非分离顶点的颜色都完全出现在其附近。该概念是由Fabrici等人正式引入的，Fabrici等人证明了平面图具有适当的无冲突8色，并构建了一个没有适当无冲突的5色的平面图。 Caro，Petruševski和škrekovski进一步研究了这种着色概念，特别是在最高平均程度上研究了上限，以保证适用的无冲突$ C $ -C $颜色$ C \ in \ in \ in \ {4,5,6 \} $。 沿着这些线路，我们完全确定图$ g $的最大平均度（表示为$ mad（g）$）的阈值，该阈值保证了所有$ c $的适当无冲突$ c $ - 颜色，还提供了紧密的示例。也就是说，对于$ c \ geq 5 $，我们证明$ gaid（g）\ leq \ frac {4c} {c+2} $具有适当的无冲突$ c $ -ocoloring，除非$ g $包含$ 1 $ -1 $ -Cubdivision $ c+1 $ Vertices。当$ c = 4 $时，我们表明$ g $带有$ mad（g）<\ frac {12} {5} $具有适当的无冲突$ 4 $ - 颜色，除非$ g $包含诱导的$ 5 $ cycle。此外，我们还表明，带有腰围至少5个的平面图具有适当的无冲突$ 7 $颜色。
A {\it proper conflict-free $c$-coloring} of a graph is a proper $c$-coloring such that each non-isolated vertex has a color appearing exactly once on its neighborhood. This notion was formally introduced by Fabrici et al., who proved that planar graphs have a proper conflict-free 8-coloring and constructed a planar graph with no proper conflict-free 5-coloring. Caro, Petruševski, and Škrekovski investigated this coloring concept further, and in particular studied upper bounds on the maximum average degree that guarantees a proper conflict-free $c$-coloring for $c\in\{4,5,6\}$. Along these lines, we completely determine the threshold on the maximum average degree of a graph $G$, denoted $mad(G)$, that guarantees a proper conflict-free $c$-coloring for all $c$ and also provide tightness examples. Namely, for $c\geq 5$ we prove that a graph $G$ with $mad(G)\leq \frac{4c}{c+2}$ has a proper conflict-free $c$-coloring, unless $G$ contains a $1$-subdivision of the complete graph on $c+1$ vertices. When $c=4$, we show that a graph $G$ with $mad(G)<\frac{12}{5}$ has a proper conflict-free $4$-coloring, unless $G$ contains an induced $5$-cycle. In addition, we show that a planar graph with girth at least 5 has a proper conflict-free $7$-coloring.
