论文标题
关于适当无冲突的图表的备注
Remarks on proper conflict-free colorings of graphs
论文作者
论文摘要
图形的顶点着色被认为是\ textit {无冲突的}，如果对于每个非分离顶点，则在其（开放的）邻域中完全出现颜色。如[Fabrici等人，\ textIt {相对于邻域而言的无冲突和独特的最大最大色彩的色彩}，Arxiv Preprint]，任何此类正确着色的颜色的最小颜色是PCF $ g $的$ G $的$ G $的$ G $，表示$ c _ {\ MATHRM {PCF}（pcf}（pcf}（pcf}（G）在本文中，我们确定了该图参数的值对几个基本图形类别，包括树，周期，超管和完整图的细分。我们还以$χ_ {\ m athrm {pcf}}（g）$在其他图参数方面给出了上限。特别是，我们表明$χ_ {\ mathrm {pcf}}}（g）\leq5δ（g）/2 $并表征均等性。 PCF $ K $ - 可颜色的几个足够条件以$ 4 \ le K \ le 6 $建立。本文结束了很少的问题。
A vertex coloring of a graph is said to be \textit{conflict-free} with respect to neighborhoods if for every non-isolated vertex there is a color appearing exactly once in its (open) neighborhood. As defined in [Fabrici et al., \textit{Proper Conflict-free and Unique-maximum Colorings of Planar Graphs with Respect to Neighborhoods}, arXiv preprint], the minimum number of colors in any such proper coloring of graph $G$ is the PCF chromatic number of $G$, denoted $χ_{\mathrm{pcf}}(G)$. In this paper, we determine the value of this graph parameter for several basic graph classes including trees, cycles, hypercubes and subdivisions of complete graphs. We also give upper bounds on $χ_{\mathrm{pcf}}(G)$ in terms of other graph parameters. In particular, we show that $χ_{\mathrm{pcf}}(G) \leq5Δ(G)/2$ and characterize equality. Several sufficient conditions for PCF $k$-colorability of graphs are established for $4\le k\le 6$. The paper concludes with few open problems.
