Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8902829 | Discrete Mathematics | 2018 | 10 Pages |
Abstract
A hereditary class G of graphs is Ï-bounded if there is a Ï-binding function, say f such that Ï(G)â¤f(Ï(G)), for every GâG, where Ï(G) (Ï(G)) denotes the chromatic (clique) number of G. It is known that for every 2K2-free graph G, Ï(G)â¤Ï(G)+12, and the class of (2K2,3K1)-free graphs does not admit a linear Ï-binding function. In this paper, we are interested in classes of 2K2-free graphs that admit a linear Ï-binding function. We show that the class of (2K2,H)-free graphs, where Hâ{K1+P4,K1+C4,P2âªP3¯,HVN,K5âe,K5} admits a linear Ï-binding function. Also, we show that some superclasses of 2K2-free graphs are Ï-bounded.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
T. Karthick, Suchismita Mishra,