A hole is an induced cycle of length at least 4, and an odd hole is a hole of odd length. A full house is a graph composed by a vertex adjacent to both ends of an edge in $K_4$ . Let $H$ be the complement of a cycle on 7 vertices. Chudnovsky et al [6] proved that every (odd hole, $K_4$)-free graph is 4-colorable and is 3-colorable if it does not has $H$ as an induced subgraph. In this paper, we use the proving technique of Chudnovsky et al to generalize this conclusion to (odd hole, full house)-free graphs, and prove that for (odd hole, full house)-free graph $G$, $\chi(G)\le \omega(G)+1$, and the equality holds if and only if $\omega(G)=3$ and $G$ has $H$ as an induced subgraph.


翻译:圆洞是一个至少有4个长度的诱导循环, 奇怪的洞是一个奇怪的洞。 圆孔是一个由边缘两端的顶点组成的图表, 以K_ 4美元为单位。 让美元作为7个顶点的循环的补充。 Chudnovsky 等人[ 6] 证明, 每一张( 单孔, $_ 4美元) 无色的图都是4色的, 如果没有以H美元作为诱导的子图, 3色是可以的。 在本文中, 我们使用Chudnovsky 等人的验证技术将这一结论概括为( 黑洞, 全房子) 无色的图表, 并证明对于( 单孔, 全房子) 无色的图形 $G$, $\ chi( G)\le\ omega( G)+1 美元, 等等均以美元作为诱导导的子图, 只有当 $( G) 3美元 和$ G$ 以美元为单位时, 平等才能维持 。

0
下载
关闭预览

相关内容

必须收藏!MIT-Gilbert老爷子《矩阵图解》,一张图看透矩阵
因果图,Causal Graphs,52页ppt
专知会员服务
238+阅读 · 2020年4月19日
17篇知识图谱Knowledge Graphs论文 @AAAI2020
专知会员服务
168+阅读 · 2020年2月13日
revelation of MONet
CreateAMind
5+阅读 · 2019年6月8日
深度卷积神经网络中的降采样
极市平台
12+阅读 · 2019年5月24日
Transferring Knowledge across Learning Processes
CreateAMind
26+阅读 · 2019年5月18日
无监督元学习表示学习
CreateAMind
26+阅读 · 2019年1月4日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【 关关的刷题日记47】Leetcode 38. Count and Say
Arxiv
0+阅读 · 2021年12月20日
Arxiv
0+阅读 · 2021年12月20日
Arxiv
0+阅读 · 2021年12月17日
Arxiv
4+阅读 · 2019年2月8日
VIP会员
相关资讯
revelation of MONet
CreateAMind
5+阅读 · 2019年6月8日
深度卷积神经网络中的降采样
极市平台
12+阅读 · 2019年5月24日
Transferring Knowledge across Learning Processes
CreateAMind
26+阅读 · 2019年5月18日
无监督元学习表示学习
CreateAMind
26+阅读 · 2019年1月4日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【 关关的刷题日记47】Leetcode 38. Count and Say
Top
微信扫码咨询专知VIP会员