Ramsey-type results for path covers and path partitions (Q2094874)

Summary: A family \(\mathcal{P}\) of subgraphs of \(G\) is called a path cover (resp. a path partition) of \(G\) if \(\bigcup_{P\in \mathcal{P}}V(P)=V(G)\) (resp. \(\dot\bigcup_{P\in \mathcal{P}}V(P)=V(G))\) and every element of \(\mathcal{P}\) is a path. The minimum cardinality of a path cover (resp. a path partition) of \(G\) is denoted by \(\mathrm{pc}(G)\) (resp. \(\mathrm{pp}(G))\). In this paper, we characterize the forbidden subgraph conditions assuring us that \(\mathrm{pc}(G)\) (or \(\mathrm{pp}(G))\) is bounded by a constant. Our main results introduce a new Ramsey-type problem.