不含某些图作为导出子图的图的色数

摘要

设G是一个图，由Erodos的结果可知其色数X(G)与其团数ω(G)之差可以任意大．因此，一般而言，对图G的色数X(G)来说，不存在用团数ω(G)表示的上界．在本文中，我们主要研究一些F-free图的性质，得到了这些图的色数的上界，此上界是用ω(G)表示的多项式，其中F是某些阶为4或5的图的集合． 本文的第一章介绍了背景和一些基本概念． 在第二章中，我们给出了(2K<,1>+K<,2>)-free图的一些结果．对于(2K<,1>+K<,2>)-free图，Gyárfás已经证明了其色数不能找到一个与团数有关的线性的上界.因此，在第二章中，我们研究了{2K<,1>+K<,2>，G<,5>)-free图和{2K<,1>+K<,2>，C<,4>}-free图.证明了如下结果．令G是一个(2K<,1>+K<,2>)-free图，如果G不含导出5-圈，可得若ω(G)=2，那么x(C)=ω(G)；若ω(G)≥3，那么x(G)≤2ω(G)<'3/2>.由此司以证明，若图G不含导出5-圈和导出kK<,1>+K<,2>，这里k是整数且k≥2，那么x(G)≤2ω<'k-1>平方根ω．接着我们又刻画了{2K<,1>+K<,2>，C<,4>)-free图的结构．如果图G不含与4-圈和2K<,1>+K<,2>同构的导出子图，我们证明了如果α(G)>3，那么G是二个split图；如果α(G)=3，那么对于G的任一个有三个元素的独立集S，G—S是一个弦图或者G—S≌C<,6>VK<,n-9>． 在第二章的最后，我们介绍了图的划分的概念．一个图G=(V,E)是K-划分的，如果我们可以把G的顶点集V划分为k个集合V<,1>，…，V<,k>，使得每一个V<,i>(对i=1，…，k)都不含阶为ω(G)的团．一个图G称为k-可划分的，如果对于G的每一个至少有一条边的导出子图H，H都有一个k-划分.Gravier，Hoàng和Maffray证明了(2K<,1>+K<,2>)-free图是3-可划分的．但我们比较感兴趣的是2-可划分的情况．因此，在本文的第二章中,我们证明了不含导出5-圈的(2K<,1>+K<,2>)-free图是2-可划分的． 对(K<,1>+P<,3>)-free图G，有X(G)≥R(3,ω+1)-1/2，这里R(p，q)是Pamsey函数.第三章中，对(K<,1>+P<,3>)-free图，我们证明了如下结果：如果G是(K<,1>+P<,3>)-free图，并且不含导出4-圈，则有若α(G)≥3，那么X(G)=ω(G)；若α(G)=2，那么X(G)≤2ω(G)．

目录

声明

摘要

1 Introduction

2 On some properties of (2K1 + K2)-free graphs

2.1 On chromatic number of {2K1 +K2,C5}-free graphs

2.2 On chromatic number of {2K1 +K2,C4}-free graphs

2.3 On the divisibility of {2K1 +K2,C5}-free graphs

3 On chromatic number of {K1+P3,C4}-free graphs

References

Contents of finished papers

Acknowledgements