论文标题
超级类别$ 2K_2 $的$χ$ - 结合功能
$χ$-binding function for a superclass of $2K_2$-free graphs
论文作者
论文摘要
过去，$ 2K_2 $ - 免费图形的班级在过去的各种情况下进行了很好的研究。在本文中，我们研究了$ \ {蝴蝶，锤子\} $的色数 - 免费图形，$ 2k_2 $ - free图的超级类，并表明一个连接的$ \ {butterfly，hammer \} $ - 免费图形$ g $，带有$ω（g）（g）\ neq 2 $ affit $χ$结合功能也是其子类$ 2K_2 $ - FREE图的最佳可用$χ$绑定功能。此外，我们表明，如果$ h \ in \ {c_4+k_p，p_4+k_p \} $，则任何$ \ {蝴蝶，hammer，h \} $ - 免费的Graph $ g $，没有组件的组成部分，尺寸为两个尺寸的组件二，二又有线性$χ$χ$ - 键入的功能。此外，我们还确定了任何连接的$ \ {蝴蝶，锤子，h \} $ - 免费图$ g $其中$ h \ in \ in \ {（k_1 \ cup k_2）+k_p，2k_1+k_p \} $，非常适合$ geq（g）\ geq 2p $。
The class of $2K_2$-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 $2K_2$-free graphs and show that a connected $\{butterfly, hammer\}$-free graph $G$ with $ω(G)\neq 2$ admits $\binom{ω+1}{2}$ as a $χ$-binding function which is also the best available $χ$-binding function for its subclass of $2K_2$-free graphs. In addition, we show that if $H\in\{C_4+K_p, P_4+K_p\}$, 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\in \{(K_1\cup K_2)+K_p, 2K_1+K_p\}$, is perfect for $ω(G)\geq 2p$.
