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$-可选的。

0
下载
关闭预览

相关内容

专知会员服务
16+阅读 · 2021年10月4日
专知会员服务
25+阅读 · 2021年7月31日
专知会员服务
50+阅读 · 2021年6月2日
图节点嵌入(Node Embeddings)概述,9页pdf
专知
15+阅读 · 2020年8月22日
NAACL 2019 | 一种考虑缓和KL消失的简单VAE训练方法
PaperWeekly
20+阅读 · 2019年4月24日
条件概率和贝叶斯公式 - 图解概率 03
遇见数学
10+阅读 · 2018年6月5日
CNN 反向传播算法推导
统计学习与视觉计算组
30+阅读 · 2017年12月29日
基于LDA的主题模型实践(一)
机器学习深度学习实战原创交流
20+阅读 · 2015年9月9日
国家自然科学基金
0+阅读 · 2017年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
Arxiv
0+阅读 · 12月27日
VIP会员
相关VIP内容
专知会员服务
16+阅读 · 2021年10月4日
专知会员服务
25+阅读 · 2021年7月31日
专知会员服务
50+阅读 · 2021年6月2日
相关资讯
图节点嵌入(Node Embeddings)概述,9页pdf
专知
15+阅读 · 2020年8月22日
NAACL 2019 | 一种考虑缓和KL消失的简单VAE训练方法
PaperWeekly
20+阅读 · 2019年4月24日
条件概率和贝叶斯公式 - 图解概率 03
遇见数学
10+阅读 · 2018年6月5日
CNN 反向传播算法推导
统计学习与视觉计算组
30+阅读 · 2017年12月29日
基于LDA的主题模型实践(一)
机器学习深度学习实战原创交流
20+阅读 · 2015年9月9日
相关基金
国家自然科学基金
0+阅读 · 2017年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
Top
微信扫码咨询专知VIP会员