Linear Chromatic Bounds for a Subfamily of 3K1-free Graphs

For an arbitrary class of graphs g, there may not exist a function f such that chi(G) <= f (omega(G)), for every G epsilon g. When such a function exists, it is called a. chi-binding function for g. The problem of finding an optimal chi-binding function for the class of 3K(1)-free graphs is open. In this paper, we obtain linear chi-binding function for the class of {3K(1), H}free graphs, where H is one of the following graphs: K-1 + C-4, (K-3 boolean OR K-1) + K-1, K-1 + P-4, K-4 boolean OR K-1, House graph and Kite graph. We first describe structures of these graphs and then derive chi-binding functions.