一类无奇洞图的色数  

On the Chromatic Number of a Family of odd Hole Free Graphs

作　　者：宋佳磊 许宝刚 Jia Lei SONG;Bao Gang XU(Institute of Mathematics,School of Mathematical Sciences,Nanjing Normal University,Nanjing 210023,P.R.China)

机构地区：[1]南京师范大学数学科学学院数学研究所,南京210023

出　　处：《数学学报（中文版）》2024年第5期830-842,共13页Acta Mathematica Sinica：Chinese Series

基　　金：国家自然科学基金(11931006)。

摘　　要：给定图G,我们称G中长度至少为4的导出圈为G的洞,长度为奇数或偶数的洞分别被称为是奇洞或偶洞.我们用HVN来表示一个由K_(4)添加一个点并向K_(4)连两条边所得的图,用H表示长为7的圈的补图.Chudnovsky等人在[J.Combin.Theory B,2010,100:313-331]中证明了每一个无奇洞且无K_(4)的图是4-可染的,且其色数为4当且仅当其含有H为导出子图.在本文中,我们将这一结论推广到无奇洞且无HVN的图类上.设G是一个无奇洞且无HVN的图,我们证明了若G含有H为导出子图,则G有一个特殊的割集或者属于两类特殊图,作为推论我们证明了X(G)≤ω(G)+1,且等号成立当且仅当ω(G)=3且G含有H为导出子图,从而完全确定了这类图的色数.A hole is an induced cycle of length at least 4,a hole of odd length(resp.even length)is called an odd hole(resp.even hole).An HVN 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.in[J.Combin.Theory B,2010,100:313-331]proved that every(odd hole,K_(4))-free graph is 4-colorable and is 3-colorable if it does not contain H as an induced subgraph.In this paper,we use the idea and proving technique of Chudnovsky et al.to generalize this conclusion to(odd hole,HVN)-free graphs.Let G be an(odd hole,HVN)-free graph.We prove that if G contains H as an induced subgraph,then it either has a special cutset or is in two classes of pre-defined graphs.As its corollary,we show thatχ(G)≤ω(G)+1,and the equality holds if and only ifω(G)=3 and G has H as an induced subgraph.

关 键 词：奇洞 色数 团数 

分 类 号：O157.5[理学—数学]