A Note on the Gyárfás–Sumner Conjecture

Tung Nguyen, Alex Scott, Paul Seymour

Research output: Contribution to journalArticlepeer-review


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 languageEnglish (US)
Article number33
JournalGraphs and Combinatorics
Issue number2
StatePublished - Apr 2024

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


  • Chromatic number
  • Induced subgraphs


Dive into the research topics of 'A Note on the Gyárfás–Sumner Conjecture'. Together they form a unique fingerprint.

Cite this