Ramsey-type problems on induced covers and induced partitions toward the Gy\'{a}rf\'{a}s-Sumner conjecture

arXiv2205.14466MaRDI QIDQ6505972FDOQ6505972

Authors: Shuya Chiba, Michitaka Furuya 

Abstract: Gy'{a}rf'{a}s and Sumner independently conjectured that for every tree $T$, there exists a function $f_T:mathbbNightarrowmathbbN$ such that every $T$-free graph $G$ satisfies $chi(G)leq{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 $minspc(G)$} (resp. the {it induced SP-partition number $minspp(G)$}) of $G$ is the minimum cardinality of a family $mathcalP$ of induced subgraphs of $G$ such that each element of $mathcalP$ is a star or a path and $$ (resp. $$). 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 $minspc$ and $minspp$, which are analogies of the Gy'{a}rf'{a}s-Sumner conjecture, and settle them. As a corollary of our results, we also settle other Ramsey-type problems for widely studied invariants.

This page was built for publication: Ramsey-type problems on induced covers and induced partitions toward the Gy\'{a}rf\'{a}s-Sumner conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6505972)