





















The chromatic profile of a digraph $H$, denoted by $δ_χ^{+}(H,k)$, is the infimum $d$ such that any $H$-free digraph $D$ on $n$ vertices with minimum out-degree $δ^{+}(D) \ge dn$ must be $k$-colorable. We determine the exact chromatic profile for several fundamental classes of digraphs. Our main result is a directed analogue of the Andrásfai-Erdős-Sós theorem, stating that $δ_χ^{+}(T_r, r-1)=\frac{3 r-7}{3 r-4}$, where $T_r$ is the transitive tournament on $r$ vertices. We then determine the chromatic profile for directed odd cycles, showing that $δ^+_χ(\overrightarrow{C}_{2\ell+1},2)=1/2$ for all $\ell\ge 1$. Finally, we resolve the profile for the three remaining orientations of the pentagon, establishing that $δ_χ^{+}(C_{5}',2)=δ_χ^{+}(C_{5}'',2)=δ_χ^{+}(C_{5}''',2)=1/3$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。