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$ 以美元为单位时, 平等才能维持 。