Premium
Polynomial bounds for chromatic number. III. Excluding a double star
Author(s) -
Scott Alex,
Seymour Paul,
Spirkl Sophie
Publication year - 2022
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22862
Subject(s) - combinatorics , mathematics , star (game theory) , conjecture , chromatic scale , clique , stars , tree (set theory) , polynomial , function (biology) , chromatic polynomial , discrete mathematics , physics , astrophysics , mathematical analysis , evolutionary biology , biology
A “double star” is a tree with two internal vertices. It is known that the Gyárfás–Sumner conjecture holds for double stars, that is, for every double starH $H$ , there is a functionf H${f}_{H}$ such that ifG $G$ does not containH $H$ as an induced subgraph thenχ ( G ) ≤ f H ( ω ( G ) )$\chi (G)\le {f}_{H}(\omega (G))$ (whereχ , ω $\chi ,\omega $ are the chromatic number and the clique number ofG $G$ ). Here we prove thatf H${f}_{H}$ can be chosen to be a polynomial.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom