List colouring is an influential and classic topic in graph theory. We initiate the study of a natural strengthening of this problem, where instead of one list-colouring, we seek many in parallel. Our explorations have uncovered a potentially rich seam of interesting problems spanning chromatic graph theory. Given a $k$-list-assignment $L$ of a graph $G$, which is the assignment of a list $L(v)$ of $k$ colours to each vertex $v\in V(G)$, we study the existence of $k$ pairwise-disjoint proper colourings of $G$ using colours from these lists. We may refer to this as a \emph{list-packing}. Using a mix of combinatorial and probabilistic methods, we set out some basic upper bounds on the smallest $k$ for which such a list-packing is always guaranteed, in terms of the number of vertices, the degeneracy, the maximum degree, or the (list) chromatic number of $G$. (The reader might already find it interesting that such a minimal $k$ is well defined.) We also pursue a more focused study of the case when $G$ is a bipartite graph. Our results do not yet rule out the tantalising prospect that the minimal $k$ above is not too much larger than the list chromatic number. Our study has taken inspiration from study of the strong chromatic number, and we also explore generalisations of the problem above in the same spirit.


翻译:列表颜色在图形理论中是一个有影响和经典的话题。 我们开始研究这一问题的自然强化问题, 而不是一个列表颜色, 我们在此同时寻找很多。 我们的探索发现了一个可能富饶的、 包括染色图理论在内的有趣的问题。 使用组合式和预测性方法的组合, 我们设置了一些基本上限, 最小的 $K $G$, 即列表包装总是得到保证的 $L (v) $k$ 。 列表为每个 vertex $v\ in V( G) $, 我们用这些列表中的颜色来研究是否存在美元对调合合的美元正配色。 使用这些颜色, 我们可能会将此称为 \ emph{ list- 包装} 。 使用组合式和 robabableical 的混合方法, 我们为最小的 $( $) 美元( $ ) 设置了某些基本上限的上限, 而在我们研究中, 最起码的金额( list) $( nucial) excial) excial extial exis a excial excial excial exmission (我们研究中, 我们的最小的 extiquest legre extiquest le legent le) a le a legent legent) a ex legental ex ex ex ex ex ex ex ex ex ex ex ex.

0
下载
关闭预览

相关内容

专知会员服务
28+阅读 · 2020年11月4日
【NeurIPS 2020】对比学习全局和局部医学图像分割特征
专知会员服务
43+阅读 · 2020年10月20日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
【NeurIPS 2019的主要趋势】Key trends from NeurIPS 2019
专知会员服务
11+阅读 · 2019年12月19日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
学术会议 | 知识图谱顶会 ISWC 征稿:Poster/Demo
开放知识图谱
5+阅读 · 2019年4月16日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【推荐】深度学习目标检测概览
机器学习研究会
10+阅读 · 2017年9月1日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Arxiv
10+阅读 · 2021年11月3日
Arxiv
3+阅读 · 2021年11月1日
Arxiv
14+阅读 · 2021年3月10日
Arxiv
14+阅读 · 2020年12月17日
Arxiv
3+阅读 · 2018年2月24日
VIP会员
相关VIP内容
相关资讯
学术会议 | 知识图谱顶会 ISWC 征稿:Poster/Demo
开放知识图谱
5+阅读 · 2019年4月16日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【推荐】深度学习目标检测概览
机器学习研究会
10+阅读 · 2017年9月1日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Top
微信扫码咨询专知VIP会员