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

Tung Nguyen, Alex Scott, Paul Seymour

Research output: Contribution to journalArticlepeer-review

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 languageAmerican English
Article number33
JournalGraphs and Combinatorics
Volume40
Issue number2
DOIs
StatePublished - Apr 2024

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Keywords

  • Chromatic number
  • Induced subgraphs

Fingerprint

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

Cite this