A graph class is $\chi$-bounded if the only way to force large chromatic number in graphs from the class is by forming a large clique. In the 1970s, Erd\H{o}s conjectured that intersection graphs of straight-line segments in the plane are $\chi$-bounded, but this was disproved by Pawlik et al. (2014), who showed another way to force large chromatic number in this class -- by triangle-free graphs $B_k$ with $\chi(B_k)=k$ constructed by Burling (1965). This also disproved the celebrated conjecture of Scott (1997) that classes of graphs excluding induced subdivisions of a fixed graph are $\chi$-bounded. We prove that in broad classes of graphs excluding induced subdivisions of a fixed graph, including the increasingly more general classes of segment intersection graphs, string graphs, region intersection graphs, and hereditary classes of graphs with finite asymptotic dimension, large chromatic number can be forced only by large cliques or large graphs $B_k$. One corollary is that the hereditary closure of $\{B_k\colon k\geq 1\}$ forms a minimal hereditary graph class with unbounded chromatic number -- the second known graph class with this property after the class of complete graphs. Another corollary is that the decision variant of approximate coloring in the aforementioned graph classes can be solved in polynomial time by exhaustively searching for a sufficiently large clique or copy of $B_k$. We also discuss how our results along with some results of Chudnovsky, Scott, and Seymour on the existence of colorings can be turned into polynomial-time algorithms for the search variant of approximate coloring in string graphs (with intersection model in the input) and other aforementioned graph classes. Such an algorithm has not yet been known for any graph class that is not $\chi$-bounded.


翻译:暂无翻译

0
下载
关闭预览

相关内容

【2022新书】数据科学的实用线性代数,328页pdf
专知会员服务
138+阅读 · 2022年9月17日
专知会员服务
16+阅读 · 2021年10月4日
【ICML2021】具有线性复杂度的Transformer的相对位置编码
专知会员服务
25+阅读 · 2021年5月20日
【ACL2020】多模态信息抽取,365页ppt
专知会员服务
150+阅读 · 2020年7月6日
强化学习最新教程,17页pdf
专知会员服务
182+阅读 · 2019年10月11日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
41+阅读 · 2019年10月9日
图节点嵌入(Node Embeddings)概述,9页pdf
专知
15+阅读 · 2020年8月22日
【NeurIPS2019】图变换网络:Graph Transformer Network
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
一文概览用于图像分割的CNN
论智
14+阅读 · 2018年10月30日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
条件概率和贝叶斯公式 - 图解概率 03
遇见数学
10+阅读 · 2018年6月5日
CNN 反向传播算法推导
统计学习与视觉计算组
30+阅读 · 2017年12月29日
Layer Normalization原理及其TensorFlow实现
深度学习每日摘要
32+阅读 · 2017年6月17日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
6+阅读 · 2014年12月31日
Arxiv
0+阅读 · 10月22日
VIP会员
相关资讯
图节点嵌入(Node Embeddings)概述,9页pdf
专知
15+阅读 · 2020年8月22日
【NeurIPS2019】图变换网络:Graph Transformer Network
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
一文概览用于图像分割的CNN
论智
14+阅读 · 2018年10月30日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
条件概率和贝叶斯公式 - 图解概率 03
遇见数学
10+阅读 · 2018年6月5日
CNN 反向传播算法推导
统计学习与视觉计算组
30+阅读 · 2017年12月29日
Layer Normalization原理及其TensorFlow实现
深度学习每日摘要
32+阅读 · 2017年6月17日
相关基金
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
6+阅读 · 2014年12月31日
Top
微信扫码咨询专知VIP会员