论文标题
Ramsey型问题在诱发的覆盖物和诱导分区朝向Gyárfás-Sumner猜想
Ramsey-type problems on induced covers and induced partitions toward the Gyárfás-Sumner conjecture
论文作者
论文摘要
Gyárfás和Sumner独立地指出，对于每棵树$ t $，都存在$ f_ {t}：\ mathbb {n} \ rightarrow \ rightArrow \ Mathbb {n} $，以便每个$ t $ t $ - free Graph $ g $ g $满足$ c $ c $ c.（g）（g） $ω（g）$分别为{\ it色号}和$ g $的{\ it clique number}。这个猜想给出了色度编号上拉姆齐型问题的解决方案。 对于图$ g $，{\ IT诱导的Sp-cover number $ {\ rm Indc}（g）$}（resp。 $ \ MATHCAL {p} $是星形或路径，$ \ bigCup _ {p \ in \ Mathcal {p}}} v（p）= v（g）$（resscal {p} p \ in \ mathcal {p}} v（p} v（p）v（p）这样的两个不变性与色数直接相关的概念。从这个事实的角度来看，我们将重点放在两个不变的$ {\ rm indc} $和$ {\ rm inspp} $的Ramsey型问题上，它们是Gyárfás-Sumner Condoxenture的类比，并解决了。作为我们的结果的推论，我们还解决了广泛研究的不变式的其他拉姆齐型问题。
Gyárfás and Sumner independently conjectured that for every tree $T$, there exists a function $f_{T}:\mathbb{N}\rightarrow \mathbb{N}$ such that every $T$-free graph $G$ satisfies $χ(G)\leq f_{T}(ω(G))$, where $χ(G)$ and $ω(G)$ are the {\it chromatic number} and the {\it clique number} of $G$, respectively. This conjecture gives a solution of a Ramsey-type problem on the chromatic number. For a graph $G$, the {\it induced SP-cover number ${\rm inspc}(G)$} (resp. the {\it induced SP-partition number ${\rm inspp}(G)$}) of $G$ is the minimum cardinality of a family $\mathcal{P}$ of induced subgraphs of $G$ such that each element of $\mathcal{P}$ is a star or a path and $\bigcup _{P\in \mathcal{P}}V(P)=V(G)$ (resp. $\dot\bigcup _{P\in \mathcal{P}}V(P)=V(G)$). Such two invariants are directly related concepts to the chromatic number. From the viewpoint of this fact, we focus on Ramsey-type problems for two invariants ${\rm inspc}$ and ${\rm inspp}$, which are analogies of the Gyárfás-Sumner conjecture, and settle them. As a corollary of our results, we also settle other Ramsey-type problems for widely studied invariants.
