We give a short proof of a stronger form of the Johansson-Molloy theorem which relies only on the first moment method. The proof adapts a clever counting argument developed by Rosenfeld in the context of non-repetitive colourings. We then extend that result to graphs where each neighbourhood has bounded density, which improves a recent result from Davies et al. Focusing on tightening the number of colours, we obtain the best known upper bound for the chromatic number of triangle-free graphs of maximum degree $\Delta \ge 224$.


翻译:我们简短地证明只依赖第一时刻方法的约翰松-莫洛伊定理的更强的形式。 证据调整了罗森菲尔德在非重复颜色背景下开发的智能计数参数。 然后我们将这一结果扩展至每个邻里有连接密度的图形, 从而改善了戴维斯等人最近的结果。 专注于收紧颜色数量, 我们获得了最著名的无三角图色数上限为$\ Delta\ge 224美元的顶层图。

0
下载
关闭预览

相关内容

【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
已删除
将门创投
4+阅读 · 2017年12月5日
Arxiv
0+阅读 · 2021年11月22日
Arxiv
0+阅读 · 2021年11月20日
Arxiv
0+阅读 · 2021年11月19日
Arxiv
0+阅读 · 2021年11月19日
Arxiv
64+阅读 · 2021年6月18日
Arxiv
3+阅读 · 2018年2月24日
VIP会员
相关VIP内容
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
相关资讯
已删除
将门创投
4+阅读 · 2017年12月5日
相关论文
Top
微信扫码咨询专知VIP会员