A proper conflict-free coloring of a graph is a proper vertex coloring wherein each non-isolated vertex's open neighborhood contains at least one color appearing exactly once. For a non-negative integer $k$, a graph $G$ is said to be proper conflict-free (degree+$k$)-choosable if given any list assignment $L$ for $G$ where $|L(v)| = d(v) + k$ holds for every vertex $v \in V(G)$, there exists a proper conflict-free coloring $φ$ of $G$ such that $φ(v) \in L(v)$ for all $v \in V(G)$. Recently, Kashima, Škrekovski, and Xu proposed two related conjectures on proper conflict-free choosability: the first asserts the existence of an absolute constant $k$ such that every graph is proper conflict-free (degree+$k$)-choosable, while the second strengthens this claim by restricting to connected graphs other than the cycle of length 5 and reducing the constant to $k=2$. In this paper, we confirm the second conjecture for three graph classes: $K_4$-minor-free graphs with maximum degree at most 4, outer-1-planar graphs with maximum degree at most 4, and planar graphs with girth at least 12; we also confirm the first conjecture for these same graph classes, in addition to all outer-1-planar graphs (without degree constraints). Moreover, we prove that planar graphs with girth at least 12 and outer-1-planar graphs are proper conflict-free $6$-choosable.
翻译:图的无冲突适当着色是一种适当的顶点着色,其中每个非孤立顶点的开邻域内至少有一种颜色恰好出现一次。对于一个非负整数$k$,若给定图$G$的任意列表分配$L$,其中对每个顶点$v \in V(G)$满足$|L(v)| = d(v) + k$,则存在$G$的一个无冲突适当着色$φ$,使得对所有$v \in V(G)$有$φ(v) \in L(v)$,此时称图$G$是无冲突适当(度+$k$)-可选的。最近,Kashima、Škrekovski和Xu提出了两个关于无冲突适当可选性的相关猜想:第一个猜想断言存在一个绝对常数$k$,使得每个图都是无冲突适当(度+$k$)-可选的;第二个猜想通过将范围限制在除长度为5的圈之外的连通图,并将常数减小至$k=2$,从而强化了这一论断。本文中,我们针对三类图类证实了第二个猜想:最大度不超过4的$K_4$-minor-free图、最大度不超过4的外1-平面图,以及围长至少为12的平面图;同时,我们也对相同的图类以及所有外1-平面图(无度约束)证实了第一个猜想。此外,我们证明了围长至少为12的平面图以及外1-平面图都是无冲突适当$6$-可选的。