Abstract
The Gyárfás–Sumner conjecture says that for every tree T and every integer 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.
Original language | American English |
---|---|
Article number | 33 |
Journal | Graphs and Combinatorics |
Volume | 40 |
Issue number | 2 |
DOIs | |
State | Published - Apr 2024 |
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
Keywords
- Chromatic number
- Induced subgraphs