Name
Abstract | ||
|---|---|---|
The Gyarfas-Sumner conjecture says that for every forest H, there is a function f(H) such that if G is H-free then chi(G) <= f(H) (omega(G)) (where chi, omega are the chromatic number and the clique number of G). Louis Esperet conjectured that, whenever such a statement holds, f(H) can be chosen to be a polynomial. The Gyarfas-Sumner conjecture is only known to be true for a modest set of forests H, and Esperet's conjecture is known to be true for almost no forests. For instance, it is not known when H is a five-vertex path. Here we prove Esperet's conjecture when each component of H is a star. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1002/jgt.22829 | JOURNAL OF GRAPH THEORY |
Keywords | DocType | Volume |
chromatic number, colouring, Gyarfas-Sumner conjecture, induced subgraph, chi-boundedness | Journal | 101 |
Issue | ISSN | Citations |
2 | 0364-9024 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alex Scott | 1 | 0 | 0.68 |
| Paul D. Seymour | 2 | 2786 | 314.49 |
| Sophie Spirkl | 3 | 0 | 0.68 |