Ramsey-type problems on induced covers and induced partitions toward the Gyárfás-Sumner conjecture

Abstract

Gyárfás and Sumner independently conjectured that for every tree $T$, there exists a function $f_T:\mathbb{N}\to \mathbb{N}$ such that every $T$-free graph $G$ satisfies $\chi (G)\le f_T(\omega (G))$, where $\chi (G)$ and $\omega (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 $\mathrm{inspc}(G)$} (resp. the {\it induced SP-partition number $\mathrm{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 $\mathrm{inspc}$ and $\mathrm{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.

arXiv comment28 pages, 3 figures