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$ can be made four-partite by deleting at most $\min\{C_\gamma n/p,(1/8+\gamma)pn^2\}$ edges. In fact, deleting at most $C_\gamma n/p$ edges yields a graph that admits a homomorphism to an Andr\'{a}sfai or Vega graph with certificate complexity at most $1/(3\gamma)$. Together with matching lower bounds from random blow-ups, this structural result determines, uniformly in $p$, the minimum-degree thresholds for $q$-partiteness with $O(n/p)$ edge deletions: $2/5$ for $q=2$, $10/29$ for $q=3$, and $1/3$ for every fixed $q\ge4$. For every fixed $q\ge2$ and $\log n/n\ll p\ll n^{-1/2}$, asymptotically almost surely $G(n,p)$ contains a spanning triangle-free subgraph with minimum degree $(1-o(1))pn$ that requires $(1/(2q)+o(1))pn^2$ edge deletions to become $q$-partite, showing that the coefficient $1/(2q)$ cannot be improved even under this stronger degree condition.
For a graph $G$, let $\alpha_1(G)$ be the maximum size of an edge set containing at most one edge from every triangle, and let $\tau_1(G)$ be the minimum size of an edge set meeting every triangle. Erd\H{o}s, Gallai, and Tuza proved that $\alpha_1(G)+\tau_1(G)=\Omega(m^{2/3})$ for every $m$-edge graph and asked for the...
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...
Let $\zeta(G)$ denote the minimum number of parts in a partition of $V(G)$ in which every part induces either a clique or an independent set. Erd\H{o}s and Gimbel asked whether, for $G_n\sim G(n,1/2)$, the difference $\chi(G_n)-\zeta(G_n)$ tends to infinity with high probability. We resolve this problem along the full...
For ordered graphs $H_1,\ldots,H_t$, let $\rt(H_1,\ldots,H_t)$ denote the least integer $N$ such that every $t$-coloring of the edges of the naturally ordered complete graph on $[N]$ contains an ordered copy of $H_i$ in color $i$ for some $i\in[t]$. We prove that a uniformly random ordered matching $M$ on $n$ vertices...
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 c...
A majority C-colouring partitions a graph into classes in which every vertex has at least half of its neighbours. Write $M(G)$ for the maximum number of classes. We determine $M(K_q^{\square(2k+1)})=\left\lfloor\frac{q^{k+1}}{\lfloor q/2\rfloor+1}\right\rfloor\qquad(q\ge3,\ k\ge0).$ The lower bound follows from explici...
Ze-Hua Lu· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
