Given a graph $G$ and a list assignment $L(v)$ for each vertex of $v$ of $G$. A proper $L$-list-coloring of $G$ is a function that maps every vertex to a color in $L(v)$ such that no pair of adjacent vertices have the same color. We say that a graph is list $k$-colorable when every vertex $v$ has a list of colors of size at least $k$. A $2$-distance coloring is a coloring where vertices at distance at most 2 cannot share the same color. We prove the existence of a $2$-distance list ($\Delta+2$)-coloring for planar graphs with girth at least $10$ and maximum degree $\Delta\geq 4$.


翻译:以图形 $G$和列表 分配 $L(v)$ 和 列表 $L(v) 分配 $G$ 。 正确的 $L$ 列表颜色 $G$ 是一个函数, 将每个顶点绘制为 $L(v) $ 的颜色, 这样一对相邻的顶点没有相同的颜色。 我们说, 当每个顶点 $v $ 都有至少 $k$ 的颜色列表时, 图表是 $k$ - 彩色 。 一个 $2 $ 远色的颜色是一种颜色, 最远处的顶点的顶点的顶点不能分享同一颜色 。 我们证明有 $2 $( Delta+2 $) 的远点列表, 彩色的平面图至少有 $10 美元, 最高处为$\ Delta\ geq 4 美元 。

0
下载
关闭预览

相关内容

如何撰写一篇好的科研论文?这份22页ppt为你指点一二
专知会员服务
65+阅读 · 2021年7月11日
【CVPR2021】动态度量学习
专知会员服务
40+阅读 · 2021年3月30日
最新《时序分类:深度序列模型》教程,172页ppt
专知会员服务
43+阅读 · 2020年11月11日
【快讯】CVPR2020结果出炉,1470篇上榜, 你的paper中了吗?
【论文笔记】通俗理解少样本文本分类 (Few-Shot Text Classification) (1)
深度学习自然语言处理
7+阅读 · 2020年4月8日
分布式并行架构Ray介绍
CreateAMind
9+阅读 · 2019年8月9日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Faster $p$-Norm Regression Using Sparsity
Arxiv
0+阅读 · 2021年11月19日
Arxiv
0+阅读 · 2021年11月19日
Arxiv
0+阅读 · 2021年11月18日
Sum-of-Squares Lower Bounds for Sparse Independent Set
Arxiv
0+阅读 · 2021年11月17日
Arxiv
0+阅读 · 2021年11月17日
VIP会员
相关资讯
【论文笔记】通俗理解少样本文本分类 (Few-Shot Text Classification) (1)
深度学习自然语言处理
7+阅读 · 2020年4月8日
分布式并行架构Ray介绍
CreateAMind
9+阅读 · 2019年8月9日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员