首页|一类无奇洞图的色数

一类无奇洞图的色数

扫码查看
给定图G,我们称G中长度至少为4的导出圈为G的洞,长度为奇数或偶数的洞分别被称为是奇洞或偶洞.我们用HVN来表示一个由K4添加一个点并向K4连两条边所得的图,用H表示长为7的圈的补图.Chudnovsky等人在[J.Combin.Theory B,2010,100:313-331]中证明了每一个无奇洞且无K4的图是4-可染的,且其色数为4当且仅当其含有H为导出子图.在本文中,我们将这一结论推广到无奇洞且无HVN的图类上.设G是一个无奇洞且无HVN的图,我们证明了若G含有H为导出子图,则G有一个特殊的割集或者属于两类特殊图,作为推论我们证明了x(G)≤ω(G)+1,且等号成立当且仅当ω(G)=3且G含有H为导出子图,从而完全确定了这类图的色数.
On the Chromatic Number of a Family of odd Hole Free Graphs
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 K4.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,K4)-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 x(G)≤ω(G)+1,and the equality holds if and only if ω(G)=3 and G has H as an induced subgraph.

odd holechromatic numberclique number

宋佳磊、许宝刚

展开 >

南京师范大学数学科学学院 数学研究所 南京 210023

奇洞 色数 团数

2024

数学学报
中国科学院数学与系统科学研究院数学研究所

数学学报

CSTPCD北大核心
影响因子:0.261
ISSN:0583-1431
年,卷(期):2024.67(5)