We show that anagram-free vertex colouring a $2\times n$ square grid requires a number of colours that increases with $n$. This answers an open question in Wilson's thesis and shows that even graphs of pathwidth $2$ do not have anagram-free colourings with a bounded number of colours.


翻译:我们显示,在2美元乘以n$方格的无方格顶点上,无方格的无方格顶点颜色需要一些以美元增加的颜色。 这回答了威尔逊论文中的一个未决问题, 并表明,即使是路径线图2美元, 也没有含有一定数量颜色的无方格颜色。

0
下载
关闭预览

相关内容

专知会员服务
82+阅读 · 2020年12月5日
【DeepMind】强化学习教程,83页ppt
专知会员服务
147+阅读 · 2020年8月7日
神经常微分方程教程,50页ppt,A brief tutorial on Neural ODEs
专知会员服务
70+阅读 · 2020年8月2日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
106+阅读 · 2020年5月15日
Python计算导论,560页pdf,Introduction to Computing Using Python
专知会员服务
69+阅读 · 2020年5月5日
强化学习最新教程,17页pdf
专知会员服务
167+阅读 · 2019年10月11日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
【论文笔记】通俗理解少样本文本分类 (Few-Shot Text Classification) (1)
深度学习自然语言处理
7+阅读 · 2020年4月8日
意识是一种数学模式
CreateAMind
3+阅读 · 2019年6月24日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
IEEE | DSC 2019诚邀稿件 (EI检索)
Call4Papers
10+阅读 · 2019年2月25日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【LeetCode 136】 关关的刷题日记32 Single Number
[DLdigest-8] 每日一道算法
深度学习每日摘要
4+阅读 · 2017年11月2日
Arxiv
0+阅读 · 2021年6月30日
Arxiv
0+阅读 · 2021年6月29日
Arxiv
0+阅读 · 2021年6月29日
Arxiv
0+阅读 · 2021年6月28日
Arxiv
0+阅读 · 2021年6月28日
VIP会员
相关VIP内容
专知会员服务
82+阅读 · 2020年12月5日
【DeepMind】强化学习教程,83页ppt
专知会员服务
147+阅读 · 2020年8月7日
神经常微分方程教程,50页ppt,A brief tutorial on Neural ODEs
专知会员服务
70+阅读 · 2020年8月2日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
106+阅读 · 2020年5月15日
Python计算导论,560页pdf,Introduction to Computing Using Python
专知会员服务
69+阅读 · 2020年5月5日
强化学习最新教程,17页pdf
专知会员服务
167+阅读 · 2019年10月11日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
相关资讯
【论文笔记】通俗理解少样本文本分类 (Few-Shot Text Classification) (1)
深度学习自然语言处理
7+阅读 · 2020年4月8日
意识是一种数学模式
CreateAMind
3+阅读 · 2019年6月24日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
IEEE | DSC 2019诚邀稿件 (EI检索)
Call4Papers
10+阅读 · 2019年2月25日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【LeetCode 136】 关关的刷题日记32 Single Number
[DLdigest-8] 每日一道算法
深度学习每日摘要
4+阅读 · 2017年11月2日
Top
微信扫码咨询专知VIP会员