The Gyárfás–Sumner conjecture says that for every tree T and every integer t≥ 1 t ≥ 1 , if G is a graph with no clique of size t and with sufficiently large chromatic number, then G contains an induced subgraph isomorphic to T . This remains open, but we prove that under the same hypotheses, G contains a subgraph H isomorphic to T that is “path-induced”; that is, for some distinguished vertex r , every path of H with one end r is an induced path of G .
No takes yet. Share an insight, caveat, or question.
Nguyen et al. (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: