2021/08/16 by Scott, Alex, Seymour, Paul, Spirkl, Sophie · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2108.07066
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 star H, there is a function f such that if G does not contain H as an induced subgraph then χ(G)≤ f(ω(G)) (where χ, ω are the chromatic number and the clique number of G). Here we prove that f can be chosen to be a polynomial.