一类无奇洞图的色数

作     者：宋佳磊 许宝刚 

作者机构：南京师范大学数学科学学院数学研究所 

出 版 物：《数学学报(中文版)》 (Acta Mathematica Sinica(Chinese Series))

年 卷 期：2024年第05期

页      面：830-842页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

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

主　　题：奇洞 色数 团数 

摘      要：给定图G,我们称G中长度至少为4的导出圈为G的洞,长度为奇数或偶数的洞分别被称为是奇洞或偶洞.我们用HVN来表示一个由K4添加一个点并向K4连两条边所得的图,用H表示长为7的圈的补图.Chudnovsky等人在[*** B,2010,100:313-331]中证明了每一个无奇洞且无K4的图是4-可染的,且其色数为4当且仅当其含有H为导出子图.在本文中,我们将这一结论推广到无奇洞且无HVN的图类上.设G是一个无奇洞且无HVN的图,我们证明了若G含有H为导出子图,则G有一个特殊的割集或者属于两类特殊图,作为推论我们证明了X（G）≤ω（G）+1,且等号成立当且仅当ω（G）=3且G含有H为导出子图,从而完全确定了这类图的色数.