We show that every graph with twin-width $t$ has chromatic number $O(\omega ^{k_t})$ for some integer $k_t$, where $\omega$ denotes the clique number. This extends a quasi-polynomial bound from Pilipczuk and Soko{\l}owski and generalizes a result for bounded clique-width graphs by Bonamy and Pilipczuk. The proof uses the main ideas of the quasi-polynomial approach, with a different treatment of the decomposition tree. In particular, we identify two types of extensions of a class of graphs: the delayed-extension (which preserves polynomial $\chi$-boundedness) and the right-extension (which preserves polynomial $\chi$-boundedness under bounded twin-width condition). Our main result is that every bounded twin-width graph is a delayed extension of simpler classes of graphs, each expressed as a bounded union of right extensions of lower twin-width graphs.


翻译:我们展示了每个双宽为$t$的图的色数为$O(\omega^{k_t})$,其中$k_t$是一个整数,$\omega$表示团数。这扩展了Pilipczuk和Soko{\l}owski的准多项式上界,并将Bonamy和Pilipczuk对有界团宽图的结果推广。证明使用了准多项式方法的主要思想,并使用不同的分解树进行处理。特别的,我们鉴定了一类图的两种扩展方式:延迟扩展(保持多项式$\chi$-有界性质)和右扩展(在有界双宽条件下保证多项式$\chi$-有界性质)。我们的主要结果是每个被界限双宽图都可以被简单图的延迟扩展所替代,每个简单图都表示为较低双宽图的有界右扩展的有界并。

0
下载
关闭预览

相关内容

ACM-CHI会议是第一次人机交互的国际会议。CHI(发音为kai)是一个研究人员和实践者聚集在一起讨论最新互动技术的地方。官网链接:http://chi2019.acm.org/
不可错过!《机器学习100讲》课程,UBC Mark Schmidt讲授
专知会员服务
69+阅读 · 2022年6月28日
中国人工智能的发展现状及未来发展趋势,20页ppt
专知会员服务
126+阅读 · 2022年3月26日
专知会员服务
50+阅读 · 2020年12月14日
专知会员服务
82+阅读 · 2020年12月5日
因果图,Causal Graphs,52页ppt
专知会员服务
238+阅读 · 2020年4月19日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
GNN 新基准!Long Range Graph Benchmark
图与推荐
0+阅读 · 2022年10月18日
图神经网络理论基础 | 谱图理论 Ch1: Introduction
图与推荐
1+阅读 · 2022年8月18日
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
25+阅读 · 2019年5月18日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
14+阅读 · 2019年4月13日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Capsule Networks解析
机器学习研究会
10+阅读 · 2017年11月12日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Arxiv
0+阅读 · 2023年5月12日
Arxiv
0+阅读 · 2023年5月12日
Arxiv
0+阅读 · 2023年5月12日
Hierarchical Graph Capsule Network
Arxiv
20+阅读 · 2020年12月16日
VIP会员
相关VIP内容
不可错过!《机器学习100讲》课程,UBC Mark Schmidt讲授
专知会员服务
69+阅读 · 2022年6月28日
中国人工智能的发展现状及未来发展趋势,20页ppt
专知会员服务
126+阅读 · 2022年3月26日
专知会员服务
50+阅读 · 2020年12月14日
专知会员服务
82+阅读 · 2020年12月5日
因果图,Causal Graphs,52页ppt
专知会员服务
238+阅读 · 2020年4月19日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
相关资讯
GNN 新基准!Long Range Graph Benchmark
图与推荐
0+阅读 · 2022年10月18日
图神经网络理论基础 | 谱图理论 Ch1: Introduction
图与推荐
1+阅读 · 2022年8月18日
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
25+阅读 · 2019年5月18日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
14+阅读 · 2019年4月13日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Capsule Networks解析
机器学习研究会
10+阅读 · 2017年11月12日
相关基金
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Top
微信扫码咨询专知VIP会员