4.3 Article

Chromatic bounds for some classes of 2K2-free graphs

期刊

DISCRETE MATHEMATICS
卷 341, 期 11, 页码 3079-3088

出版社

ELSEVIER
DOI: 10.1016/j.disc.2018.07.018

关键词

Chromatic number; Clique number; Graph classes; 2K(2)-free graphs

向作者/读者索取更多资源

A hereditary class g of graphs is chi-bounded if there is a chi-binding function, say f such that chi(G) <= f (omega(G)), for every G is an element of g, where x (G) (omega(G)) denotes the chromatic (clique) number of G. It is known that for every 2K(2)-free graph G, chi(G) <= ((omega(G)+1)(2)), and the class of (2K(2), 3K(1))-free graphs does not admit a linear chi-binding function. In this paper, we are interested in classes of 2K(2)-free graphs that admit a linear chi-binding function. We show that the class of (2K(2), H)-free graphs, where H is an element of {K-1 + P-4, K-1 + C-4, (P2 boolean OR P3) over bar, HVN, K-5 - e, K-5} admits a linear chi-binding function. Also, we show that some superclasses of 2K(2)-free graphs are chi-bounded. (C) 2018 Elsevier B.V. All rights reserved.

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

4.3
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

暂无数据
暂无数据