Abstract:A bull is a graph obtained from a four-vertex path by adding a vertex adjacent to the two middle vertices of the path. A graph $G$ is bull-free if no induced subgraph of $G$ is a bull. We prove that for all $k,t\in \mathbb N$, if $G$ is a bull-free graph of clique number at most $k$ and every triangle-free induced subgraph of $G$ has chromatic number at most $t$, then $G$ has chromatic number at most $k^{O(\log t)}$. We further show that the bound $k^{O(\log t)}$ is best possible up to a multiplicative constant in the exponent.
Thomassé, Trotignon, and Vušković (2017) were the first to give a bound of the form $2^{p\log p}$, where $p=O(k^2+t)$, with a proof that uses Chudnovsky's structure theorem for bull-free graphs. This was improved by Chudnovsky, Cook, Davies, and Oum (2026) to a bound of the form $k^{O(t)}$, with a 10-page proof that again relies heavily on Chudnovsky's structure theorem.
Our proof is a single page long and completely avoids the structure theorem, instead using only a result of Chudnovsky and Safra (which itself has a short proof).
From: Sepehr Hajebi [view email]
[v1]
Tue, 29 Apr 2025 18:04:42 UTC (9 KB)
[v2]
Thu, 1 May 2025 16:31:57 UTC (9 KB)
[v3]
Wed, 11 Jun 2025 23:20:58 UTC (9 KB)
[v4]
Fri, 3 Jul 2026 13:23:12 UTC (8 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。