论文标题
$ p_t $ - free和$ c _ {\ geq t} $的退化 - 没有大的完整两部分子图
Degeneracy of $P_t$-free and $C_{\geq t}$-free graphs with no large complete bipartite subgraphs
论文作者
论文摘要
如果存在一个函数$ f $，则一类遗传级图$ \ nathcal {g} $ is \ emph {$χ$ bounded}，以至于每个图$ f $ in \ mathcal {g} $ in \ nathcal {g} $满足$χ（g）\ leq f（G）分别$ g $。作为大约$χ$结合的类的第一个结果之一，Gyárfás在1985年证明，如果$ g $是$ p_t $ -free，即不包含$ t $ - vertex路径作为诱发的子图，则$χ（g）\ leq（t-leq（t-1）^{t-1）在2017年，Chudnovsky，Scott和Seymour证明了$ C _ {\ geq T} $ - 免费图形，即除外的图形，这些图形排除了至少$ t $顶点的诱发周期，也是$χ$ bonded的，并且获得的又一次绑定在Clique number中。请注意，$ p_ {t-1} $ - 免费图形特别是$ c _ {\ geq t} $ - 免费。无论是$ c _ {\ geq t} $ - 免费，还是至少$ p_t $ - free Graphs $ g $，它仍然是该区域的主要开放问题，$χ（g）$的值可以通过上面的$ω（g）$的多项式函数从上面界定。我们考虑了这个问题的放松，在该问题中，我们将色数与图中包含的最大平衡的biclique的大小比较为A（不一定是诱发的）子图。我们表明，每一个$ t $都存在一个常数$ c $，因此，对于不包含$ k _ {\ ell，\ ell} $的每一个$ c _ {\ geq t} $作为一个子插图，它认为$χ（g）\ leq \ ell^ell^{c} $。
A hereditary class of graphs $\mathcal{G}$ is \emph{$χ$-bounded} if there exists a function $f$ such that every graph $G \in \mathcal{G}$ satisfies $χ(G) \leq 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 $P_t$-free, i.e., does not contain a $t$-vertex path as an induced subgraph, then $χ(G) \leq (t-1)^{ω(G)-1}$. In 2017, Chudnovsky, Scott, and Seymour proved that $C_{\geq 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 $P_{t-1}$-free graphs are in particular $C_{\geq t}$-free. It remains a major open problem in the area whether for $C_{\geq t}$-free, or at least $P_t$-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_{\geq t}$-free graph which does not contain $K_{\ell,\ell}$ as a subgraph, it holds that $χ(G) \leq \ell^{c}$.
