华东师范大学学报(自然科学版) ›› 2014, Vol. 2014 ›› Issue (1): 9-12.

• 应用数学与基础数学 • 上一篇    下一篇

不含 2K1+K2 和 C4 作为导出子图的图的色数

段 芳, 张维娟   

  1. 新疆师范大学~~数学科学学院,\; 乌鲁木齐\; 830054
  • 收稿日期:2013-04-01 修回日期:2013-07-01 出版日期:2014-01-25 发布日期:2015-09-25

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

DUAN Fang,  ZHANG Wei-juan   

  1. School of Mathematical Sciences, Xinjiang Normal University,\; Urumqi 830054, China
  • Received:2013-04-01 Revised:2013-07-01 Online:2014-01-25 Published:2015-09-25

PDF

2123

摘要： 设图 G 不含与 2K1+K2 同构的导出子图, 并且不含导出4-圈, 通过对该图类独立数的讨论, 刻画出它的结构,
从而得到该图类色数与团数有关的线性的上界.

关键词: 色数, 团数, F-free 图

Abstract: In this paper, the structural characterization of { 2K1+K2 , C4 }-free graphs was given according to their
independence numbers, and the linear upper bound on chromatic number of { 2K1+K2 , C4 }-free graphs was obtained in terms of their
clique number.

Key words: chromatic number, clique number, F-free graph

中图分类号: