首页|Degeneracy of P-t-free and C->= t-free graphs with no large complete bipartite subgraphs
Degeneracy of P-t-free and C->= t-free graphs with no large complete bipartite subgraphs
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NSTL
Elsevier
A hereditary class of graphs G is chi-boundedif there exists a function f such that every graph G is an element of G satisfies chi(G) <= f(omega(G)), where chi(G) and omega(G) are the chromatic number and the clique number of G, respectively. As one of the first results about chi-bounded classes, Gyarfas proved in 1985 that if G is P-t-free, i.e., does not contain a t-vertex path as an induced subgraph, then chi (G) <= (t - 1)(omega(G)-1). In 2017, Chudnovsky, Scott, and Seymour proved that C->= t-free graphs, i.e., graphs that exclude induced cycles with at least tvertices, are chi-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 P-t-free graphs G, the value of chi(G) can be bounded from above by a polynomial function of omega(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 tthere exists a constant c such that for every l and every C->= t-free graph which does not contain K-l,K-l as a subgraph, it holds that chi(G)<= l(c). (C) 2021 Elsevier Inc. All rights reserved.
NSTL
Elsevier
