Linear Chromatic Bounds for a Subfamily of 3K 1-free Graphs

摘要

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 3K 1-free graphs is open. In this paper, we obtain linear χ-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 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.