2020/12/07 by Marthe Bonamy, Bonamy, Marthe, Nicolás Bousquet +9
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2012.03686
openalex publication_date 2020/12/07 · openalex created_date 2020/12/21 · openalex updated_date 2026/07/28
A hereditary class of graphs G is χ-bounded if there exists a function f such that every graph G ∈ G satisfies χ(G) ≤ f(ω(G)), where χ(G) and ω(G) are the chromatic number and the clique number of G, respectively. As one of the first results about χ-bounded classes, Gyárfás proved in 1985 that if G is Pt-free, i.e., does not contain a t-vertex path as an induced subgraph, then χ(G) ≤ (t-1)ω(G)-1. In 2017, Chudnovsky, Scott, and Seymour proved that C≥ t-free graphs, i.e., graphs that exclude induced cycles with at least t vertices, are χ-bounded as well, and the obtained bound is again superpolynomial in the clique number. Note that Pt-1-free graphs are in particular C≥ t-free. It remains a major open problem in the area whether for C≥ t-free, or at least Pt-free graphs G, the value of χ(G) can be bounded from above by a polynomial function of ω(G). We consider a relaxation of this problem, where we compare the chromatic number with the size of a largest balanced biclique contained in the graph as a (not necessarily induced) subgraph. We show that for every t there exists a constant c such that for and every C≥ t-free graph which does not contain Kℓ,ℓ as a subgraph, it holds that χ(G) ≤ ℓc.