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

作     者：段芳 

作者单位：新疆大学 

学位级别：硕士

导师姓名：吴宝音都仍

授予年度：2007年

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

主      题：图的着色 F-free图 完美图 划分 

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