Search

For an arbitrary class of graphs $$\mathcal{G}$$ , there may not exist a function f such that $$\chi(G) \leq f(\omega(G))$$ , for every $$G \in \mathcal{G}$$ . When such a function exists, it is called a χ-binding function for $$\mathcal{G}$$ . The problem of finding an optimal χ-binding function for the class of 3 K 1-free graphs is open. In this paper, we obtain linear χ-binding function for the class of {3 K 1, H}-free graphs, where H is one of the following graphs: $$K_1 + C_4, (K_3 \cup K_1)+K_1, K_1 + P_4, K_4 \cup K_1$$ , House graph and Kite graph. We first describe structures of these graphs and then derive χ-binding functions. [ABSTRACT FROM AUTHOR]