|
|||||
|
|
| 一类无奇洞图的色数 | |
| 作者姓名： | 宋佳磊 许宝刚 |
| 作者单位： | 南京师范大学数学科学学院数学研究所 |
| 基金项目： | 国家自然科学基金 11931006 |
| 摘 要： | 给定图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为导出子图,从而完全确定了这类图的色数. |
| 关 键 词： | 奇洞 色数 团数 |