不含K1＋P3和C4作为导出子图的图的色数

• 作 者: 段芳
• 机 构: 新疆师范大学数学科学学院
• 出 处: 新疆师范大学学报：自然科学版
• 发表日期: 2014年1期
• 关键词: 色数 团数 F-free图 Clique number Chromatic number F-free graph
• 基金项目: 新疆师范大学优秀青年教师科研启动基金资助（XJNU1213）.

Erodos证明了对于一个图G ，χ（G）-ω（G）可以任意大。因此，对一般图而言，其色数不一定能找到一个与团数有关的上界。文章主要研究了一类 F-free图的色数和团数的关系。得到了如果图G是一个不含K 1＋ P3和C4作为导出子图的图，那么当α（G ）≥3时，χ（G ）＝ω（G ）；当α（G ）＝2时，χ（G ）n ≤2ω（G ）。