论文标题
均匀的集合，集团分离器，关键图和最佳$χ$结合功能
Homogeneous sets, clique-separators, critical graphs, and optimal $χ$-binding functions
论文作者
论文摘要
给定图表的集合$ \ MATHCAL {H} $，令$ f_ \ Mathcal {h}^\ star \ star \ colon \ colon \ mathbb {n} _ {> 0} \ to \ m athbb {n} _ {> 0} $是最佳的$ -bindy $ umath $ quarts $ - $ f_ \ Mathcal {h}^\ star（ω）= \ max \ {χ（g）：g \ text {is} \ Mathcal {h} \ Mathcal {h} \ text {-free，}ω（g）=ω\} =ω\}。 $ p_5 $ - free Graphs和$（C_5，C_7，\ ldots）$的子类别的$χ$ - 结合功能 - 免费图形。特别是，我们证明了每个$ω\ geq 1 $： （i）$ \ f _ {\ {p_5，banner \}}^\ star（ω）= f_ {3k_1}^\ star（ω）\ inθ（ω^2/\ log（ω）），$ （ii）$ \ f _ {\ {p_5，co-banner \}}}^\ star（ω）= f^\ star _ {\ {2k_2 \}}}}（ω）\ in \ mathcal {o}（O}（O}（O}）（ω^2），$ （iii）$ \ f _ {\ {c_5，c_7，\ ldots，banner \}}}^\ star（ω）= f^\ star _ {\ {c_5,3k_1 \}} （iv）$ \ f _ {\ {p_5，c_4 \}}}^\ star（ω）= \ lceil（5Ω-1）/4 \ rceil.qun 我们还对每个考虑的图形类都表征了所有图形$ g $，均为$χ（g）>χ（g-u）$ in V（g）$中的每个$ u \。从这些结构性结果来看，我们可以证明Reed的猜想 - 与$（P_5，Banner）$ - 免费图形相关的图形数，集团数和最高图。
Given a set $\mathcal{H}$ of graphs, let $f_\mathcal{H}^\star\colon \mathbb{N}_{>0}\to \mathbb{N}_{>0}$ be the optimal $χ$-binding function of the class of $\mathcal{H}$-free graphs, that is, $$f_\mathcal{H}^\star(ω)=\max\{χ(G): G\text{ is } \mathcal{H}\text{-free, } ω(G)=ω\}.$$ In this paper, we combine the two decomposition methods by homogeneous sets and clique-separators in order to determine optimal $χ$-binding functions for subclasses of $P_5$-free graphs and of $(C_5,C_7,\ldots)$-free graphs. In particular, we prove the following for each $ω\geq 1$: (i) $\ f_{\{P_5,banner\}}^\star(ω)=f_{3K_1}^\star(ω)\in Θ(ω^2/\log(ω)),$ (ii) $\ f_{\{P_5,co-banner\}}^\star(ω)=f^\star_{\{2K_2\}}(ω)\in\mathcal{O}(ω^2),$ (iii) $\ f_{\{C_5,C_7,\ldots,banner\}}^\star(ω)=f^\star_{\{C_5,3K_1\}}(ω)\notin \mathcal{O}(ω),$ and (iv) $\ f_{\{P_5,C_4\}}^\star(ω)=\lceil(5ω-1)/4\rceil.$ We also characterise, for each of our considered graph classes, all graphs $G$ with $χ(G)>χ(G-u)$ for each $u\in V(G)$. From these structural results, we can prove Reed's conjecture -- relating chromatic number, clique number, and maximum degree of a graph -- for $(P_5,banner)$-free graphs.
