2017/02/02 by Karthick, T., Mishra, Suchismita
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1702.00622
A hereditary class G of graphs is χ-bounded if there is a χ-binding function, say f such that χ(G) ≤ f(ω(G)), for every G ∈ \calG, where χ(G) (ω(G)) denote the chromatic (clique) number of G. It is known that for every 2K2-free graph G, χ(G) ≤ \binomω(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.