

























A hereditary class $\mathcal{G}$ of graphs is $χ$-bounded if there is a $χ$-binding function, say $f$ such that $χ(G) \leq f(ω(G))$, for every $G \in \cal{G}$, where $χ(G)$ ($ω(G)$) denote the chromatic (clique) number of $G$. It is known that for every $2K_2$-free graph $G$, $χ(G) \leq \binom{ω(G)+1}{2}$, and the class of ($2K_2, 3K_1$)-free graphs does not admit a linear $χ$-binding function. In this paper, we are interested in classes of $2K_2$-free graphs that admit a linear $χ$-binding function. We show that the class of ($2K_2, H$)-free graphs, where $H\in \{K_1+P_4, K_1+C_4, \overline{P_2\cup P_3}, HVN, K_5-e, K_5\}$ admits a linear $χ$-binding function. Also, we show that some superclasses of $2K_2$-free graphs are $χ$-bounded.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。