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

Tung Nguyen; Alex Scott; Paul Seymour

doi:10.1007/s00373-024-02754-z

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

Tung Nguyen, Alex Scott, Paul Seymour

Mathematics

Research output: Contribution to journal › Article › peer-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 language	English (US)
Article number	33
Journal	Graphs and Combinatorics
Volume	40
Issue number	2
DOIs	https://doi.org/10.1007/s00373-024-02754-z
State	Published - Apr 2024

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Keywords

Chromatic number
Induced subgraphs

Access to Document

10.1007/s00373-024-02754-z

Cite this

@article{8b676946c1b94dc69356d601b4232f42,

title = "A Note on the Gy{\'a}rf{\'a}s–Sumner Conjecture",

abstract = "The Gy{\'a}rf{\'a}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.",

keywords = "Chromatic number, Induced subgraphs",

author = "Tung Nguyen and Alex Scott and Paul Seymour",

note = "Publisher Copyright: {\textcopyright} The Author(s) 2024.",

year = "2024",

month = apr,

doi = "10.1007/s00373-024-02754-z",

language = "English (US)",

volume = "40",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "2",

}

TY - JOUR

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

AU - Nguyen, Tung

AU - Scott, Alex

AU - Seymour, Paul

N1 - Publisher Copyright: © The Author(s) 2024.

PY - 2024/4

Y1 - 2024/4

N2 - 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.

AB - 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.

KW - Chromatic number

KW - Induced subgraphs

UR - http://www.scopus.com/inward/record.url?scp=85187134502&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85187134502&partnerID=8YFLogxK

U2 - 10.1007/s00373-024-02754-z

DO - 10.1007/s00373-024-02754-z

M3 - Article

AN - SCOPUS:85187134502

SN - 0911-0119

VL - 40

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 2

M1 - 33

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this