2022/07/17 by Prashant, Athmakoori, Raj, S. Francis
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2207.08168
The class of 2K2-free graphs has been well studied in various contexts in the past. In this paper, we study the chromatic number of \butterfly, hammer\-free graphs, a superclass of 2K2-free graphs and show that a connected \butterfly, hammer\-free graph G with ω(G)≠ 2 admits \binomω+12 as a χ-binding function which is also the best available χ-binding function for its subclass of 2K2-free graphs. In addition, we show that if H∈\C4+Kp, P4+Kp\, then any \butterfly, hammer, H\-free graph G with no components of clique size two admits a linear χ-binding function. Furthermore, we also establish that any connected \butterfly, hammer, H\-free graph G where H∈ \(K1∪ K2)+Kp, 2K1+Kp\, is perfect for ω(G)≥ 2p.