We prove that there is an absolute constant $c>0$ such that every graph of chromatic number at least $r$ and at most $cr^3\log^2 r$ edges contains at least $\binom r3$ triangles. The proof has three ingredients. First, a sparse-core argument based on a triangle-sensitive coloring estimate of Harris extracts, from any counterexample, an induced subgraph of order $O(r)$ and chromatic number at least $(1-\eta)r$. Second, we prove an order-uniform stability theorem: for every $\beta>0$ there is $\gamma>0$, independent of the constant in the linear order bound, such that every sufficiently large $s$-critical graph $J$ of order $O(s)$ with $\omega(J)\le (1-\beta)s$ has at least $\binom s3+\gamma s^3$ triangles. The proof combines the excess method and the modified-independent-set argument of Fox, Tidor, and Zhang. Third, we prove the exact bound when the graph contains a clique of order at least $(1-\delta)r$. This uses a new dense common-palette list analogue of Harris's edge--triangle estimate: if every list occupies a fixed positive proportion of a common palette, then the edge-triangle coloring bound survives up to a constant factor.
We prove that every triangle-free graph with minimum degree at least $\frac{n}{3}$ is $4$-colorable and thereby settle a problem of Brandt and Thomass\'e (2005) at the threshold $\frac{n}{3}$. The number four is best possible. For a positive integer-valued function $f(n)=o(n)$, we relate the chromatic number of $f(n)$-...
We prove a sparse version of the four-colour theorem of Brandt and Thomass\'{e}, answering a question of Allen, B\"ottcher, Kohayakawa and Roberts. For every fixed $0<\gamma\le1/10$ and every $p=p(n)\in(0,1]$, asymptotically almost surely every spanning triangle-free $H\subseteq G(n,p)$ with $\delta(H)\ge(1/3+\gamma)pn...
For a graph $G$, a proper edge coloring of $G$ is called a D-coloring if every diamond subgraph of $G$ is rainbow. Let $\chi'_D(G)$ be the D-chromatic index of $G$, which is the smallest integer $k$ such that $G$ admits a D-coloring with $k$ colors. Let $\Delta$ be the maximum degree of $G$. The only known Brooks-type...
Let $\Ke$ be obtained from $K_7$ by deleting two independent edges. We prove that every 5-connected graph on $n\ge7$ vertices with at least $4n-9$ edges contains a $\Ke$ minor, settling Conjecture~1.4 of Dvo\v r\'ak, Norin and Rahman (arXiv preprint 2609.17760v1). The bound is sharp. We prove the stronger statement tha...
Caibing Chang, Zi-Jian Deng, Qin-Fei Tang et al.· 0 citations
An equitable $k$-coloring of a graph partitions its vertex set into $k$ independent sets whose sizes differ by at most one; the least such $k$ is the equitable chromatic number $\chie(G)$. Every known bound on $\chie$ valid for all graphs, beginning with the Hajnal--Szemer\'edi theorem, is linear in the maximum degree...
We study minimum degree conditions for tight Hamiltonian cycles in uniformly dense $3$-uniform hypergraphs. We prove that for every $d,\alpha>0$, every sufficiently large $(\rho,d)$-dense $3$-graph on $n$ vertices with minimum codegree at least $(1/3+\alpha)n$ contains a tight Hamiltonian cycle. This resolves a problem...
Yao-Bin Chen, Jie Han, Xi-Zhi Liu· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
