The classical Andrásfai-Erdős-Sós theorem considers the chromatic number of $K_{r + 1}$-free graphs with large minimum degree, and in the case $r = 2$ says that any $n$-vertex triangle-free graph with minimum degree greater than $2/5 \cdot n$ is bipartite. This began the study of the chromatic profile of triangle-free graphs: for each $k$, what minimum degree guarantees that a triangle-free graph is $k$-colourable? The profile has been extensively studied and was finally determined by Brandt and Thomassé.

Triangle-free graphs are exactly those in which each neighbourhood is one-colourable. As a natural variant, Łuczak and Thomassé introduced the notion of a locally bipartite graph in which each neighbourhood is 2-colourable. Here we study the chromatic profile of the family of graphs in which every neighbourhood is $b$-colourable (locally $b$-partite graphs) as well as the family where the common neighbourhood of every $a$-clique is $b$-colourable. Our results include the chromatic thresholds of these families as well as showing that every $n$-vertex locally $b$-partite graph with minimum degree greater than $(1 - 1/(b + 1/7)) \cdot n$ is $(b + 1)$-colourable. Understanding these locally colourable graphs is crucial for extending the Andrásfai-Erdős-Sós theorem to non-complete graphs, which we develop elsewhere.

§ INTRODUCTION

In 1973, Erdős and Simonovits [8] asked the following question: for each graph $H$ and positive integer $k$, what $\delta$ guarantees that every $n$-vertex $H$-free graph with minimum degree greater than $\delta n$ is $k$-colourable? The values of $\delta$, as $k$ varies, form the chromatic profile of $H$-free graphs. More generally, for a family of graphs $\sca{F}$, the chromatic profile of $\sca{F}$ is the sequence of values $\delta_{\chi}(\sca{F}, k)$ where

\begin{equation*}
\delta_{\chi}(\sca{F}, k) = \inf\set{d : \text{if }\delta(G) \geqslant d \ssize{G} \text{ and } G \in \sca{F}, \text{then } \chi(G) \leqslant k}.
\end{equation*}

In the case where $\sca{F}$ is the family of $H$-free graphs we write $\delta_{\chi}(H, k)$ for $\delta_{\chi}(\sca{F}, k)$. The question of determining $\delta_{\chi}(H, k)$, first asked in [8], was re-emphasised by Allen, Böttcher, Griffiths, Kohayakawa and Morris [1]. For general $H$ very little is known about the chromatic profile and indeed Erdős and Simonovits described it as “too complicated”.

There has been much greater success with the chromatic threshold. The chromatic threshold of a family $\sca{F}$ is the limit (and so infimum) of the sequence $\delta_{\chi}(\sca{F}, k)$: that is,

\begin{align*}
\delta_{\chi}(\sca{F}) & = \inf_{k} \delta_{\chi}(\sca{F}, k) \\
& = \inf \{d : \exists C = C(\sca{F}, d) \text{ such that if } \delta(G) \geqslant d \ssize{G} \text{ and } G \in \sca{F}, \text{then } \chi(G) \leqslant C\}.
\end{align*}

Allen et al. [1] determined the chromatic threshold of $H$-free graphs for every graph $H$. They further obtained the chromatic threshold of locally bipartite graphs – the family of graphs in which each neighbourhood is bipartite – confirming the conjecture of Łuczak and Thomassé [16] that this threshold is $1/2$.

Whilst understanding the chromatic structure of locally bipartite graphs is interesting in its own right, a further motive (that originally brought them to our attention) is to extend the Andrásfai-Erdős-Sós theorem [2] – that theorem gives the first interesting value in the chromatic profile of complete graphs, namely

\begin{equation*}
\delta_{\chi}(K_{r + 1}, r) = 1 - \frac{1}{r - 1/3}.
\end{equation*}

This theorem can be seen as a minimum-degree analogue of Erdős and Simonovits's stability theorem [6, 7, 19] for the structure of $K_{r + 1}$-free graphs with close to the maximum number of edges. Erdős and Simonovits's result says that any $H$-free graph with $(1 - 1/r - o(1)) \binom{n}{2}$ edges (where $r + 1$ is the chromatic number of $H$) can be made $r$-partite by deleting $o(n^{2})$ edges. The natural minimum-degree analogue asks what minimum degree guarantees that an $H$-free graph can be made $r$-partite by deleting $o(n^{2})$ edges. The theorem of Andrásfai, Erdős and Sós answers this for cliques. It turns out that, in order to extend the theorem to non-complete $H$ (as in [12]), it is crucial to better understand locally colourable graphs (as defined next), and that is our purpose in this paper.

A graph is $a$-locally $b$-partite if the common neighbourhood of every $a$-clique is $b$-colourable. A graph is locally $b$-partite if it is 1-locally $b$-partite: the neighbourhood of every vertex is $b$-colourable. We use $\sca{F}_{a, b}$ to denote the family of $a$-locally $b$-partite graphs.

The family of locally bipartite graphs is $\sca{F}_{1, 2}$. Note that, in general,

\begin{equation*}
\sca{F}_{1, \ell} \subset \sca{F}_{2, \ell - 1} \subset \dotsb \subset \sca{F}_{\ell, 1} = \set{G : G \text{ is } K_{\ell + 2}\text{-free}}.
\end{equation*}

In particular, $\sca{F}_{a, b}$ is a subfamily of $K_{\ell + 2}$-free graphs where $\ell = a + b - 1$.

As mentioned, the Andrásfai-Erdős-Sós theorem gives the first interesting value in the chromatic profile of $K_{\ell + 2}$-free graphs, that is, of the family $\sca{F}_{\ell, 1}$. For the basic case of triangle-free graphs, this shows $\delta_{\chi}(K_{3}, 2) = 2/5$. Hajnal (see [8]) showed that $\delta_{\chi}(K_{3}) \geqslant 1/3$. Häggkvist [10] showed that $\delta_{\chi}(K_{3}, 3) \geqslant 10/29$ and Jin [13] proved that equality holds. Finally, building on work of Chen, Jin and Koh [5], Brandt and Thomassé [4] fully described triangle-free graphs with minimum degree above the chromatic threshold (showing that, in fact, $\delta_{\chi}(K_{3}) = \delta_{\chi}(K_{3}, 4) = 1/3$). Moreover, Goddard and Lyle [9], and Nikiforov [17], independently showed that the chromatic profile of $K_{r + 2}$-free graphs can be derived straightforwardly from that of triangle-free graphs. The chromatic profile of the $K_{\ell + 2}$-free graphs, that is, of $\sca{F}_{\ell, 1}$, has thus been completely determined.

The chromatic profile of the family $\sca{F}_{a, b}$ for $b \geqslant 2$ displays substantially different behaviour to the case $b = 1$, however. In <Ref> we determine the chromatic threshold of the family of $a$-locally $b$-partite graphs. This result in the special case $a = 1$ and $b = 2$ was conjectured (with a construction for the lower bound) by Łuczak and Thomassé [16] and proved by Allen et al. [1].

Let $a$ and $b$ be positive integers with $b \geqslant 2$. Let $\sca{F}_{a, b}$ denote the family of $a$-locally $b$-partite graphs and let $\ell = a + b - 1$. Then

\begin{equation*}
\delta_{\chi}(\sca{F}_{a, b}) = 1 - \frac{1}{\ell},
\end{equation*}

and, in particular, the chromatic threshold of locally $b$-partite graphs, $\delta_{\chi}(\sca{F}_{1, b})$, is $1 - 1/b$.

For comparison, the chromatic threshold of the family, $\sca{F}_{\ell, 1}$, of $K_{\ell + 2}$-free graphs is $1 - 1/(\ell + 1/2)$.

Now for the chromatic profile. All $a$-locally $b$-partite graphs are $K_{a + b + 1}$-free and furthermore, the $n$-vertex $K_{a + b + 1}$-free graph with highest minimum degree (and most edges), the Turán graph [20], $T_{a + b}(n)$ is $a$-locally $b$-partite and $(a + b)$-chromatic. In particular,

\begin{equation*}
\delta_{\chi}(\sca{F}_{a, b}, k) = 1 - \frac{1}{a + b} \text{ for } k = 1, 2, \dotsc, \ell := a + b - 1,
\end{equation*}

since there are no $K_{a + b + 1}$-free graphs (and so no $a$-locally $b$-partite) graphs with $\delta(G) > (1 - 1/(a + b)) \cdot \ssize{G}$. In particular, the first interesting value in the chromatic profile of $a$-locally $b$-partite graphs is $\delta_{\chi}(\sca{F}_{a, b}, \ell + 1)$. An upper bound for this is given by Theorems <ref> ($b \geqslant 3$) and <ref> ($b = 2$). In <Ref> we prove <Ref> for locally $b$-partite graphs (that is, for $a = 1$) and in <Ref>, we extend it to all $a$ and prove <Ref>.

Let $a$ and $b$ be positive integers with $b \geqslant 3$. Let $\sca{F}_{a, b}$ denote the family of $a$-locally $b$-partite graphs and let $\ell = a + b - 1$. Then

\begin{equation*}
\delta_{\chi}(\sca{F}_{a, b}, \ell + 1) \leqslant 1 - \frac{1}{\ell + 1/7},
\end{equation*}

and, in particular, every locally $b$-partite graph $G$ with $\delta(G) > (1 - 1/(b + 1/7)) \cdot \ssize{G}$ is $(b + 1)$-colourable.

Let $a$ be a positive integer. Let $\sca{F}_{a, 2}$ denote the family of $a$-locally bipartite graphs and let $\ell = a + 1$. Then

\begin{equation*}
\delta_{\chi}(\sca{F}_{a, 2}, \ell + 1) = 1 - \frac{1}{\ell + 1/3}.
\end{equation*}

Note that the chromatic threshold of the family of $K_{\ell + 2}$-free graphs is $1 - 1/(\ell + 1/2)$. In particular, all chromatic profile values for $K_{\ell + 2}$-free graphs are greater than the first interesting value for $a$-locally $b$-partite ones ($b \geqslant 2$).

To extend the chromatic profile of triangle-free graphs to $K_{r + 1}$-free graphs as mentioned above, Goddard and Lyle [9], and Nikiforov [17], showed that every $n$-vertex maximal $K_{r + 1}$-free graph with minimum degree greater than $\delta_{\chi}(K_{r + 1}) \cdot n$ consists of an independent set joined to a $K_{r}$-free graph. That is, maximal graphs of $\sca{F}_{r, 1}$ with sufficiently large minimum degree are obtained from those in $\sca{F}_{r - 1, 1}$ by joining an independent set. A simple induction then converts the structure of triangle-free graphs to the structure of $K_{r + 1}$-free graphs. It is natural to ask whether something similar can be done to convert between different families $\sca{F}_{a, b}$. Firstly, there does not seem to be an easy way to convert between $\sca{F}_{a, b - 1}$ and $\sca{F}_{a, b}$ (certainly joining on an independent set fails). Although we obtain the upper bound for $\delta_{\chi}(\sca{F}_{1, b}, b + 1)$ in <Ref> using knowledge of locally bipartite graphs, it is not a straightforward induction. Joining on an independent set to a graph in $\sca{F}_{a - 1, b}$ does give a graph in $\sca{F}_{a, b}$, but it is not clear that all maximal graphs in $\sca{F}_{a, b}$ of large minimum degree are obtained in this way – the lower value of $\delta_{\chi}(\sca{F}_{a, b})$ for $b \geqslant 2$ means the structural lemma of Goddard, Lyle and Nikiforov does not apply. Indeed, our arguments extending results from locally $b$-partite graphs to $a$-locally $b$-partite graphs are simpler, although interestingly require knowledge of locally $b'$-partite graphs for all $b' \leqslant a + b$. It seems that the crux of understanding locally colourable graphs is understanding locally $b$-partite graphs, a sentiment we will crystallise in <Ref>.

Some of the required knowledge of locally bipartite graphs was obtained in [11], which included results such as

\begin{equation*}
\delta_{\chi}(\sca{F}_{1, 2}, 3) = 4/7, \quad \text{and} \quad \delta_{\chi}(\sca{F}_{1, 2}, 4) \leqslant 6/11.
\end{equation*}

The results in [11] give detailed information about $n$-vertex locally bipartite graphs with minimum degree greater than $6/11 \cdot n$, including homomorphism properties. However, in order to prove the upper bound for $\delta_{\chi}(\sca{F}_{1, b}, b + 1)$ in <Ref>, we need to extend our structural knowledge of locally bipartite graphs down to $8/15$, though, fortunately, we do not need any homomorphism properties. We do this in <Ref> and our full knowledge of locally bipartite graphs is summarised there in <Ref>.

§.§ Notation

Let $G$ be a graph and $X \subset V(G)$. We write $\Gamma(X)$ for $\cap_{v \in X} \Gamma(v)$ (the common neighbourhood of the vertices of $X$) and $\deg(X)$ or $d(X)$ for $\ssize{\Gamma(X)}$. We often omit the parentheses so $\Gamma(u, v) = \Gamma(u) \cap \Gamma(v)$ and $d(u, v) = \ssize{\Gamma(u, v)}$. We write $G_{X}$ for $G[\Gamma(X)]$ so, for example, $G_{u, v}$ is the induced graph on the common neighbourhood of vertices $u$ and $v$. Note that $G$ being $a$-locally $b$-partite is equivalent to $\chi(G_{K}) \leqslant b$ for every $a$-clique $K$ of $G$. We make frequent use of the fact that for two vertices $u$ and $v$ of $G$

\begin{equation*}
d(u, v) = d(u) + d(v) - \ssize{\Gamma(u) \cup \Gamma(v)} \geqslant d(u) + d(v) - \ssize{G} \geqslant 2 \delta(G) - \ssize{G}.
\end{equation*}

Given a set of vertices $X \subset V(G)$, we write $e(X, G)$ for the number of ordered pairs of vertices $(x, v)$ with $x \in X$, $v \in G$ and $xv$ an edge in $G$. In particular, $e(X, G)$ counts each edge in $G[X]$ twice and each edge from $X$ to $G - X$ once and satisfies

\begin{equation*}
e(X, G) = \sum_{x \in X} \deg(x) = \sum_{v \in G} \ssize{\Gamma(v) \cap X}.
\end{equation*}

We generalise this notation to vertex weightings which will appear in many of our arguments. We will take a set of vertices $X \subset V(G)$ and assign weights $\omega : X \rightarrow \ZZN$ to the vertices of $X$. Then we define

\begin{equation*}
\omega(X, G) = \sum_{x \in X} \omega(x) \deg(x) = \sum_{v \in G} \text{Total weight of the neighbours of } v \text{ in } X.
\end{equation*}

We will often use the word circuit (as opposed to cycle) in our arguments. A circuit is a sequence of (not necessarily distinct) vertices $v_{1}, v_{2}, \dotsc, v_{\ell}$ with $\ell > 1$, $v_{i}$ adjacent to $v_{i + 1}$ (for $i = 1, 2, \dotsc, \ell - 1$) and $v_{\ell}$ adjacent to $v_{1}$. Note that in a locally bipartite graph the neighbourhood of any vertex does not contain an odd circuit (and of course does not contain an odd cycle). We use circuit to avoid considering whether some pairs of vertices are distinct when it is unnecessary to do so.

Given a graph $G$, a blow-up of $G$, is a graph obtained by replacing each vertex $v$ of $G$ by a non-empty independent set $I_{v}$ and each edge $uv$ by a complete bipartite graph between classes $I_{u}$ and $I_{v}$. We say we have blown-up a vertex $v$ by $n$ if $\ssize{I_{v}} = n$. It is often helpful to think of this as weighting vertex $v$ by $n$.

A blow-up is balanced if the independent sets $(I_{v})_{v \in G}$ are as equal in size as possible. We use $G(t)$ to denote the graph obtained by blowing-up each vertex of $G$ by $t$ – $G(t)$ is the balanced blow-up of $G$ on $t \ssize{G}$ vertices. Note, for example, that the balanced blow-ups of the clique, $K_{r}$, are exactly the Turán graphs, $T_{r}(n)$. We note in passing that a graph has the same chromatic and clique number as any of its blow-ups. Furthermore if $H$ is a blow-up of $G$, then $G$ is $a$-locally $b$-partite if and only if $H$ is $a$-locally $b$-partite.

Given two graphs $G$ and $H$, the join of $G$ and $H$, denoted $G + H$, is the graph obtained by taking disjoint copies of $G$ and $H$ and joining each vertex of the copy of $G$ to each vertex of the copy of $H$. Note that the chromatic and clique numbers of $G + H$ are the sum of the chromatic and clique numbers of $G$ and $H$.

A graph $G$ is homomorphic to a graph $H$, written $G \rightarrow H$, if there is a map $\varphi : V(G) \rightarrow V(H)$ such that for any edge $uv$ of $G$, $\varphi(u)\varphi(v)$ is an edge of $H$. A graph $G$ is homomorphic to a graph $H$ if and only if $G$ is a subgraph of some blow-up of $H$. In particular, if $G \rightarrow H$, then $\chi(G) \leqslant \chi(H)$ and moreover if $H$ is $a$-locally $b$-partite, then $G$ is also.

§ CHROMATIC THRESHOLDS

The $(r - 1)$-locally 1-partite graphs are exactly the $K_{r + 1}$-free graphs, and their chromatic threshold was determined by Goddard and Lyle [9], and Nikiforov [17].

\begin{equation*}
\delta_{\chi}(\sca{F}_{r - 1, 1}) = \delta_{\chi}(K_{r + 1}) = 1 - \frac{1}{r - 1/2}.
\end{equation*}

In this section we prove <Ref>, showing that $\delta_{\chi}(\sca{F}_{a, b}) = 1 - 1/(a + b - 1)$ for all $a \geqslant 1$ and $b \geqslant 2$. The upper bound follows from the work of Allen et al. [1].

[of upper bound in <Ref>]
Fix $a$ and $b$ positive integers with $b \geqslant 2$ and let $\ell = a + b - 1$. Let $d > 1 - 1/\ell$ and let $G \in \sca{F}_{a, b}$ with $\delta(G) \geqslant d \ssize{G}$. Now $K_{\ell - 1} + C_{5}$ has an $a$-clique whose common neighbourhoods contains $K_{b - 2} + C_{5}$ so is not $b$-colourable. In particular $G$ is $(K_{\ell - 1} + C_{5})$-free.

Now, in the language of [1], $K_{\ell - 1} + C_{5}$ is $(\ell + 2)$-near-acyclic, so the chromatic threshold of the family of $(K_{\ell - 1} + C_{5})$-free graphs is $1 - 1/\ell$. In particular, there is a constant $C$ depending only upon $d$ and $\ell$ (and not on $G$) such that $\chi(G) \leqslant C$. Hence,

\begin{equation*}
\delta_{\chi}(\sca{F}_{a, b}) \leqslant 1 - \frac{1}{\ell} = 1 - \frac{1}{a + b - 1}. \qedhere
\end{equation*}

For the lower bound it suffices to give examples of graphs $G \in \sca{F}_{a, b}$ with $\delta(G) \geqslant (1 - 1/(a + b - 1) - o(1)) \cdot \ssize{G}$ which have arbitrarily large chromatic number. Allen et al. [1] used graphs of large girth and high chromatic number as well as Borsuk-Hajnal graphs for their lower bounds. However, these depend upon the forbidden subgraph $H$ and do not seem to be applicable here where the collection of forbidden subgraphs is infinite. Łuczak and Thomassé [16] modified a Borsuk graph to give the lower bound of 1/2 for the chromatic threshold of locally bipartite graphs. We will give a somewhat simpler example which gives the lower bound for all $\sca{F}_{a, b}$ ($a \geqslant 1, b \geqslant 2$).

Our example is based upon the classical Schrijver graph [18]. The Kneser graph, $\operatorname{KG}(n, k)$, is the graph whose vertex set is all $k$-subsets of $\set{1, 2, \dotsc, n}$ with two vertices adjacent if the corresponding $k$-sets are disjoint. In 1955 Kneser [14] conjectured that the chromatic number of $\operatorname{KG}(n, k)$ is $n - 2k + 2$. This conjecture remained open for two decades and was first proved by Lovász [15] using homotopy theory (see also Bárány [3] for a very short proof).

The Schrijver graph, $\operatorname{SG}(n, k)$, is the graph whose vertex set is all $k$-subsets of $\set{1, 2, \dotsc, n}$ which do not contain both $i$ and $i + 1$ for any $i = 1, 2, \dotsc, n - 1$ and do not contain both $n$ and 1. Again vertices are adjacent if the corresponding $k$-sets are disjoint. Put another way, $\operatorname{SG}(n, k)$ is the induced subgraph of $\operatorname{KG}(n, k)$ obtained by deleting all vertices whose corresponding sets are supersets of any of $\set{1, 2}$, $\set{2, 3}$, $\set{3, 4}$, …, $\set{n - 1, n}$, $\set{n, 1}$. Schrijver [18] showed that $\operatorname{SG}(n, k)$ is vertex-critical with chromatic number $\chi(\operatorname{SG}(n, k)) = \chi(\operatorname{KG}(n, k)) = n - 2k + 2$.

[of lower bound in <Ref>]
Fix $a$ and $b$ positive integers with $b \geqslant 2$ and let $\ell = a + b - 1$. Fix $k$ and let $n = 2k + f(k)$ where $f(k)$ is a non-negative integer less than $k$, and both $f(k) \rightarrow \infty$, $f(k)/k \rightarrow 0$ as $k \rightarrow \infty$. Since $k > n/3$, graph $\operatorname{SG}(n, k)$ is triangle-free. We will eventually consider a blow-up of the graph shown in <Ref>.

ıin -1,1
ȷin -1,1
(4*ı- 1.6,1.5*ȷ)v_ı,ȷ,n,1
(4*ı- 0.8,1.5*ȷ)v_ı,ȷ,1,2
(4*ı+ 0.8,1.5*ȷ)blob_ı,ȷ
(4*ı+ 1.6,1.5*ȷ)v_ı,ȷ,n-1,n
[above = -4pt](blob_ı,ȷ)$\dotsc$

(4*ı- 2.2,1.5*ȷ- 0.5)A_ı,ȷ
(4*ı+ 2.2,1.5*ȷ- 0.5)B_ı,ȷ
(4*ı+ 2.2,1.5*ȷ+ 0.5)C_ı,ȷ
(4*ı- 2.2,1.5*ȷ+ 0.5)D_ı,ȷ
(A_ı,ȷ,B_ı,ȷ) AB_ı,ȷ
(B_ı,ȷ,C_ı,ȷ) BC_ı,ȷ
(C_ı,ȷ,D_ı,ȷ) CD_ı,ȷ
(D_ı,ȷ,A_ı,ȷ) DA_ı,ȷ

(SG) at (0,3.8)$\operatorname{SG}(n, k)$;

(AB_-1,1,CD_-1,-1 AB_1,1,CD_1,-1 BC_-1,1,DA_1,1 BC_-1,-1,DA_1,-1 B_-1,1,D_1,-1 C_-1,-1,A_1,1)
(v,B_-1,1 v,B_1,1 v,C_-1,-1 v,C_1,-1)
[dashed, line width = 0.6pt] (SG) – (C_-1,1);
[dashed, line width = 0.6pt] (SG) – (D_1,1);
[dashed, line width = 0.6pt] (SG) – (C_-1,-1);
[dashed, line width = 0.6pt] (SG) – (D_1,-1);

* Each rectangle is an independent set of $n$ vertices: $v_{1, 2}$, $v_{2, 3}$, …, $v_{n - 1, n}$, $v_{n, 1}$ – we always consider indices modulo $n$.

* There are $\ell - 1$ rectangles and the vertices in rectangles form a complete $(\ell - 1)$-partite graph with $n$ vertices in each part.

* The vertex $v$ is adjacent to all of the $v_{i, i + 1}$ but has no neighbours in the copy of $\operatorname{SG}(n, k)$ – in particular, the rectangles together with $v$ form a complete $\ell$-partite graph.

* Finally $A \in \operatorname{SG}(n, k)$ is adjacent to $v_{i, i + 1}$ if either $i$ or $i + 1$ is in $A$ (note, by the definition of the Schrijver graph, that it is impossible for both $i$ and $i + 1$ to be in $A$).

We first check that the graph, $G$, shown in <Ref> is locally $\ell$-partite. Fix a vertex $u$ of $G$. If $u = v$, then $G_{u}$ is the $\ell - 1$ rectangles and so is $(\ell - 1)$-colourable. Next suppose that $u$ is a vertex in the copy of $\operatorname{SG}(n, k)$, so $v \not \in \Gamma(u)$. As $\operatorname{SG}(n, k)$ is triangle-free, $\Gamma(u)$ consists of an independent set in $\operatorname{SG}(n, k)$ together with some vertices from the $\ell - 1$ rectangles. In particular, $G_{u}$ is $\ell$-colourable.

Finally suppose that $u$ lies in the $\ell - 1$ rectangles. By symmetry, we may take $u$ to be a $v_{1, 2}$. Then $\Gamma(u)$ consists of two independent sets in $\operatorname{SG}(n, k)$ (sets containing 1 and sets containing 2), $\ell - 2$ rectangles and $v$. There are no edges from $v$ to the copy of $\operatorname{SG}(n, k)$, so $G_{u}$ is $\ell$-colourable.

Now we consider a suitable blow-up of $G$. Let $s$ be a multiple of $n$ that is much larger than $\ssize{\operatorname{SG}(n, k)}$. We will blow-up each $v_{i, i + 1}$ by $s/n$ so that all rectangles contain $s$ vertices and we will blow up $v$ by $s$ also. Note that $v$ together with the rectangles form a complete $\ell$-partite graph with $s$ vertices in each part. Keep the copy of $\operatorname{SG}(n, k)$ as it is. Call the resulting graph $G'$.

* $G'$ has $\ell s + \ssize{\operatorname{SG}(n, k)}$ vertices.

* Any $A \in \operatorname{SG}(n, k)$ is adjacent to $2k/n$ proportion of the $v_{i, i + 1}$ so has degree at least $(\ell - 1) s (2k)/n = (\ell - 1)s/(1 + f(k)/(2k))$.

* Any other vertex has degree at least $(\ell - 1) s$.

* $\chi(G') \geqslant \chi(\operatorname{SG}(n, k)) = n - 2k + 2 = f(k) + 2$.

Given any $C, \varepsilon > 0$, we may choose $k$ large enough so that $f(k) \geqslant C$ and $(\ell - 1)/(1 + f(k)/(2k)) \geqslant \ell - 1 - \varepsilon$ and then choose $s$ large enough so that $\ell s + \ssize{\operatorname{SG}(n, k)} \leqslant (\ell + \varepsilon) s$. The resulting graph $G'$ has chromatic number at least $f(k) + 2 \geqslant C$ and

\begin{equation*}
\frac{\delta(G')}{\ssize{G'}} \geqslant \frac{\ell - 1 -\varepsilon}{\ell + \varepsilon} \geqslant 1 - \frac{1}{\ell} - \varepsilon.
\end{equation*}

Being $a$-locally $b$-partite is preserved when taking blow-ups. Now $G$ is locally $\ell$-partite and so $G'$ is too. As $\sca{F}_{1, \ell} \subset \sca{F}_{a, b}$, $G'$ is $a$-locally $b$-partite. Thus,

\begin{equation*}
\delta_{\chi}(\sca{F}_{a, b}) \geqslant 1 - \frac{1}{\ell} - \varepsilon = 1 - \frac{1}{a + b - 1} - \varepsilon,
\end{equation*}

but $\varepsilon > 0$ was arbitrary and so we have the required result.

§ STRUCTURE OF LOCALLY BIPARTITE GRAPHS DOWN TO $8/15$

Our understanding of the structure of locally bipartite graphs can be summarised as follows. The graphs $\overline{C}_{7}$, $H_{2}^{+}$, $H_{2}$, etc. can be seen in <Ref> where they are discussed more thoroughly.

Let $G$ be a locally bipartite graph.

* If $\delta(G) > 4/7 \cdot \ssize{G}$, then $G$ is 3-colourable. Balanced blow-ups of $\overline{C}_{7}$ show that this is tight.

* If $\delta(G) > 5/9 \cdot \ssize{G}$, then $G$ is homomorphic to $\overline{C}_{7}$. Also, $G$ is either 3-colourable or contains $\overline{C}_{7}$. Suitable blow-ups of $H_{2}^{+}$ show that this is tight.

* There is an absolute constant $\varepsilon > 0$ such that if $\delta(G) > (5/9 - \varepsilon) \cdot \ssize{G}$, then $G$ is homomorphic to either $\overline{C}_{7}$ or $H_{2}^{+}$.

* If $\delta(G) > 6/11 \cdot \ssize{G}$, then $G$ is 4-colourable. Also, $G$ is either 3-colourable or contains $\overline{C}_{7}$ or $H_{2}^{+}$. In the first two cases, $G$ is homomorphic to $\overline{C}_{7}$.

* If $\delta(G) > 7/13 \cdot \ssize{G}$, then $G$ is either 3-colourable or contains $H_{2}$. Suitable blow-ups of $T_{0}$ show that this is tight.

* If $\delta(G) > 8/15 \cdot \ssize{G}$, then $G$ is either 3-colourable or contains $H_{2}$ or $T_{0}$. Suitable blow-ups of $H_{1}^{++}$ show that this is tight.

* For any $\varepsilon > 0$, there is a constant $C$ such that if $\delta(G) > (1/2 + \varepsilon) \cdot \ssize{G}$, then $G$ is $C$-colourable.

* There are locally bipartite graphs, $G$, with minimum degree $(1/2 - o(1)) \cdot \ssize{G}$ and arbitrarily large chromatic number.

In [11] we considered the structure of locally bipartite graphs with minimum degree down to $6/11$ and, indeed, the first four bullet points of <Ref> are proved there. The final two bullet points are equivalent to the chromatic threshold of locally bipartite graphs being $1/2$: the penultimate one is due to Allen et al. [1] and the final one to Łuczak and Thomassé [16]. In this section we prove the remaining two bullet points. They are immediate from the following two results.

Let $G$ be a locally bipartite graph. If $\delta(G) > 8/15 \cdot \ssize{G}$, then $G$ is either 3-colourable or contains $H_{0}$ or $T_{0}$. If $\delta(G) > 7/13 \cdot \ssize{G}$, then $G$ is either 3-colourable or contains $H_{0}$.

Let $G$ be a locally bipartite graph which contains $H_{0}$. If $\delta(G) > 8/15 \cdot \ssize{G}$, then $G$ contains $H_{2}$.

We prove <Ref> in <Ref> and <Ref> in <Ref> having ruled out some configurations in <Ref>. Some ideas return from [11], although the proof here is largely self-contained. <Ref> displays the graphs of <Ref> as well as some that appear in the proof.

in 0,1,...,6

(*360/7 + 90:1)v_

in 0,1,...,6

(*360/7 + 90:1)v_

in 0,1,...,6

(*360/7 + 90:1)v_

(v_1,v_3,v_5,v_0, v_2,v_4,v_6)

in 0,1,...,6

(*360/7 + 90:1)v_

*$C_{7}^{2} = \overline{C}_{7}$

in 0,1,...,6

(*360/7 + 90:1)v_

(v_1,v_3,v_5,v_0, v_2,v_4,v_6)
(u,v_0 u,v_2 u,v_5)

in 0,1,...,6

(*360/7 + 90:1)v_

(t,v_0 t,u_1 t,u_6)
in 0,2,3,4,5,6

in 0,1,2,3,4,5

in 0,1,...,6

(*360/7 + 90:1)v_

(ul,v_0 ul,v_2 ul,v_3 ur,v_0 ur,v_5 ur,v_3)

in 0,1,...,6

(*360/7 + 90:1)v_

in 0,1,...,6

* All graphs shown are 4-chromatic and all bar $W_{7}$ are locally bipartite.

* The graph $H_{0}$ is isomorphic to the Moser Spindle – the smallest 4-chromatic unit distance graph. $H_{0}$ is also the smallest 4-chromatic locally bipartite graph and so it is natural that it should play such an integral part in many of our results. The graph $\overline{C}_{7}$ is the complement (and also the square) of the 7-cycle.

* Adding a single edge to $H_{0}$ while maintaining local bipartiteness can give rise to two non-isomorphic graphs, one of which is $H_{1}$. The other will appear fleetingly in <Ref>. Adding a single edge to $H_{1}$ while maintaining local bipartiteness gives rise to a unique (up to isomorphism) graph – $H_{2}$. There is only one way to add a single edge to $H_{2}$ and maintain local bipartiteness – this gives $\overline{C}_{7}$. $H_{2}^{+}$ is $H_{2}$ with a degree 3 vertex added. $H_{1}^{++}$ is $H_{1}$ with two degree 3 vertices added.

* Any five vertices of $H_{0}$ contain a triangle or a 5-cycle. In particular, if $G$ is a locally bipartite graph, then any vertex can have at most four neighbours in any copy of $H_{0}$ appearing in $G$. We will use this fact frequently when we have copies of $H_{0}$, $H_{1}$, $H_{2}$ and $\overline{C}_{7}$.

* $\overline{C}_{7}$ and $H_{2}^{+}$ are both edge-maximal locally bipartite graphs.

* $T_{0}$ is a 7-cycle (the outer cycle) together with two vertices each joined to six of the seven vertices in the outer cycle (with the `seventh' vertices two apart) and finally a vertex of degree three is added.

* $W_{7}$, is called the 7-wheel. More generally, a single vertex joined to all the vertices of a $k$-cycle is called a $k$-wheel and is denoted by $W_{k}$. We term any edge from the central vertex to the cycle a spoke of the wheel and any edge of the cycle a rim of the wheel. Note that a graph is locally bipartite exactly if it does not contain any odd wheel (there is no such nice characterisation for a graph being locally tripartite, locally 4-partite, …).

Containment and homomorphisms between the first seven graphs of <Ref> are summarised in <Ref>. Note that a full arrow pointing from $H$ to $G$ signifies that $H$ is a subgraph of $G$ and a dashed arrow from $H$ to $G$ signifies that $H$ is homomorphic to $G$. Furthermore, for two graphs $H$ and $G$ in the diagram, $H$ is homomorphic to $G$ exactly if there is a sequence of arrows starting at $H$ and ending at $G$. We verify <Ref> in the appendix.

(H21) at (0,0)$H_{2}^{+}$;
(blank) [left = of H21]H1;
(C7) [left = of blank]$\overline{C}_{7}$;
(H12) [below = of H21]$H_{1}^{++}$;
(T0) [right = of H12]$T_{0}$;
(H2) [left = of H12]$H_{2}$;
(H1) [below = of H2]$H_{1}$;
(H0) [below = of H1]$H_{0}$;

[-Latex] (H2) – (H21);
[-Latex] (H2) – (C7);
[dashed, -Latex] (H12) – (H21);
[dashed, -Latex] (T0) – (H21);
[-Latex] (H1) – (H2);
[-Latex] (H1) – (H12);
[-Latex] (H0) – (H1);

<Ref> makes various tightness claims, referring to `suitable blow-ups'. These blow-ups are as follows. Note that $0^{+}$ represents some tiny positive weight (we have not deleted the vertices entirely just given them a small weight relative to the rest). We remark that, for example, the blow-up of $T_{0}$ cannot contain a copy of $H_{2}$ as $H_{2}$ is not homomorphic to $T_{0}$.

in 0,1,...,6

(*360/7 + 90:1.5)v_

(v_1,v_3,v_5,v_0, v_2,v_4,v_6)
(u,v_0 u,v_2 u,v_5)

*$H_{2}^{+}$ weighted

in 0,1,...,6

(*360/7 + 90:1.5)v_

(t,v_0 t,u_1 t,u_6)
in 0,2,3,4,5,6

in 0,1,2,3,4,5

[below right = -3pt](u_1)3
[below left = -3pt](u_6)3

*$T_{0}$ weighted

in 0,1,...,6

(*360/7 + 90:1.5)v_

(ul,v_0 ul,v_2 ul,v_3 ur,v_0 ur,v_5 ur,v_3)

*$H_{1}^{++}$ weighted

A fruitful notion of [11] which we will again need is that of dense and sparse pairs of vertices.

A pair of vertices $u, v$ in a graph $G$ is dense if $G_{u, v}$ contains an edge. A pair of vertices $u, v$ in a graph $G$ is sparse if $u$ and $v$ are not adjacent and $G_{u, v}$ does not contain an edge.

In a locally bipartite graph there are no $K_{4}$'s so every pair of vertices is exactly one of `adjacent', `dense' or `sparse'. We borrow from [11] the following three simple but useful lemmas. The final one hints at the importance of $H_{0}$.

Let $G$ be a graph with $\delta(G) > 1/2 \cdot \ssize{G}$ and let $I$ be any largest independent set in $G$. Then, for every $u, v \in I$, the pair $u, v$ is dense.

Let $G$ be a graph with $\delta(G) > 1/2 \cdot \ssize{G}$ and suppose $C$ is an induced 4-cycle in $G$. Then at least one of the non-edges of $C$ is a dense pair.

Let $G$ be a locally bipartite graph which does not contain $H_{0}$. For any vertex $v$ of $G$,

\begin{equation*}
D_{v} := \set{u : \text{the pair } u, v \text{ is dense}}
\end{equation*}

is an independent set of vertices.

§.§ From $H_{0}$ to $H_{2}$ – proof of <Ref>

In this subsection we prove <Ref>. We do so in two steps.

Let $G$ be a locally bipartite graph containing $H_{0}$. If $\delta(G) > 1/2 \cdot \ssize{G}$, then $G$ contains $H_{1}$.

We label a copy of $H_{0}$ in $G$ as below and let $X = \set{a_{0}, a_{1}, \dotsc, a_{6}}$.

in 0,1,...,6

(*360/7 + 90:1)v_

Let $U_{4}$ be the set of vertices with exactly four neighbours in $X$. As mentioned below <Ref>, no vertex in a locally bipartite graph has five neighbours in a copy of $H_{0}$ so all other vertices have at most three neighbours in $X$, and hence

\begin{equation*}
7/2 \cdot \ssize{G} < 7 \delta (G) \leqslant e(X, G) \leqslant 4 \ssize{U_{4}} + 3(\ssize{G} - \ssize{U_{4}}) = 3 \ssize{G} + \ssize{U_{4}},
\end{equation*}

and so

\begin{equation*}
\ssize{U_{4}} > 1/2 \cdot \ssize{G}.
\end{equation*}

Now $\ssize{U_{4}} + d(a_{0}) > \ssize{G}$ and so some vertex $v$ is adjacent to $a_{0}$ and has four neighbours in $X$. Note that $v$ cannot be adjacent to both $a_{1}$, $a_{2}$ as otherwise $va_{0}a_{1}a_{2}$ is a $K_{4}$, so by symmetry we may assume that $v$ is not adjacent to $a_{1}$. Similarly we may assume that $v$ is not adjacent to $a_{5}$. But $v$ has four neighbours in $X$ so must be adjacent to at least one of $a_{2}$, $a_{6}$ – by symmetry we may assume $v$ is adjacent to $a_{2}$.

There are two possibilities: $v$ is adjacent to $a_{0}, a_{2}, a_{3}, a_{4}$, or $v$ is adjacent to $a_{0}, a_{2}, a_{6}$ and one of $a_{3}$, $a_{4}$. Suppose the former case occurs. If $v = a_{5}$, then $a_{3}a_{5}$ is an edge and so $G[X]$ contains $H_{1}$. Similarly if $v = a_{6}$. If $v$ is neither $a_{5}$ nor $a_{6}$, then $G$ contains $H_{1}$ (replace $a_{1}$ by $v$).

Now suppose the latter case occurs. We may assume by symmetry that $v$ is adjacent to $a_{3}$. If $v = a_{4}$, then $a_{0}a_{4}$ is an edge and so $G$ contains a $K_{4}$. If $v = a_{5}$, then $a_{3}a_{5}$ is an edge and so $G[X]$ contains $H_{1}$. If $v$ is neither $a_{4}$ nor $a_{5}$, then $G$ contains the following graph.

in 0,1,...,6

(*360/7 + 90:1)v_

If $v$ is adjacent to $a_{4}$, then $G$ contains a copy of $H_{1}$ (ignore the edge $va_{6}$). Similarly if $a_{3}$ is adjacent to $a_{6}$. Otherwise $va_{6}a_{4}a_{3}$ is an induced 4-cycle in $G$. By <Ref>, at least one of the pairs $v, a_{4}$ and $a_{3}, a_{6}$ is dense. By symmetry we may assume that $v, a_{4}$ is dense: let $a'_{2}a'_{3}$ be an edge in $G_{v, a_{4}}$. Note that $a_{5}$ is not adjacent to $v$ (else $a_{5}a_{6}a_{0}v$ is a $K_{4}$) so $a_{5}$ is neither $a'_{2}$ nor $a'_{3}$. Similarly $a_{0}$ is not adjacent to $a_{4}$ and so $a_{0}$ is neither $a'_{2}$ nor $a'_{3}$. If $a_{6} = a'_{2}$, then $G_{a_{6}}$ contains the 5-cycle $a'_{3}va_{0}a_{5}a_{4}$, which is impossible. Hence, $a'_{2}, a'_{3}$ are distinct from $a_{4}, a_{5}, a_{6}, a_{0}, v$ and so $G[\set{a_{6}, a_{0}, v, a'_{2}, a'_{3}, a_{4}, a_{5}}]$ contains a copy of $H_{1}$ (with apex $a_{6}$). Hence in all cases $G$ contains a copy of $H_{1}$.

Let $G$ be a locally bipartite graph containing $H_{1}$. If $\delta(G) > 8/15 \cdot \ssize{G}$, then $G$ contains $H_{2}$.

Consider a copy of $H_{1}$ with vertices $X = \set{a_{0}, a_{1}, \dotsc, a_{6}}$. We assign weights $\omega : X \rightarrow \ZZN$ as shown in the diagram below, so, for example $\omega(a_{0}) = 2$ and $\omega(a_{1}) = 1$ (recall this notation from <Ref>). We will often use this way of giving weightings by diagram. For each vertex $v \in G$, let $f(v)$ be the total weight of the neighbours of $v$ in $X$.

in 0,1,...,6

(*360/7 + 90:1)v_

[below left](v_3)$a_{3}:1$
[below right](v_4)$a_{4}:1$

We will assume that $G$ does not contain $H_{2}$. We first show that any vertex $v$ has $f(v) \leqslant 6$ and further that if $f(v) = 6$, then $\Gamma(v) \cap X = \set{a_{1}, a_{2}, a_{5}, a_{6}}$.

Let $v$ be a vertex with $f(v) \geqslant 6$. Recall that no vertex in a locally bipartite has five neighbours in a copy of $H_{1}$ so $v$ is adjacent to at most four of the $a_{i}$. Thus, $v$ is adjacent to at least two of the vertices of weight two, that is, to at least two of $a_{0}$, $a_{2}$, $a_{5}$. If $v$ is adjacent to all of $a_{0}, a_{2}, a_{5}$, then $G_{a_{0}}$ contains the odd circuit $va_{5}a_{6}a_{1}a_{2}$. Thus $v$ is adjacent to exactly two of $a_{0}$, $a_{2}$ and $a_{5}$.

Suppose $v$ is adjacent to $a_{0}$. By symmetry we may assume that $v$ is adjacent to $a_{2}$ but not to $a_{5}$. Then $v$ is not adjacent to $a_{1}$, else $va_{0}a_{1}a_{2}$ is a $K_{4}$. Similarly $v$ cannot be adjacent to both $a_{3}$ and $a_{4}$. Hence $v$ is adjacent to $a_{0}$, $a_{2}$, $a_{6}$ and one of $a_{3}$, $a_{4}$. By symmetry, we may assume $v$ is adjacent to $a_{3}$. If $v = a_{5}$, then $a_{2}a_{5}$ is an edge, so $G$ contains $K_{4}$. If $v = a_{4}$, then $a_{0}$ has five neighbours in $X$, a contradiction. If $v$ is neither $a_{4}$ nor $a_{5}$, then $G$ contains $H_{2}$ (replace $a_{1}$ by $v$).

Thus $v$ is not adjacent to $a_{0}$ and so is adjacent to both $a_{2}$ and $a_{5}$. Note $v$ cannot be adjacent to both $a_{3}$, $a_{4}$ else $va_{2}a_{3}a_{4}$ is $K_{4}$, so we may assume that $v$ is adjacent to $a_{1}$. If $v$ were adjacent to one of $a_{3}$, $a_{4}$, then we may assume, by symmetry that $v$ is adjacent to $a_{4}$ and not $a_{3}$. Now $v$ cannot be $a_{0}$ nor $a_{6}$ as it would then have five neighbours in $X$. Hence $G$ contains $H_{2}$ (replace $a_{3}$ by $v$). Therefore $v$ is adjacent to neither $a_{3}$ nor $a_{4}$. But $f(v) \geqslant 6$, so $v$ is adjacent to $a_{1}$, $a_{6}$ and thus $\Gamma(v) \cap X = \set{a_{1}, a_{2}, a_{5}, a_{6}}$.

So every vertex $v$ have $f(v) \leqslant 6$ and furthermore all $v \in \Gamma(a_{0}) \cup \Gamma(a_{3}) \cup \Gamma(a_{4})$ have $f(v) \leqslant 5$. We first claim that there is $i \in \set{3, 4}$ such that $\Gamma(a_{0}, a_{2}, a_{i}) = \varnothing$. If not, there is $a'_{1} \in \Gamma(a_{0}, a_{2}, a_{3})$ and $a''_{1} \in \Gamma(a_{0}, a_{2}, a_{4})$. But then $G_{a_{2}}$ contains the odd circuit $a'_{1} a_{3} a_{4} a''_{1} a_{0}$. Similarly there is $j \in \set{3, 4}$ such that $\Gamma(a_{0}, a_{5}, a_{j}) = \varnothing$.

Next we claim that there is $i \in \set{3, 4}$ with $\Gamma(a_{0}, a_{2}, a_{i}) = \Gamma(a_{0}, a_{5}, a_{i}) = \varnothing$. If not, then without loss of generality there is $a'_{1} \in \Gamma(a_{0}, a_{2}, a_{3})$ and $a'_{6} \in \Gamma(a_{0}, a_{5}, a_{4})$. Certainly, $\Gamma(a'_{1}) \cap X \neq \set{a_{1}, a_{2}, a_{5}, a_{6}}$, so $f(a'_{1}) \leqslant 5$. But $\omega(a_{0}) + \omega(a_{2}) + \omega(a_{3}) = 5$, so $\Gamma(a'_{1}) \cap X = \set{a_{0}, a_{2}, a_{3}}$. Similarly $\Gamma(a'_{6}) \cap X = \set{a_{0}, a_{4}, a_{5}}$. In particular, all of $a_{0}, \dotsc, a_{6}, a'_{1}, a'_{6}$ are distinct. But then $G[\set{a_{0}, a'_{1}, a_{2}, a_{3}, a_{4}, a_{5}, a'_{6}}]$ contains $H_{2}$. Thus without loss of generality $\Gamma(a_{0}, a_{2}, a_{3}) = \Gamma(a_{0}, a_{5}, a_{3}) = \varnothing$. Then $\Gamma(a_{3})$, $\Gamma(a_{0}, a_{2})$, $\Gamma(a_{0}, a_{5})$ are pairwise disjoint (we already showed that $\Gamma(a_{0}, a_{2}, a_{5}) = \varnothing$). Hence the set $Y = \Gamma(a_{3}) \cup \Gamma(a_{0}, a_{2}) \cup \Gamma(a_{0}, a_{5})$ has size

\begin{equation*}
\ssize{Y} = d(a_{3}) + d(a_{0}, a_{2}) + d(a_{0}, a_{5}) \geqslant \delta(G) + 2(2\delta(G) - \ssize{G}) = 5 \delta(G) - 2 \ssize{G}.
\end{equation*}

Now all $v \in Y$ have $f(v) \leqslant 5$. We bound $\omega(X, G)$ from both directions (recalling this notation from <Ref>) to get

\begin{equation*}
10 \delta(G) \leqslant \sum_{x \in X} \omega(x) d(x) = \sum_{v \in G} f(v) \leqslant 5 \ssize{Y} + 6(\ssize{G} - \ssize{Y}) = 6 \ssize{G} - \ssize{Y} \leqslant 8 \ssize{G} - 5 \delta(G),
\end{equation*}

which contradicts $\delta(G) > 8/15 \cdot \ssize{G}$.

These two claims combine to give <Ref>.

§.§ Ruling out sparse pairs being spokes of odd wheels

In this subsection we make a start on the proof of <Ref>, by ruling out the possibility that $G$ contains a sparse pair of vertices which is the spoke of an odd wheel (<Ref>). The following straightforward lemma appeared in [11].

Let $G$ be a locally bipartite graph with $\delta(G) > 1/2 \cdot \ssize{G}$ and which does not contain $H_{0}$. Then $G$ does not contain a sparse pair $u, v$ with $uv$ being the missing spoke of a 5-wheel.

We will use the following technical lemma on various occasions.

Let $G$ be a locally bipartite graph and let $u$ and $v$ be a sparse pair of vertices in $G$. Suppose that $C$ is the shortest odd cycle which both passes through $v$ and satisfies $C \setminus \set{v} \subset \Gamma(u)$ (i.e. $G[C \cup \set{u}]$ contains an odd wheel missing the spoke $uv$). Then every neighbour of $u$ has at most two neighbours in $C$ and if two, then they are two apart on $C$. In particular, $C$ is an induced cycle.

Label the configuration as follows and write $v_{0}$ for $v$ (we consider indices modulo $2k + 1$). Note $C = \set{v, v_{1}, \dotsc, v_{2k}}$.

in 0,1,2,3,4,5,6,7,8

(*360/9 + 90:1)v_

(v_3,v_4) A
(v_5,v_6) B
(v_4,v_5) C

in 1,2,3,6,7,8

[above](v_0)$v = v_{0}$
[right](v_6)$v_{2k - 2}$
[right](v_7)$v_{2k - 1}$

Consider a vertex $x$ which is adjacent to $u$. Suppose that $x$ is adjacent to two vertices in $C$ which are not two apart: $x$ is adjacent to $v_{i}$ and $v_{i + r}$ where $r \in \set{1, 3, 4, \dotsc, k}$. Firstly if $r = 1$, then either $G$ contains the $K_{4}$ $uxv_{i}v_{i + 1}$ or $G_{u, v}$ contains an edge (if one of $v_{i}$ or $v_{i + 1}$ is $v$) which contradicts the sparsity of $u, v$. Secondly if $r > 1$ is odd, then $C' = x v_{i} v_{i + 1} \dotsb v_{i + r}$ is an odd cycle which is shorter than $C$. Either $C'$ is in $G_{u}$ (if $v \not \in C'$) contradicting the local bipartness of $G$ or we have found a shorter odd cycle than $C$ which satisfies the properties of $C$ (if $v \in C'$). Finally if $r > 2$ is even, then $C' = xv_{i + r}v_{i + r + 1} \dotsb v_{i - 1} v_{i}$ is an odd cycle which is shorter than $C$. Again we either obtain an odd cycle in $G_{u}$ or contradict the minimality of $C$. Hence every neighbour of $u$ has at most two neighbours in $C$ and if two, then they are $v_{i}$, $v_{i + 2}$ for some $i$.

All of $v_{1}, \dotsc, v_{2k}$ are neighbours of $u$ so have two neighbours in $C$. Hence $C$ is induced.

Let $G$ be a locally bipartite graph with $\delta(G) > 8/15 \cdot \ssize{G}$ which does not contain $H_{0}$. Any sparse pair in $G$ that is the missing spoke of an odd wheel is the missing spoke of a 7-wheel.

Consider a sparse pair $u, v$ that is the missing spoke of a $(2k + 1)$-wheel. Choose the odd wheel so that $k$ is minimal. Without loss of generality, $u$ is the central vertex and $v$ is in the outer $(2k + 1)$-cycle which we call $C$. <Ref> shows that $k > 2$. We are done if we can show that $k = 3$.

By <Ref>, every neighbour of $u$ has at most two neighbours in $C$. All vertices have at most $2k$ neighbours in $C$ as otherwise $G$ contains a $(2k + 1)$-wheel. Hence,

\begin{align*}
(2k + 1) \delta(G) & \leqslant e(G, C) \leqslant 2 d(u) + 2k(\ssize{G} - d(u)) \\
& = 2k \ssize{G} - (2k - 2) d(u) \leqslant 2k \ssize{G} - (2k - 2) \delta(G),
\end{align*}

\begin{equation*}
\frac{8}{15} < \frac{\delta(G)}{\ssize{G}} \leqslant \frac{2k}{4k - 1},
\end{equation*}

which implies that $k < 4$.

Thus, to rule out sparse pairs being a missing spoke of an odd wheel we only need to rule out there being a sparse pair which is the missing spoke of a 7-wheel. This is where the graph $T_{0}$ becomes relevant. We will prove the following.

Let $G$ be a locally bipartite graph which does not contain $H_{0}$. If either $\delta(G) > 7/13 \cdot \ssize{G}$, or $\delta(G) > 8/15 \cdot \ssize{G}$ and $G$ does not contain $T_{0}$, then $G$ does not contain a sparse pair which is the missing spoke of a 7-wheel.

Let $G$ be a locally bipartite graph which does not contain $H_{0}$ and either satisfies $\delta(G) > 7/13 \cdot \ssize{G}$, or $\delta(G) > 8/15 \cdot \ssize{G}$ and $G$ does not contain $T_{0}$. In a slight abuse of notation we will say that a vertex $u$ is sparse to a cycle $C$ if $u$ is adjacent to $\ssize{C} - 1$ vertices of $C$ and is in a sparse pair with the final vertex. We are required to show that there is no vertex $u$ and no 7-cycle $C$ with $u$ sparse to $C$.

By <Ref>, there is no 5-cycle $C$ and vertex $u$ with $u$ sparse to $C$. Hence, if a vertex $u$ is sparse to a 7-cycle $C$, then, by <Ref>, $C$ is an induced 7-cycle and any neighbour of $u$ has at most two neighbours in $C$.

If a vertex $u$ is sparse to a 7-cycle $C = v_{0}v_{1} \dotsc v_{6}$ with the pair $u, v_{0}$ sparse, then there is some vertex which has six neighbours in $C$ and is adjacent to all of $v_{6}$, $v_{0}$, $v_{1}$.

[of Claim]
First consider the induced 4-cycle $uv_{6}v_{0}v_{1}$. The pair $u, v_{0}$ is sparse, so $\Gamma(u, v_{6}, v_{0}) = \Gamma(v_{0}, v_{1}, u) = \varnothing$. Also $\Gamma(v_{1}, u, v_{6}) = \varnothing$ as otherwise $G_{u}$ contains an odd circuit. Hence all $z \not \in \Gamma(v_{6}, v_{0}, v_{1})$ have at most two neighbours in $\set{u, v_{6}, v_{0}, v_{1}}$.

in 0,1,6

(*360/7 + 90:1)v_

\begin{equation*}
4 \delta(G) \leqslant e(\set{v_{0}, v_{1}, u, v_{6}}, G) \leqslant 3 \ssize{\Gamma(v_{6}, v_{0}, v_{1})} + 2(\ssize{G} - \ssize{\Gamma(v_{6}, v_{0}, v_{1})}),
\end{equation*}

so $\ssize{\Gamma(v_{6}, v_{0}, v_{1})} \geqslant 4 \delta(G) - 2 \ssize{G}$.

If the claim is false, then all vertices in $\Gamma(v_{6}, v_{0}, v_{1})$ have at most five neighbours in $C$. Also note that $\Gamma(u)$ and $\Gamma(v_{6}, v_{0}, v_{1})$ are disjoint and that all vertices have at most six neighbours in $C$ (otherwise $G$ contains a 7-wheel) so,

\begin{align*}
7 \delta(G) & \leqslant e(C, G) \leqslant 2 d(u) + 5\ssize{\Gamma(v_{6}, v_{0}, v_{1})} + 6(\ssize{G} - d(u) - \ssize{\Gamma(v_{6}, v_{0}, v_{1})}) \\
& = 6 \ssize{G} - 4d(u) - \ssize{\Gamma(v_{6}, v_{0}, v_{1})} \leqslant 6 \ssize{G} - 4 \delta(G) - 4 \delta(G) + 2 \ssize{G},
\end{align*}

which contradicts $\delta(G) > 8/15 \cdot \ssize{G}$.

Let $C$ be a 7-cycle such that there is some vertex which is sparse to $C$. Then every vertex with at least six neighbours in $C$ is sparse to $C$.

[of Claim]
Let vertex $u$ be sparse to the 7-cycle $C$ and let $x$ be a vertex with at least six neighbours in $C$. Since $G$ is locally bipartite, $x$ has exactly six neighbours in $C$. Let $y$ be the vertex of $C$ to which $x$ is not adjacent. There is a vertex $u'$ which has six neighbours in $C$ and is adjacent to $y$. Indeed, if $u$ is adjacent to $y$ then take $u' = u$ and if $u$ is not adjacent to $y$, then <Ref> gives the desired $u'$.

Now $\Gamma(u',x)$ contains two consecutive vertices of $C$, so the pair $u'$, $x$ is dense. But $u'$ is adjacent to $y$ so, by <Ref>, the pair $y, x$ cannot be dense. In particular, $x, y$ is sparse and so $x$ is sparse to $C$.

Now fix a 7-cycle $C = v_{0} v_{1} \dotsc v_{6}$ such that there is some vertex which is sparse to $C$. Say vertex $v_{i}$ is lonely if there is some vertex $u$ which is adjacent to all of $C \setminus \set{v_{i}}$ – by the previous claim $u$ is sparse to $C$ and the pair $u, v_{i}$ is sparse.

For all $i$, $v_{i}$ and $v_{i + 2}$ are not both lonely.

[of Claim]
Suppose for contradiction that $v_{1}$ and $v_{6}$ are both lonely: let $u_{1}$ and $u_{6}$ be sparse to $C$ with both the pairs $u_{1}, v_{1}$ and $u_{6}, v_{6}$ sparse. <Ref> shows that any neighbour of $u_{1}$ (or $u_{6}$) has at most two neighbours in $C$. Let $X = \set{u_{1}, u_{6}, v_{0}, \dotsc, v_{6}}$ and give weights, $\omega$, to the vertices in $X$ as shown below.

in 0,1,...,6

(*360/7 + 90:1.5)v_

in 0,2,3,4,5,6

in 0,1,2,3,4,5

[below left](v_3)$v_{3}:1$
[below right](v_4)$v_{4}:1$

For each vertex $v \in G$, let $f(v)$ be the total weight of the neighbours of $v$ in $X$. We shall show that if $v \not \in \Gamma(u_{6}, u_{1}, v_{0})$, then $f(v) \leqslant 10$ and if $v \in \Gamma(u_{6}, u_{1}, v_{0})$, then $f(v) = 13$. Let $v$ be a vertex with $f(v) \geqslant 11$. It suffices to show that $v$ is adjacent to $u_{6}$, $u_{1}$, $v_{0}$ and none of $v_{1}$, …, $v_{6}$.

If $v$ is adjacent to neither $u_{1}$ nor $u_{6}$, then $f(v) \leqslant 11$ with equality only if $v$ is adjacent to all of $C$ which would give a 7-wheel so, in fact, $f(v) \leqslant 10$. Thus, we may assume $v$ is adjacent to $u_{1}$. But then $v$ must have at most two neighbours in $C$. If neither of these is $v_{0}$, then $f(v) \leqslant 4 + 4 + 1 + 1 = 10$. Hence we may assume $v$ is adjacent to both $v_{0}$ and $u_{1}$.

Since $f(v) \geqslant 11$ and $v$ has at most two neighbours in $C$, $v$ must be adjacent to $u_{6}$ as well. Now, $v$ is adjacent to both $u_{1}$ and $v_{0}$ so, by <Ref>, the only other possible neighbour of $v$ in $C$ is one of $v_{2}$ and $v_{5}$. However if $v$ is adjacent to $v_{2}$, then $G_{u_{1}}$ contains the odd circuit $v_{0}vv_{2}v_{3}\dotsc v_{6}$ while if $v$ is adjacent to $v_{5}$, then $G_{u_{6}}$ contains the odd circuit $v_{0}v_{1}\dotsc v_{5}v$. In conclusion, $v$ is adjacent to $u_{1}$, $u_{6}$, $v_{0}$, and no other vertices of $C$.

\begin{equation*}
19 \delta(G) \leqslant \omega(X, G) = \sum_{v \in G} f(v) \leqslant 13 \ssize{\Gamma(v_{0}, u_{1}, u_{6})} + 10 (\ssize{G} - \ssize{\Gamma(v_{0}, u_{1}, u_{6})}),
\end{equation*}

\begin{equation}\label{eq:19}
3 \ssize{\Gamma(v_{0}, u_{1}, u_{6})} \geqslant 19 \delta(G) - 10 \ssize{G}.
\end{equation}

Any $v \in \Gamma(v_{0}, u_{1}, u_{6})$ satisfies $f(v) = 13$ so has only one neighbour in $C$. Also any neighbour of $u_{1}$ has at most two neighbours in $C$. Hence

\begin{align*}
7 \delta(G) & \leqslant e(C, G) \leqslant \ssize{\Gamma(v_{0}, u_{1}, u_{6})} + 2(d(u_{1}) - \ssize{\Gamma(v_{0}, u_{1}, u_{6})}) + 6(\ssize{G} - d(u_{1})) \\
& = 6 \ssize{G} - 4d(u_{1}) - \ssize{\Gamma(v_{0}, u_{1}, u_{6})},
\end{align*}

\begin{equation}\label{eq:11}
\ssize{\Gamma(v_{0}, u_{1}, u_{6})} \leqslant 6 \ssize{G} - 11 \delta(G).
\end{equation}

Now, if $G$ is $T_{0}$-free, then $\Gamma(v_{0}, u_{1}, u_{6}) = \varnothing$ so, by inequality (<ref>), $\delta(G) \leqslant 10/19 \cdot \ssize{G} < 8/15 \cdot \ssize{G}$, a contradiction. On the other hand, combining inequalities (<ref>) and (<ref>) gives

\begin{equation*}
19 \delta(G) - 10 \ssize{G} \leqslant 3 \ssize{\Gamma(v_{0}, u_{1}, u_{6})} \leqslant 18 \ssize{G} - 33 \delta(G),
\end{equation*}

which is a contradiction when $\delta(G) > 7/13 \cdot \ssize{G}$.

We now finish the proof of <Ref>. By the choice of $C$, some $v_{i}$ is lonely. Without loss of generality, $v_{0}$ is lonely. By <Ref>, neither $v_{2}$ nor $v_{5}$ is lonely. By <Ref>, at least one of $v_{3}$ and $v_{4}$ is lonely. By symmetry, we may assume $v_{3}$ is lonely. By <Ref>, $v_{1}$ is not lonely and at most one of $v_{4}$, $v_{6}$ is. Again, by symmetry, we may assume $v_{6}$ is not lonely. In conclusion, $v_{1}$, $v_{2}$, $v_{5}$, $v_{6}$ are all not lonely, $v_{0}$ and $v_{3}$ are lonely and $v_{4}$ may or may not be.

Let $U_{6}$ be the set of vertices with six neighbours in $C$. By <Ref>, any vertex in $U_{6}$ is sparse to $C$ so cannot be adjacent to all of $v_{0}$, $v_{3}$, $v_{4}$ (else some other $v_{i}$ is lonely). In particular,

\begin{equation*}
U_{6} \subset \overline{\Gamma(v_{0})} \cup \overline{\Gamma(v_{3})} \cup \overline{\Gamma(v_{4})}.
\end{equation*}

As $v_{0}$ is lonely, there is a vertex $u$ that is sparse to $C$ with $u, v_{0}$ sparse. No two of $v_{0}, v_{3}, v_{4}$ are two part on $C$ and so, by <Ref>, any neighbour of $u$ is in at least two of $\overline{\Gamma(v_{0})}$, $\overline{\Gamma(v_{3})}$, $\overline{\Gamma(v_{4})}$ and is not in $U_{6}$. Hence

\begin{equation*}
\ssize{U_{6}} + 2d(u) \leqslant \lvert \overline{\Gamma(v_{0})} \rvert + \lvert \overline{\Gamma(v_{3})} \rvert + \lvert \overline{\Gamma(v_{4})} \rvert \leqslant 3 \ssize{G} - 3 \delta(G),
\end{equation*}

and so $\ssize{U_{6}} \leqslant 3 \ssize{G} - 5 \delta(G)$. Since every neighbour of $u$ has at most two neighbours in $C$,

\begin{align*}
7 \delta(G) & \leqslant e(C, G) \leqslant 6 \ssize{U_{6}} + 2d(u) + 5(\ssize{G} - \ssize{U_{6}} - d(u)) = 5 \ssize{G} + \ssize{U_{6}} - 3d(u) \\
& \leqslant 5 \ssize{G} + 3 \ssize{G} - 5 \delta(G) - 3 \delta(G) = 8 \ssize{G} - 8 \delta(G),
\end{align*}

which contradicts $\delta(G) > 8/15 \cdot \ssize{G}$.

<Ref> and <Ref> together give the result we need.

Let $G$ be a locally bipartite graph which does not contain $H_{0}$. If either $\delta(G) > 7/13 \cdot \ssize{G}$, or $\delta(G) > 8/15 \cdot \ssize{G}$ and $G$ does not contain $T_{0}$, then $G$ does not contain a sparse pair which is the missing spoke of an odd wheel.

§.§ The proof of <Ref>

Here we will prove <Ref> which we restate for convenience.

We start with a locally bipartite graph $G$ which does not contain $H_{0}$ and satisfies either $\delta(G) > 7/13 \cdot \ssize{G}$, or $\delta(G) > 8/15 \cdot \ssize{G}$ and $G$ does not contain $T_{0}$. We are required to show that $G$ is 3-colourable. We may assume that $G$ is edge-maximal: for any sparse pair $u, v$ of $G$, the addition of $uv$ to $G$ introduces an odd wheel, a copy of $H_{0}$ or a copy of $T_{0}$. By <Ref>, the addition of $uv$ to $G$ introduces an odd wheel, a copy of $H_{2}$ (since $G$ itself does not contain $H_{2}$) or a copy of $T_{0}$.

Firstly, if the addition of $uv$ introduces an odd wheel, then, by <Ref>, $uv$ must be a rim of that wheel – this case is depicted in <Ref> below. Secondly, if the addition of $uv$ introduces a copy of $H_{2}$, then that copy of $H_{2}$ less the edge $uv$ must not contain $H_{0}$ – this case is depicted in <Ref> below. Finally, suppose the addition of $uv$ introduces a copy of $T_{0}$ (but not an odd wheel nor a copy of $H_{0}$). Label this copy of $T_{0}$ in $G + uv$ as follows.

in 0,1,...,6

(*360/7 + 90:1.6)v_

(t,v_0 t,u_1 t,u_6)
in 0,2,3,4,5,6

in 0,1,2,3,4,5

[below right = -4pt](u_1)$u_{1}$
[below left = -4pt](u_6)$u_{6}$

Note that $G + uv$ is locally bipartite and does not contain $H_{0}$ so, by <Ref>, for any vertex $x$, $D_{x} = \set{y : \text{the pair } x, y \text{ is dense}}$ is an independent set. In $G + uv$, $t \in D_{v_{1}}$ and $t$ is adjacent to $u_{1}$ so the pair $u_{1}, v_{1}$ is not dense. Also $u_{1}v_{1}$ is not an edge (else $G + uv$ contains a 7-wheel centred at $u_{1}$), so the pair $u_{1}, v_{1}$ is sparse in $G + uv$. Therefore, $u_{1}, v_{1}$ is a sparse pair in $G$. Now, by <Ref>, $G$ does not contain an odd wheel with a sparse spoke so $uv$ must either be one of the edges $v_{i}v_{i + 1}$ or one of the edges $u_{1}v_{i}$. Similarly $uv$ must either be one of the edges $v_{i}v_{i + 1}$ or one of the edges $u_{6}v_{i}$. Thus, in fact, $uv$ must be one of the edges $v_{i}v_{i + 1}$ and by symmetry we may take $i = 0, 1, 2, 3$ – this case is depicted in <Ref> below.

Thus, in $G$, any sparse pair $u, v$ must appear in one of the following configurations (with the labels of $u$ and $v$ possibly swapped).

in 0,1,...,10

(*360/11 + 90:1)v_

(v_1,v_2) A
(v_9,v_10) B
(v_1,v_10) C

in 2,3,...,9

in 0,1,...,6

(*360/7 + 90:1)v_

(v_1,v_3,v_5,v_0, v_2,v_4,v_6)
[above left](v_1)$v$

in 0,1,...,6

(*360/7 + 90:1)v_

(v_1,v_3,v_5,v_0, v_2,v_4,v_6)
[above left](v_1)$u$

in 0,1,...,6

(*360/7 + 90:1)v_

(v_1,v_3,v_5,v_0, v_2,v_4,v_6)

in 0,1,...,6

(*360/7 + 90:1)v_

(v_1,v_3,v_5,v_0, v_2,v_4,v_6)

in 0,1,...,6

(*360/7 + 90:1)v_

(v_3,v_5,v_0, v_2,v_4,v_6)
[above left](v_1)$u$

in 0,1,...,6

(*360/7 + 90:1)v_

(t,v_0 t,u_1 t,u_6)
in 0,2,3,4,5,6

in 0,1,2,3,4,5

[above left](v_1)$v$

in 0,1,...,6

(*360/7 + 90:1)v_

(t,v_0 t,u_1 t,u_6)
in 0,2,3,4,5,6

in 0,1,2,3,4,5

[above left](v_1)$u$

in 0,1,...,6

(*360/7 + 90:1)v_

(t,v_0 t,u_1 t,u_6)
in 0,2,3,4,5,6

in 0,1,2,3,4,5

in 0,1,...,6

(*360/7 + 90:1)v_

(t,v_0 t,u_1 t,u_6)
in 0,2,3,4,5,6

in 0,1,2,3,4,5

We will now consider a largest independent set in $G$: an independent set $I$ of size $\alpha(G)$. We will shortly show that all vertices are either in $I$ or adjacent to all of $I$.

By <Ref>, for every $u \in I$, $I \setminus \set{u} \subset D_{u}$. We now show there is set equality.

For every $u \in I$, $D_{u} = I \setminus \set{u}$

Let $v \in D_{u}$. The set $D_{u}$ is independent, by <Ref>, so $v$ has no neighbour in $I$. But $I$ is a largest independent set so $v$ must be in $I$.

The following definition will be helpful.

A pair of vertices $u, v$ is quasidense if there is a sequence of vertices $u = d_{1}, d_{2}, \dotsc, d_{k}, d_{k + 1} = v$ such that all pairs $d_{i}, d_{i + 1}$ are dense ($i = 1, 2, \dotsc, k$).

<Ref> immediately implies that if the pair $u, v$ is quasidense and $u \in I$, then $v \in I$ also.

Every vertex of $G$ is either in $I$ or adjacent to all of $I$.

Fix a vertex $u \in I$ and let $v$ be any other vertex which is not adjacent to $u$. It suffices to show that $v \in I$. If the pair $u, v$ is (quasi)dense, then $v \in I$ so we may assume that $u, v$ is sparse (and not quasidense), so $u, v$ appears in one of the configurations given in <Ref> (with labels $u$ and $v$ possibly swapped). However in each of <Ref> the pair $u, v$ is quasidense. Hence we may assume that $u, v$ appear in one of <Ref>.

We consider <Ref> together. For ease we label some more of the vertices as follows.

in 0,1,...,6

(*360/7 + 90:1)v_

(v_1,v_3,v_5,v_0, v_2,v_4,v_6)
[above left](v_1)$u$

in 0,1,...,6

(*360/7 + 90:1)v_

(v_1,v_3,v_5,v_0, v_2,v_4,v_6)
[above left](v_1)$v'$

In both cases, the pair $u', w$ is dense and so, by <Ref>, the pair $u', v'$ is not dense. However, $u'v'$ is not an edge, as the pair $u, v$ is sparse, and so $u', v'$ is a sparse pair. But then $uu'vv'$ is an induced 4-cycle in which both non-edges are sparse which contradicts <Ref>.

Finally we consider <Ref> which we label as follows. Let $X = \set{u, v, v', v_{1}, v_{2}, v_{3}, v_{4}}$ and give weights, $\omega$, to the vertices of $X$ as shown.

in 0,1,...,6

((-1)*360/7 + 90:1)v_

(v_3,v_5,v_0, v_2,v_4,v_6)
[above right](v_0)$v_{4}:4$
[above left](v_2)$v_{1}:4$
[below left](v_4)$v_{2}:2$
[below right](v_5)$v_{3}:2$

The pair $v, v'$ is dense, so, if $u, v'$ is quasidense, then $u, v$ is quasidense, a contradiction. Also, as $G$ is $H_{0}$-free, $uv'$ is not an edge. Hence the pair $u, v'$ is sparse and not quasidense. Now $v, v'$ is dense and so, by <Ref>, the pair $vv_{4}$ is not. But $vv_{4}$ is not an edge (else $u, v$ is dense), so $v, v_{4}$ is a sparse pair. Similarly, $v', v_{1}$ is a sparse pair. To summarise, the pairs $u, v$ and $u, v'$ are sparse and not quasidense  and the pairs $v, v_{4}$ and $v', v_{1}$ are sparse. It follows that $G[X]$ contains no further edges.

If a vertex $x$ has five neighbours in $X$, then it is adjacent to three consecutive vertices round the 7-cycle, so $x$ is either adjacent to a triangle or to all of $u, v_{1}, v$ or to all of $v', v_{4}, u$. The first gives a $K_{4}$ while the latter two contradict the pairs $u, v$ and $u, v'$ being sparse. Hence all vertices have at most four neighbours in $X$.

For each vertex $x$ in $G$, let $f(x)$ be the total weight of the neighbours of $x$ in $X$. Now

\begin{equation*}
\sum_{x \in G} f(x) = \omega(X, G) \geqslant 15 \delta(G) > 8 \ssize{G},
\end{equation*}

so some vertex $x$ has $f(x) \geqslant 9$. Certainly $x$ must be adjacent to at least one of $v_{1}$, $v_{4}$ and, as noted above, $x$ has at most four neighbours in $X$. As $G[X]$ contains no further edges, $x \not \in X$.

Suppose that $x$ is adjacent to both $v_{1}$, $v_{4}$ so the pair $x, u$ is dense. As $v, v_{4}$ is sparse, $x$ is not adjacent to $v$. As $v', v_{1}$ is sparse, $x$ is not adjacent to $v'$. If $x$ is adjacent to $v_{2}$, then $x, v$ is dense so $u, v$ is quasidense, a contradiction. If $x$ is adjacent to $v_{3}$, then $x, v'$ is dense so $u, v'$ is quasidense, a contradiction. Thus $\Gamma(x) \cap X = \set{v_{1}, v_{4}}$, so $f(x) = 8$, a contradiction.

Otherwise we may assume, by symmetry, that $x$ is adjacent to $v_{1}$ but not to $v_{4}$. Now $f(x) \geqslant 9$ and $x$ has at most four neighbours in $X$, so $x$ must be adjacent to both $v_{2}$ and $v_{3}$ and to one of $u$, $v$, $v'$. As $G$ is $K_{4}$-free, $x$ is not adjacent to $v$ nor to $v'$, so $x$ is adjacent to $u$. But then both the pairs $x, v_{4}$ and $x, v'$ are dense so $D_{x}$ is not independent, contradicting <Ref>.

[of <Ref>]
Let $u \in I$. <Ref> gives $G[V(G) \setminus I] = G_{u}$, so $G[V(G) \setminus I]$ is 2-colourable. Using a third colour for the independent set $I$ gives a 3-colouring of $G$.

§ LOCALLY $B$-PARTITE GRAPHS

In this section we prove <Ref> in the case $a = 1$, showing that, for $b \geqslant 3$, any locally $b$-partite graph $G$ with minimum degree greater than $(1 - 1/(b + 1/7)) \cdot \ssize{G}$ is $(b + 1)$-colourable.

The proof of this (which appears in <Ref>) will be an induction upon $b$, with some ideas from the proof of <Ref> persisting. We first generalise dense and sparse pairs.

We say a pair of vertices $u, v$ is $b$-dense if $G_{u, v}$ contains a $b$-clique (so $uv$ is a missing edge from a $K_{b + 2}$) and is $b$-sparse if $u$ and $v$ are not adjacent and $G_{u, v}$ does not contain a $b$-clique.

Note that 2-dense and 2-sparse are exactly what was referred to as dense and sparse in <Ref>. Also any pair of vertices in a locally $b$-partite graph is exactly one of `adjacent', `$b$-dense' and `$b$-sparse'. As before, we will characterise in what configurations a $b$-sparse pair of vertices can lie. First, we will prove the following lemma which will be helpful for lifting results from the locally bipartite case.

Let $b$, $s$ be positive integers and $\gamma$ any real with $b + \gamma > s$. Let $G$ be a graph with $\delta(G) > (1 - 1/(b + \gamma)) \cdot \ssize{G}$. For any $s$-set $X \subset V(G)$, we have

\begin{align*}
\ssize{G_{X}} & \geqslant s \delta(G) - (s - 1) \ssize{G} > \bigl(1 - \tfrac{s}{b + \gamma}\bigr) \cdot \ssize{G}, \text{ and}\\
\delta(G_{X}) & > \big(1 - \tfrac{1}{b - s + \gamma}\big) \cdot \ssize{G_{X}}.
\end{align*}

Let $X = \set{x_{1}, \dotsc, x_{s}}$. Note that for each $v \in V(G)$

\begin{equation*}
\mathds{1}(v \in G_{X}) \geqslant \mathds{1}(vx_{1} \in E(G)) + \dotsb + \mathds{1}(vx_{s} \in E(G)) - (s - 1),
\end{equation*}

and summing over $v \in V(G)$ gives

\begin{equation*}
\ssize{G_{X}} \geqslant s \delta(G) - (s - 1) \ssize{G} > s\bigl(1 - \tfrac{1}{b + \gamma}\bigr) \ssize{G} - (s - 1) \ssize{G} = \bigl(1 - \tfrac{s}{b + \gamma}\bigr) \cdot \ssize{G}.
\end{equation*}

Note that $\delta(G_{X}) \geqslant \delta(G) - (\ssize{G} - \ssize{G_{X}}) = \ssize{G_{X}} - (\ssize{G} - \delta(G))$ so

\begin{align*}
\frac{\delta(G_{X})}{\ssize{G_{X}}} & \geqslant 1 - \frac{\ssize{G} - \delta(G)}{\ssize{G}} \cdot \frac{\ssize{G}}{\ssize{G_{X}}} > 1 - \biggl(1 - \frac{\delta(G)}{\ssize{G}}\biggr) \cdot \frac{1}{1 - s/(b + \gamma)} \\
& > 1 - \frac{1}{b + \gamma} \cdot \frac{1}{1 - s/(b + \gamma)} = 1 - \frac{1}{b + \gamma - s}.\qedhere
\end{align*}

If, in <Ref>, $X$ is an $s$-clique and $G$ is locally $b$-partite, then $G_{X}$ is $(b - s + 1)$-colourable and for any $u, v \in G_{X}$, if the pair $u, v$ is $b$-sparse in $G$, then $u, v$ is $(b - s)$-sparse in $G_{X}$. (The former can be seen by taking a vertex $x \in X$ and noting that $G_{x}$ is $b$-colourable and contains the $(s - 1)$-clique $X - \{x\}$ joined to $G_{X}$; the latter by noting that if vertices $u, v \in G_{X}$ form a $(b - s)$-dense pair in $G_{X}$, then they form a $b$-dense pair in $G$.)

We given an easy extension to <Ref> which demonstrates the use of the previous lemma for lifting results.

Let $b \geqslant 2$ be an integer and $G$ be a graph with $\delta(G) > (1 - 1/b) \cdot \ssize{G}$. If $C$ is an induced 4-cycle in $G$ and $G_{C}$ contains a $(b - 2)$-clique, then at least one of the non-edges of $C$ is a $b$-dense pair.

If $b = 2$, this is just <Ref>. Let $b \geqslant 3$ and $K$ be a $(b - 2)$-clique adjacent to all of $C$. Then applying <Ref> with $X = K$, $s = b - 2$, and $\gamma = 0$ gives $\delta(G_{K}) > (1 - 1/2) \cdot \ssize{G_{K}} = 1/2 \cdot \ssize{G_{K}}$. Hence, by <Ref>, one of the non-edges of $C$ is a dense pair in $G_{K}$ so is a $b$-dense pair in $G$.

The next lemma extends <Ref> and partly explains why the situation for locally $b$-partite is simpler for $b \geqslant 3$ than for $b = 2$. <Ref> said that in any locally bipartite $H_{0}$-free graph, the set of vertices which form a dense pair with a fixed vertex are an independent set. Here, in place of $H_{0}$-free, we give a minimum degree condition which guarantees this – for $b \geqslant 3$ this minimum degree condition falls below the chromatic threshold so is, for our purposes, automatic. When $b = 2$, this minimum degree condition is 4/7, which corresponds to $\overline{C}_{7}$.

Let $b \geqslant 2$ be an integer and $G$ be a locally $b$-partite graph with $\delta(G) > 2b/(2b + 3) \cdot \ssize{G}$. For each vertex $v$ of $G$,

\begin{equation*}
D_{v} := \set{u : \text{the pair } u, v \text{ is } b\text{-dense}}
\end{equation*}

is an independent set of vertices.

Suppose that in fact there are vertices $v$, $u_{1}$ and $u_{2}$ with both pairs $v, u_{1}$ and $v, u_{2}$ $b$-dense as well as $u_{1}$ adjacent to $u_{2}$. Let $Q_{1}$ and $Q_{2}$ be $b$-cliques in $G_{vu_{1}}$ and $G_{vu_{2}}$ respectively. Choose $Q_{1}$ and $Q_{2}$ so that $\ell = \ssize{V(Q_{1}) \cap V(Q_{2})}$ is maximal.

Firstly if $\ell \geqslant 1$, then fix $y \in V(Q_{1}) \cap V(Q_{2})$. Now $G_{y}$ contains

in 0,1,...,5

(*360/5 + 90:1.5)v_

(K1) at (v_1)$K_{b - \ell}$;
(K2) at (v_4)$K_{b - \ell}$;
(K) at (0,0)$K_{\ell - 1}$;
[line width = 0.6pt](v_0) – (K1);
[line width = 0.6pt](K1) – (v_2);
[line width = 0.6pt](v_3) – (K2);
[line width = 0.6pt](K2) – (v_0);
[line width = 0.6pt](K) – (v_0);
[line width = 0.6pt](K) – (K1);
[line width = 0.6pt](K) – (v_2);
[line width = 0.6pt](K) – (v_3);
[line width = 0.6pt](K) – (K2);

[below left](v_2)$u_{1}$
[below right](v_3)$u_{2}$

The pair $v, u_{1}$ is $(b - 1)$-dense in $G_{y}$ so in any $b$-colouring of $G_{y}$, $v$ and $u_{1}$ are the same colour. Similarly in any $b$-colouring of $G_{y}$, $v$ and $u_{2}$ are the same colour. In particular, $G_{y}$ is not $b$-colourable which contradicts the local $b$-colourability of $G$.

Hence $\ell = 0$. Let $X = V(Q_{1}) \cup V(Q_{2}) \cup \set{v, u_{1}, u_{2}}$ which is a set of $2b + 3$ vertices. As $\delta(G) > 2b/(2b + 3) \cdot \ssize{G}$, some vertex has at least $2b + 1$ neighbours in $X$ – call this vertex $x$. As $G_{x}$ is $K_{b + 1}$-free, $x$ has a non-neighbour $x_{1} \in V(Q_{1}) \cup \set{u_{1}}$ and a non-neighbour $x_{2} \in V(Q_{2}) \cup \set{u_{2}}$. These must be the only non-neighbours of $x$ in $X$. In particular, $x$ is adjacent to $v$ and so, as $G_{x}$ is $K_{b + 1}$-free, $x_{1}$ must be in $V(Q_{1})$ and $x_{2}$ must be in $V(Q_{2})$. In particular, $Q'_{1} = Q_{1} - \set{x_{1}} + \set{x}$ is a $b$-clique in $G_{v, u_{1}}$ and $Q'_{2} = Q_{2} - \set{x_{2}} + \set{x}$ is a $b$-clique in $G_{v, u_{2}}$. But $\ssize{V(Q'_{1}) \cap V(Q'_{2})} = 1$ which contradicts the maximality of $\ell$.

Note that

\begin{equation*}
1 - \tfrac{1}{b} \geqslant \tfrac{2b}{2b + 3},
\end{equation*}

for all $b \geqslant 3$. We are only interested in locally $b$-partite graphs with $\delta(G) > (1 - 1/b) \cdot \ssize{G}$ (the chromatic threshold) and the conclusion of <Ref> holds for all such graphs.

§.§ Ruling out configurations

In this section, we will rule out various configurations from locally $b$-partite graphs in a similar vein to <Ref>. The motivation for ruling out these particular configurations can be found at the start of our proof in <Ref>.

Fix an integer $b \geqslant 3$, let $G$ be a locally $b$-partite graph with $\delta(G) > (1 - 1/(b + 1/7)) \cdot \ssize{G}$ and let $u, v$ be a $b$-sparse pair in $G$. Then $G + uv$ does not contain a $K_{b - 1} + C_{\text{odd}}$ where at least one of $u$, $v$ is in the $K_{b - 1}$.

We will prove this for $b = 3$ and then use the lifting lemma for larger $b$.

For $b = 3$, $G$ is a locally tripartite graph with $\delta(G) > 15/22 \cdot \ssize{G} > 2/3 \cdot \ssize{G}$ and $u, v$ is a 3-sparse pair in $G$. Suppose the conclusion does not hold. Each neighbourhood of $G$ is 3-colourable so does not contain an odd wheel. In particular, $G$ does not contain $K_{2} + C_{\text{odd}}$, and so $G$ contains one of the following two configurations (corresponding to whether only one of $u, v$ is in the clique or they both are). In the left figure, $x$ is adjacent to all vertices inside the ring, and in the right figure, $u$ and $v$ are adjacent to all vertices inside the ring. In future, we will use rings in this way.

in 0,1,2,3,4,5,6,7,8

(*360/9 + 90:1)v_

(v_3,v_4) A
(v_5,v_6) B
(v_4,v_5) C

in 1,2,3,6,7,8

in 0,1,2,3,4,5,6,7,8

(*360/9 + 90:1)v_

(v_3,v_4) A
(v_5,v_6) B
(v_4,v_5) C

(u,u' v,v')

We deal with the left-hand configuration first. Since $G_{x}$ is 3-colourable, $G_{x}$ is locally bipartite, $H_{0}$-free and $T_{0}$-free. Applying <Ref> with $X = \set{x}$ and $\gamma = 1/7$ gives $\delta(G_{x}) > (1 - 1/(2 + 1/7)) \cdot \ssize{G_{x}} = 8/15 \cdot \ssize{G_{x}}$ so, by <Ref>, $G_{x}$ does not contain a sparse pair which is the missing spoke of an odd wheel. In particular, the pair $u, v$ is dense in $G_{x}$ so must be 3-dense in $G$, a contradiction.

Now consider the right-hand configuration. We may assume that $k$ is minimal. As the pair $u, v$ is 3-sparse, $k > 1$. Let $X = \set{u, v, v_{0}, v_{1}, \dotsc, v_{2k}}$. We consider indices modulo $2k$.

First consider a vertex $x$ adjacent to both $u$ and $v$. We claim that $x$ is adjacent to at most two of the $v_{i}$ so has at most four neighbours in $X$. For $r \not \in \set{0, \pm 2}$, $x$ cannot be adjacent to both $v_{i}$ and $v_{i + r}$. Indeed if $r = \pm 1$, then $xv_{i}v_{i + r}$ is a triangle in $G_{u,v}$ while other $r$ give a shorter odd cycle in $G_{u,v}$.

Now consider any other vertex $x$: this is not adjacent to at least one of $u$ or $v$. If this is the only non-neighbour of $x$ in $X$ then $G_{x}$ contains an odd-wheel, which is not 3-colourable. Thus all vertices have at most $2k + 1$ neighbours in $X$. Hence,

\begin{align*}
(2k + 3) \delta(G) & \leqslant e(G, X) \leqslant 4 \ssize{G_{u, v}} + (2k + 1)(\ssize{G} - \ssize{G_{u, v}}) \\
& \leqslant (2k + 1) \ssize{G} - (2k - 3)(2 \delta(G) - \ssize{G}) = (4k -2) \ssize{G} - (4k - 6) \delta(G),
\end{align*}

which contradicts $\delta(G) > 2/3 \cdot \ssize{G}$.

Suppose now that $b \geqslant 4$ and that $G + uv$ does contain a $K_{b - 1} + C_{\text{odd}}$ where at least one of $u, v$ is in the $K_{b - 1}$. The $(b - 1)$-clique contains a $(b - 3)$-clique, $L$, with $u, v \not \in L$. Thus $L$ is a $(b - 3)$-clique in $G$.

Now $G_{L}$ is a 4-colourable (so locally tripartite) graph in which $u, v$ is 3-sparse (by <Ref>). Applying <Ref> with $X = L$, $\gamma = 1/7$ gives $\delta(G_{L}) > (1 - 1/(b - (b - 3) + 1/7)) \cdot \ssize{G_{L}} = 15/22 \cdot \ssize{G_{L}}$. Finally, $G_{L} + uv$ contains a $K_{2} + C_{\text{odd}}$ where at least one of $u$, $v$ is in the 2-clique. This contradicts the result for $b = 3$.

Fix an integer $b \geqslant 3$, let $G$ be a locally $b$-partite graph with $\delta(G) > (1 - 1/(b + 1/7)) \cdot \ssize{G}$ and let $u, v$ be a $b$-sparse pair in $G$. Then $G + uv$ does not contain a $K_{b - 2} + H_{0}$ where at least one of $u$, $v$ is in the $K_{b - 2}$.

We split into two cases depending upon whether only one of $u$, $v$ is in the $(b - 2)$-clique or both are. In each case we will prove the result for small $b$ and then use the lifting lemma for larger $b$.

Suppose only one of $u$, $v$ is in the $(b - 2)$-clique. We first prove the result for $b = 3$: $G$ is locally tripartite, the pair $u, v$ is 3-sparse, and $\delta(G) > 15/22 \cdot \ssize{G} > 2/3 \cdot \ssize{G}$. Suppose the conclusion does not hold. Since $G$ does not contain $K_{1} + H_{0}$, $G$ contains the configuration shown in <Ref> where $u$ is adjacent to all of the copy of $H_{0}$ except for one vertex ($v$) to which is it 3-sparse.

in 0,1,...,6

(*360/7 + 90:1)v_

[densely dashed](u,u')

in 0,1,...,6

(*360/7 + 90:1)v_

(u,u' v,v')

Let $X$ be the vertex set of the $H_{0}$. First consider a vertex $x$ adjacent to $u$: $x$ cannot be adjacent to a triangle or 5-cycle in $G[X]$ otherwise $G + uv$ contains a 2-clique $ux$ joined to an odd cycle which contradicts <Ref>. In particular, any neighbour of $u$ has at most four neighbours in $X$.

Consider any vertex $x$: $\chi(G[X]) = 4$ so $x$ has at most six neighbours in $X$. Hence

\begin{equation*}
7 \delta(G) \leqslant e(G,X) \leqslant 4 d(u) + 6(\ssize{G} - d(u)) \leqslant 6 \ssize{G} - 2\delta(G),
\end{equation*}

which contradicts $\delta(G) > 15/22 \cdot \ssize{G} > 2/3 \cdot \ssize{G}$.

Now let $b \geqslant 4$ and suppose $G + uv$ does contain a $K_{b - 2} + H_{0}$ where exactly one of $u$, $v$ (say $u$) is in the $(b - 2)$-clique. Graph $G$ is locally $b$-partite so does not contain $K_{b - 2} + H_{0}$, so $v$ is in the copy of $H_{0}$. Let $L$ be the $(b - 2)$-clique without $u$: $L$ is a $(b - 3)$-clique in $G$ and so $G_{L}$ is 4-colourable and so locally tripartite. Also, by <Ref>, $\delta(G_{L}) > 15/22 \cdot \ssize{G_{L}}$ and, by <Ref>, $u, v$ is a 3-sparse pair in $G_{L}$. Finally $G_{L} + uv$ contains $u + H_{0}$, which contradicts the result we just proved for $b = 3$.

Now consider the second case, where both $u$ and $v$ are in the $(b - 2)$-clique: this means that $b \geqslant 4$. We first prove the result for $b = 4$: $G$ is locally 4-partite, the pair $u, v$ is 4-sparse, and $\delta(G) > 22/29 \cdot \ssize{G} > 3/4 \cdot \ssize{G}$. If the result is false, then $G$ contains the configuration shown in <Ref>.

Let $X = V(H_{0}) \cup \set{u}$ – a set of eight vertices. First consider a vertex $x$ adjacent to both $u$ and $v$: $x$ cannot be adjacent to a triangle or 5-cycle in $V(H_{0})$ as this would contradict <Ref>. Hence $x$ has at most four neighbours in $V(H_{0})$ and so at most five in $X$.

Since $G[X]$ is not 4-colourable, all vertices have at most seven neighbours in $X$. Hence

\begin{align*}
8 \delta(G) & \leqslant 5 \ssize{G_{u, v}} + 7(\ssize{G} - \ssize{G_{u, v}}) \\
& \leqslant 7 \ssize{G} - 2(2 \delta(G) - \ssize{G}) = 9 \ssize{G} - 4 \delta(G),
\end{align*}

which contradicts $\delta(G) > 22/29 \cdot \ssize{G} > 3/4 \cdot \ssize{G}$.

Finally suppose $b \geqslant 5$ and $G + uv$ does contain a $K_{b - 2} + H_{0}$ where both of $u$, $v$ are in the $(b - 2)$-clique. Let $L$ be the $(b - 2)$-clique without $u$, $v$: $L$ is a $(b - 4)$-clique in $G$ so, by <Ref>, $G_{L}$ is 5-colourable and so locally 4-partite. Also, by <Ref>, $\delta(G_{L}) > 22/29 \cdot \ssize{G_{L}}$ and $u, v$ is a 4-sparse pair in $G_{L}$. Finally $G_{L} + uv$ contains $uv + H_{0}$, which contradicts the result we obtained for $b = 4$.

Fix an integer $b \geqslant 3$, let $G$ be a locally $b$-partite graph with $\delta(G) > (1 - 1/(b + 1/7)) \cdot \ssize{G}$ and let $u,v$ be a $b$-sparse pair in $G$. Then $G + uv$ does not contain a $K_{b - 2} + T_{0}$ where at least one of $u$, $v$ is in the $(b - 2)$-clique.

Again we split into two cases depending upon whether only one of $u$, $v$ is in the $(b - 2)$-clique or both are and in each case we will prove the result for small $b$ and then use the lifting lemma for larger $b$.

Suppose only one of $u$, $v$ is in the $(b - 2)$-clique. We first prove the result for $b = 3$: $G$ is locally tripartite, the pair $u, v$ is 3-sparse, and $\delta(G) > 15/22 \cdot \ssize{G} > 2/3 \cdot \ssize{G}$. Suppose the conclusion does not hold. Since $G$ does not contain $K_{1} + T_{0}$, $G$ contains the configuration shown in <Ref> (labels have been added for convenience) where $u$ is adjacent to all of the copy of $T_{0}$ except for one vertex ($v$) to which it is 3-sparse.

in 0,1,...,6

(*360/7 + 90:1.6)v_

(t,v_0 t,u_1 t,u_6)
in 0,2,3,4,5,6

in 0,1,2,3,4,5

[below right = -4pt](u_1)$u_{1}$
[below left = -4pt](u_6)$u_{6}$

[densely dashed](u,u')

in 0,1,...,6

(*360/7 + 90:1.6)v_

(t,v_0 t,u_1 t,u_6)
in 0,2,3,4,5,6

in 0,1,2,3,4,5

[below right = -4pt](u_1)$u_{1}$
[below left = -4pt](u_6)$u_{6}$

(u,u' v,v')

We first show that at least one of the pairs $u_{1}, v_{1}$ and $u_{6}, v_{6}$ is 3-sparse. Neither of these is an edge as otherwise $G + uv$ contains $u$ joined to a 7-wheel which contradicts <Ref>. If $v \not \in \set{u_{1}, u_{6}, v_{3}, v_{4}}$, then $u_{1}, u_{6}$ is 3-dense (triangle $uv_{3}v_{4}$) and so $u_{1}, v_{1}$ is 3-sparse, by <Ref>. On the other hand, suppose $v \in \set{u_{1}, u_{6}, v_{3}, v_{4}}$ – by symmetry we may assume $v \neq u_{6}$. Then $v_{1}, t$ is 3-dense (triangle $uv_{0}u_{6}$) and so $u_{1}, v_{1}$ is 3-sparse, by <Ref>. From now on, we will assume that the pair $u_{1}, v_{1}$ is 3-sparse in $G$.

Let $G' = G + uv$ – we work in $G'$. From <Ref>, $G'_{u}$ contains no odd wheel, i.e. is locally bipartite, and from <Ref>, $G'_{u}$ is $H_{0}$-free. Now $u_{1}v_{1}$ is not an edge (else there is a 7-wheel in $G'_{u}$) and the pair $v_{1}, t$ is 2-dense in $G'_{u}$ so $u_{1}, v_{1}$ is 2-sparse in $G'_{u}$, by <Ref>. In particular, by <Ref>, $u_{1}v_{1}$ is not a missing spoke of a 5-wheel in $G'_{u}$. Hence, by <Ref>, any neighbour of $u_{1}$ in $G'_{u}$ is adjacent to at most two of the $v_{i}$. In particular, any common neighbour of $u$ and $u_{1}$ in $G'$ is adjacent to at most two of the $v_{i}$.

Let $X = \set{u,u_{1},v_{0},v_{1}, \dotsc, v_{6}}$. What we have just shown gives that any common neighbour of $u$ and $u_{1}$ in $G'$ has at most four neighbours in $X$. Consider a vertex $x$ which is not adjacent to both $u$ and $u_{1}$: $x$ cannot be adjacent to all of $X \setminus \set{u_{1}}$ otherwise $G'_{u, x}$ contains a 7-cycle which contradicts <Ref>. Also $x$ cannot be adjacent to all of $X \setminus \set{u}$ as otherwise $G'_{x} = G_{x}$ contains a 7-wheel missing the spoke $u_{1}v_{1}$ which is 3-sparse in $G$. This again contradicts <Ref>. Hence, any vertex has at most seven neighbours in $X$. Thus,

\begin{align*}
9 \delta(G) & \leqslant 9 \delta(G') \leqslant 4 \lvert G'_{u, u_{1}} \rvert + 7(\ssize{G'} - \lvert G'_{u, u_{1}} \rvert) = 7 \ssize{G} - 3 \lvert G'_{u, u_{1}} \rvert \\
& \leqslant 7 \ssize{G} - 3 \ssize{G_{u, u_{1}}} \leqslant 7 \ssize{G} - 3(2\delta(G) - \ssize{G}) = 10 \ssize{G} - 6 \delta(G),
\end{align*}

which contradicts $\delta(G) > 2/3 \cdot \ssize{G}$.

Now let $b \geqslant 4$ and suppose $G + uv$ does contain a $K_{b - 2} + T_{0}$ where exactly one of $u$, $v$ (say $u$) is in the $(b - 2)$-clique. Graph $G$ is locally $b$-partite so does not contain $K_{b - 2} + T_{0}$ so $v$ is in the copy of $T_{0}$. Let $L$ be the $(b - 2)$-clique without $u$: $L$ is a $(b - 3)$-clique in $G$ and so $G_{L}$ is 4-colourable and so locally tripartite. Also, by <Ref>, $\delta(G_{L}) > 15/22 \cdot \ssize{G_{L}}$ and $u, v$ is a 3-sparse pair in $G_{L}$. Finally $G_{L} + uv$ contains $u + T_{0}$, which contradicts the result we just proved for $b = 3$.

Now consider the second case, where both $u$ and $v$ are in the $(b - 2)$-clique: this means that $b \geqslant 4$. We first prove the result for $b = 4$: $G$ is locally 4-partite, the pair $u, v$ is 4-sparse, and $\delta(G) > 22/29 \cdot \ssize{G} > 3/4 \cdot \ssize{G}$. If the result is false, then $G$ contains the configuration shown in <Ref> (labels have been added for convenience).

By <Ref>, $G_{u, v}$ is locally bipartite and $H_{0}$-free. By <Ref>, $\delta(G_{u, v}) > 1/2 \cdot \ssize{G_{u, v}}$. Since $G_{u, v}$ does not contain an odd wheel, $u_{1}v_{1}$ is not an edge. Also $v_{1}, t$ is a 2-dense pair, $tu_{1}$ is an edge and $G_{u, v}$ is $H_{0}$-free, so, by <Ref>, $u_{1}, v_{1}$ is a 2-sparse pair in $G_{u, v}$. Similarly $u_{6}, v_{6}$ is 2-sparse in $G_{u, v}$.

Now let $X = \set{u, u_{1}, u_{6}, v_{0}, \dotsc, v_{6}}$ (note that this does not contain $t$ or $v$). Within $G_{u, v}$, $u_{1}$ together with the $v_{i}$ form a 7-wheel missing the spoke $u_{1}v_{1}$ which is a sparse pair. Since $G_{u,v}$ is locally bipartite with $\delta(G_{u, v}) > 1/2 \cdot \ssize{G_{u, v}}$, <Ref> implies that $G_{u, v}$ does not contain any 5-wheels missing a sparse spoke. Hence, by <Ref>, any neighbour of $u_{1}$ in $G_{u, v}$ is adjacent to at most two of the $v_{i}$. Thus, any neighbour of $u$, $v$, $u_{1}$ has at most five neighbours in $X$ (two amongst $v_{i}$ together with possibly $u_{1}, u_{6}, u$). Similarly any neighbour of $u$, $v$, $u_{6}$ has at most five neighbours in $X$. Next consider a vertex $x$ adjacent to both $u$, $v$ but to neither $u_{1}$ nor $u_{6}$. As $G_{u,v}$ is locally bipartite, $x$ is adjacent to at most six of the $v_{i}$ so $x$ has at most seven neighbours in $X$. Finally $\chi(G[X]) = 5$ so all vertices have at most nine neighbours in $X$. Hence

\begin{align*}
10 \delta(G) & \leqslant 5\ssize{\Gamma(u, v, u_{1}) \cup \Gamma(u, v, u_{6})} + 7(\ssize{G_{u, v}} - \ssize{\Gamma(u, v, u_{1}) \cup \Gamma(u, v, u_{6})}) + 9(\ssize{G} - \ssize{G_{u, v}}) \\
& = 9 \ssize{G} - 2 \ssize{G_{u, v}} - 2 \ssize{\Gamma(u, v, u_{1}) \cup \Gamma(u, v, u_{6})} \leqslant 9 \ssize{G} - 2 \ssize{G_{u, v}} - 2 \ssize{G_{u, v, u_{1}}} \\
& \leqslant 9 \ssize{G} - 2(2 \delta(G) - \ssize{G}) - 2(3 \delta(G) - 2 \ssize{G}) = 15 \ssize{G} - 10 \delta(G),
\end{align*}

which contradicts $\delta(G) > 3/4 \cdot \ssize{G}$.

Now let $b \geqslant 5$ and suppose $G + uv$ does contain a $K_{b - 2} + T_{0}$ where both of $u$, $v$ are in the $(b - 2)$-clique. Let $L$ be the $(b - 2)$-clique without $u$, $v$: $L$ is a $(b - 4)$-clique in $G$ and so $G_{L}$ is 5-colourable and so locally 4-partite. Also, by <Ref>, $\delta(G_{L}) > 22/29 \cdot \ssize{G_{L}}$ and, by <Ref>, the pair $u, v$ is 4-sparse in $G_{L}$. Finally $G_{L} + uv$ contains $uv + T_{0}$, which contradicts the result just proved for $b = 4$.

§.§ Finishing the proof

Here we will prove <Ref> for locally $b$-partite graphs.

Take an edge-maximal locally $b$-partite graph $G$ with $\delta(G) > (1 - 1/(b + 1/7)) \cdot \ssize{G}$. We need to show that $G$ is $(b + 1)$-colourable. We may assume by induction that the theorem holds for all $b'$ with $3 \leqslant b' < b$ (if there are any).

We first show that for any $b$-sparse pair $u, v$ of $G$, $G' = G + uv$ contains a $(b - 2)$-clique $K$ with $G'_{K}$ not 3-colourable. Indeed, for $b = 3$, $G'$ is not locally tripartite (by edge-maximality) so there is a vertex  in $G'$ whose neighbourhood is not 3-colourable. Take $K$ to be this vertex. For $b > 3$, $G'$ is not locally $b$-partite so contains a vertex $w_{1}$ with $G'_{w_{1}}$ not $b$-colourable. Applying <Ref> with $X = \set{w_{1}}$ and $\gamma = 1/7$ gives

\begin{equation*}
\delta(G'_{w_{1}}) > \biggl(1 - \frac{1}{b - 1 + 1/7}\biggr) \cdot \lvert G'_{w_{1}} \rvert.
\end{equation*}

By the induction hypothesis, if $G'_{w_{1}}$ was locally $(b - 1)$-partite, then it would be $b$-colourable. In particular, $G'_{w_{1}}$ is not locally $(b - 1)$-partite and so there is a vertex $w_{2}$ in $G'_{w_{1}}$ with $G'_{w_{1}, w_{2}}$ not $(b - 1)$-colourable. Repeating this argument gives a $(b - 2)$-clique $K$ with $G'_{K}$ not 3-colourable.

Now, applying <Ref> with $X = K$ and $\gamma = 1/7$ gives

\begin{equation*}
\delta(G'_{K}) > \biggl(1 - \frac{1}{b - (b - 2) + 1/7}\biggr) \cdot \lvert G'_{K}\rvert = 8/15 \cdot \lvert G'_{K} \rvert.
\end{equation*}

By <Ref> and <Ref>, $G'_{K}$ contains either an odd wheel, a copy of $H_{2}$, or a copy of $T_{0}$. Hence $G'$ contains either $K_{b - 2} + W_{\text{odd}} = K_{b - 1} + C_{\text{odd}}$, $K_{b - 2} + H_{2}$ or $K_{b - 2} + T_{0}$. Note that $G$ cannot contain any of these so $uv$ is a missing edge from one of these configurations. <Ref> mean that both $u$ and $v$ lie in the $C_{\text{odd}}$, the $H_{2}$ or the $T_{0}$.

In particular, $u, v \not \in K$ so $K$ is a $(b - 2)$-clique in $G$ and $V(G_{K}) = V(G'_{K})$. We have the following facts.

* By <Ref>, $G_{K}$ is 3-colourable and so locally bipartite.

* By <Ref>, $u, v$ is a 2-sparse pair in $G_{K}$.

* Applying <Ref> with $X = K$ and $\gamma = 1/7$ gives $\delta(G_{K}) > 8/15 \cdot \ssize{G_{K}}$.

* The graph $G_{K}$ contains no odd wheel, $H_{0}$ or $T_{0}$ ($G_{K}$ is 3-colourable) but the addition of $uv$ introduces an odd wheel, a copy of $H_{2}$, or a copy of $T_{0}$.

Using the argument at the start of the proof of <Ref>, we deduce that, within $G_{K}$, there must be one of the configurations appearing in <Ref> in <Ref> (with labels $u$ and $v$ possibly swapped). Note in that proof we only used edge-maximality to show that $uv$ was the missing edge of an odd wheel, a copy of $H_{2}$ or a copy of $T_{0}$ (and so here we do not need $G_{K}$ to be edge-maximal locally bipartite).

We now mimic the remainder of the proof of <Ref>. Let $I$ be a largest independent set in $G$: $\ssize{I} = \alpha(G)$.

For all $u, v \in I$, the pair $u, v$ is $b$-dense and furthermore for every $u \in I$, $D_{u} = I \setminus \set{u}$.

Fix distinct $u, v \in I$. We will first show that $G_{u, v}$ is not $(b - 1)$-colourable. Note that $\Gamma(u), \Gamma(v) \subset V(G) \setminus I$ so $\ssize{\Gamma(u) \cup \Gamma(v)} \leqslant \ssize{G} - \ssize{I}$. Also $I \subset V(G) \setminus \Gamma(u)$, so $\ssize{I} \leqslant \ssize{G} - d(u) \leqslant \ssize{G} - \delta(G)$. Hence,

\begin{align*}
\ssize{\Gamma(u, v)} & = d(u) + d(v) - \ssize{\Gamma(u) \cup \Gamma(v)} \geqslant 2 \delta(G) + \ssize{I} - \ssize{G} \\
& = b \delta(G) - (b - 1) \ssize{G} + (b - 2)(\ssize{G} - \delta(G)) + \ssize{I} \\
& \geqslant b \delta(G) - (b - 1) \ssize{G} + (b - 1) \ssize{I} > (b - 1) \ssize{I},
\end{align*}

where we used $\delta(G) > (1 - 1/b) \cdot \ssize{G}$ in the final inequality. But $I$ was a largest independent set in $G$ so $G_{u, v}$ is not $(b - 1)$-colourable.

Now we will show that $u, v$ is $b$-dense. Suppose not and so they form a $b$-sparse pair. If $b = 3$, then $G_{u, v}$ is not bipartite and so contains an odd cycle. This contradicts <Ref>. For $b \geqslant 4$ we will find a $(b - 4)$-clique $K$ in $G_{u, v}$ with $G_{u, v, K}$ not 3-colourable. For $b = 4$, we take $K = \varnothing$ and this suffices. For larger $b$, we note that, by <Ref>, $\delta(G_{u, v}) > (1 - 1/(b - 2 + 1/7)) \cdot \ssize{G_{u, v}}$. By the induction hypothesis, if $G_{u, v}$ were locally $(b - 2)$-partite, then $G_{u, v}$ would be $(b - 1)$-colourable, which it is not. Thus, there is $w_{1} \in G_{u, v}$ with $G_{u, v, w_{1}}$ not $(b - 2)$-colourable. Repeating this argument we obtain a $(b - 4)$-clique $K$ with $G_{u, v, K}$ not 3-colourable. Applying <Ref> with $X = \set{u, v, K}$ and $\gamma = 1/7$ gives

\begin{equation*}
\delta(G_{u, v, K}) > (1 - 1/(b - (b - 2) + 1/7)) \cdot \ssize{G_{u, v, K}} = 8/15 \cdot \ssize{G_{u, v, K}}.
\end{equation*}

Then <Ref> gives that $G_{u, v, K}$ either contains an odd wheel, a copy of $H_{0}$ or a copy of $T_{0}$. These contradict <Ref> (applied to $G$). We have shown that $u, v$ must be $b$-dense, i.e. that $I \setminus \set{u} \subset D_{u}$.

We now prove the other direction. Let $v \in D_{u}$. The set $D_{u}$ is independent by <Ref>, since $G$ is locally $b$-partite with $\delta(G) > (1 - 1/b) \cdot \ssize{G} \geqslant 2b/(2b + 3) \cdot \ssize{G}$. In particular, $v$ has no neighbour in $I$. But $I$ is a largest independent set so $v$ must be in $I$.

A pair of vertices $u, v$ is $b$-quasidense if there is a sequence of vertices $u = d_{1}, d_{2}, \dotsc, d_{k}, d_{k + 1} = v$ such that all pairs $d_{i}, d_{i + 1}$ are $b$-dense ($i = 1, 2, \dotsc, k$).

<Ref> immediately implies that if $u, v$ is $b$-quasidense and $u \in I$, then $v \in I$ as well. Now we can finish the proof. It suffices to show that every vertex is either in $I$ or is adjacent to all of $I$. Indeed, we may then fix $u \in I$ and note that $G[V(G) \setminus I] = G_{u}$ so $G[V(G) \setminus I]$ is $b$-colourable. Using a further colour for the independent set $I$ gives a $(b + 1)$-colouring of $G$.

Suppose instead there is $u \in I$ and $v \not \in I$ with $u$ not adjacent to $v$. In particular, the pair $u, v$ cannot be $b$-quasidense and so is $b$-sparse. Thus from our remarks just preceding <Ref>, there is a $(b - 2)$-clique $K$ in $G$ such that $G_{K}$ contains one of the configurations appearing in <Ref> (with labels $u$ and $v$ possibly swapped) and the pair $u, v$ is 2-sparse in $G_{K}$.

Focus on $G_{K}$ – this graph is 3-colourable so locally bipartite, $H_{0}$-free and $T_{0}$-free and the pair $u, v$ is 2-sparse in $G_{K}$. Also, by <Ref>, $\delta(G_{K}) > (1 - 1/(b - (b - 2) + 1/7)) \cdot \ssize{G_{K}} = 8/15 \cdot \ssize{G_{K}}$. In the proof of <Ref>, we used these facts alone to show that $u, v$ is quasidense in every configuration appearing in <Ref>. Hence the pair $u, v$ is quasidense in $G_{K}$ so is $b$-quasidense in $G$. This is our required contradiction.

§ $A$-LOCALLY $B$-PARTITE GRAPHS

In this section we relate the chromatic profile of $a$-locally $b$-partite graphs to the chromatic profile of locally $b$-partite graphs, making precise our comment in the introduction that to understand $a$-locally $b$-partite graphs it seems to be enough to understand locally $b$-partite graphs. This is elucidated at the end of <Ref> and just before <Ref>. Along the way we will prove <Ref>.

§.§ The first threshold – proving <Ref>

As noted in the introduction, the first interesting threshold is $\delta_{\chi}(\sca{F}_{a,b}, a + b)$ – what values of $c$ guarantee that any $a$-locally $b$-partite graph with $\delta(G) \geqslant c \ssize{G}$ is $(a + b)$-colourable? We already know $\delta_{\chi}(\sca{F}_{1,2}, 3) = 4/7$ and $\delta_{\chi}(\sca{F}_{1,b}, b + 1) \leqslant 1 - 1/(b + 1/7)$ and will extend these to all values of $a$ and $b$. To simplify the statements of our results and make comparisons between different values of $a$ and $b$, it is helpful to write

\begin{equation*}
\delta_{\chi}(\sca{F}_{a,b}, a + b) = 1 - \frac{1}{a + b - 1 + \gamma_{a, b}},
\end{equation*}

and to focus our attention on the $\gamma_{a, b}$. As $\delta_{\chi}(\sca{F}_{a,b}, a + b) \geqslant \delta_{\chi}(\sca{F}_{a,b})$ we have, from <Ref>,

\begin{equation*}
\gamma_{a, b} \geqslant 0.
\end{equation*}

We collect some other basic properties of the $\gamma_{a, b}$.

For all positive integers $a$ and $b$ the following hold.

* $\delta_{\chi}(\sca{F}_{a, b+1}, a + b) \leqslant \delta_{\chi}(\sca{F}_{a + 1, b}, a + b)$ and so

\begin{equation}\label{eq:ab}
\gamma_{a, b + 1} \leqslant \gamma_{a + 1, b}.
\end{equation}

* $1/(2 - \delta_{\chi}(\sca{F}_{a, b}, a + b)) \leqslant \delta_{\chi}(\sca{F}_{a + 1, b}, a + b + 1)$ and so

\begin{equation}\label{eq:a}
\gamma_{a, b} \leqslant \gamma_{a + 1, b}.
\end{equation}

Also $\gamma_{1,2} = 1/3$ and $\gamma_{1, b} \leqslant 1/7$ for all $b \geqslant 3$.

In [11] it was shown that $\delta_{\chi}(\sca{F}_{1,2},3) = 4/7$ giving $\gamma_{1,2} = 1/3$ while, for $b \geqslant 3$, <Ref> showed $\delta_{\chi}(\sca{F}_{1,b},b + 1) \leqslant 1 - 1/(b + 1/7)$ so $\gamma_{1, b} \leqslant 1/7$.

Now $\sca{F}_{a, b + 1} \subset \sca{F}_{a + 1, b}$ from which $\delta_{\chi}(\sca{F}_{a, b + 1}, a + b) \leqslant \delta_{\chi}(\sca{F}_{a + 1, b}, a + b)$ immediately follows. This gives inequality (<ref>).

Finally let $d < \delta_{\chi}(\sca{F}_{a, b}, a + b)$: there is an $a$-locally $b$-partite graph $G$ with $\delta(G) \geqslant d \ssize{G}$ and $\chi(G) > a + b$. Let $G'$ be $G$ joined to an independent set of size $\ssize{G} - \delta(G)$, that is,

\begin{equation*}
G' = K_{1}(\ssize{G} - \delta(G)) + G.
\end{equation*}

Since $G$ is $a$-locally $b$-partite, it is also $(a + 1)$-locally $(b - 1)$-partite. From both of these it follows that $G'$ is $(a + 1)$-locally $b$-partite. Also, $\chi(G') = \chi(G) + 1 > a + b + 1$, and

\begin{align*}
\frac{\delta(G')}{\ssize{G'}} = \frac{\ssize{G}}{2 \ssize{G} - \delta(G)} = \frac{1}{2 - \delta(G) \ssize{G}^{-1}} \geqslant \frac{1}{2 - d},
\end{align*}

so $\delta_{\chi}(\sca{F}_{a + 1, b}, a + b + 1) \geqslant 1/(2 - d)$. This holds for all $d < \delta_{\chi}(\sca{F}_{a, b}, a + b)$, so $\delta_{\chi}(\sca{F}_{a + 1, b}, a + b + 1) \geqslant 1/(2 - \delta_{\chi}(\sca{F}_{a, b}, a + b))$. Thus

\begin{equation*}
1 - \frac{1}{a + b + \gamma_{a + 1, b}} \geqslant \frac{1}{1 + \frac{1}{a + b - 1 + \gamma_{a, b}}} = \frac{a + b - 1 + \gamma_{a, b}}{a + b + \gamma_{a, b}} = 1 - \frac{1}{a + b + \gamma_{a, b}},
\end{equation*}

and so $\gamma_{a + 1, b} \geqslant \gamma_{a, b}$, as required.

Inequality (<ref>) gives a lower bound for $\gamma_{a + 1, b}$ in terms of $\gamma_{a, b}$. The next lemma, which lies at the heart of our analysis, gives an upper bound.

For all positive integers $a$ and $b$,

\begin{equation}\label{eq:gammamain0}
\gamma_{a, b} \leqslant \gamma_{a + 1, b} \leqslant \max \set{\gamma_{a, b}, \gamma_{1, a + b}}.
\end{equation}

The left-hand inequality is just inequality (<ref>). Let $\gamma = \max \set{\gamma_{a, b}, \gamma_{1, a + b}}$. Let $G$ be an $(a + 1)$-locally $b$-partite graph with

\begin{equation*}
\delta(G) > \biggl(1 - \frac{1}{a + b + \gamma}\biggr) \cdot \ssize{G}.
\end{equation*}

It suffices to show that $\chi(G) \leqslant a + b + 1$ as then

\begin{equation*}
1 - \frac{1}{a + b + \gamma} \geqslant \delta_{\chi}(\sca{F}_{a + 1, b}, a + b + 1) = 1 - \frac{1}{a + b + \gamma_{a + 1, b}}.
\end{equation*}

Fix any $u \in V(G)$ and consider $G_{u}$: $G_{u}$ is an $a$-locally $b$-partite graph with

\begin{equation*}
\delta(G_{u}) > \biggl(1 - \frac{1}{a + b - 1 + \gamma}\biggr) \cdot \ssize{G_{u}},
\end{equation*}

by the lifting lemma, <Ref>. But $\gamma \geqslant \gamma_{a, b}$ so

\begin{equation*}
\delta(G_{u}) > \delta_{\chi}(\sca{F}_{a, b}, a + b) \cdot \ssize{G_{u}},
\end{equation*}

and hence $G_{u}$ is $(a + b)$-colourable. Thus $G$ is a locally $(a + b)$-partite graph. Also $\gamma \geqslant \gamma_{1, a + b}$, so

\begin{equation*}
\delta(G) > \delta_{\chi}(\sca{F}_{1, a + b}, a + b + 1) \cdot \ssize{G}.
\end{equation*}

Thus $G$ is $(a + b + 1)$-colourable.

From this one can immediately deduce <Ref>.

For all positive integers $a$ and for all $b \geqslant 3$,

\begin{equation*}
\gamma_{a, 2} = 1/3, \quad \gamma_{a, b} \leqslant 1/7,
\end{equation*}

and so

\begin{equation*}
\delta_{\chi}(\sca{F}_{a, 2}, a + 2) = 1 - \frac{1}{a + 1 + 1/3}, \qquad \delta_{\chi}(\sca{F}_{a, b}, a + b) \leqslant 1 - \frac{1}{a + b - 1 + 1/7}.
\end{equation*}

From <Ref>, $\gamma_{1, 2} = 1/3$ and $\gamma_{1, b} \leqslant 1/7$ for any $b \geqslant 3$. By <Ref>, for any $a$ and any $b \geqslant 2$,

\begin{equation*}
\gamma_{a, b} \leqslant \gamma_{a + 1, b} \leqslant \max \set{\gamma_{a, b}, \gamma_{1, a + b}} \leqslant \max \set{\gamma_{a, b}, 1/7}.
\end{equation*}

An easy induction gives $\gamma_{a, 2} = 1/3$ for all $a$ and $\gamma_{a, b} \leqslant 1/7$ for any $b \geqslant 3$.

Note that inequalities (<ref>) and (<ref>) give

\begin{equation*}
\gamma_{a, b} \geqslant \gamma_{1, b'},
\end{equation*}

for all $b \leqslant b' \leqslant a + b - 1$. In line with our inductive arguments in <Ref>, we believe that in fact $\gamma_{1, b} \geqslant \gamma_{1, b + 1}$ for all $b$. If this were true, then $\gamma_{a, b} \geqslant \gamma_{1, a + b}$, and so <Ref> would give $\gamma_{a, b} = \gamma_{a + 1, b}$ for all $a, b$. Of course, this implies $\gamma_{a, b} = \gamma_{1, b}$ and so $\delta_{\chi}(\sca{F}_{a, b}, a + b)$ would be determined by $\delta_{\chi}(\sca{F}_{1, b}, b + 1)$ – a particular manifestation of our aforementioned belief that to understand $a$-locally $b$-partite graphs, we should focus on locally $b$-partite graphs. It also highlights the following question.

Is the sequence $\gamma_{1, b}$ decreasing in $b$?

§.§ $a$-locally bipartite graphs

One could replicate the elementary approach of the previous section to try to evaluate $\delta_{\chi}(\sca{F}_{a, b}, k)$ for $k > a + b$. Indeed one might define $\gamma_{a, b, m}$ by

\begin{equation*}
\delta_{\chi}(\sca{F}_{a, b}, a + b + m) = 1 - \frac{1}{a + b - 1 + \gamma_{a, b, m}},
\end{equation*}

so that $\gamma_{a, b, 0} = \gamma_{a, b}$. Many of the properties of the $\gamma_{a, b}$ pass over: the $\gamma_{a, b, m}$ are non-negative (and, in fact, $\lim_{m \rightarrow \infty} \gamma_{a, b, m} = 0$) and both inequalities (<ref>) and (<ref>) extend easily ($\gamma_{a, b + 1, m} \leqslant \gamma_{a + 1, b, m}$ and $\gamma_{a, b, m} \leqslant \gamma_{a + 1, b, m}$). However, there seems to be no argument to produce inequality (<ref>) or anything similar. A more involved approach would be required.

The next threshold to consider is $\delta_{\chi}(\sca{F}_{a, b}, a + b + 1)$. For locally bipartite graphs, we showed $\delta_{\chi}(\sca{F}_{1, 2}, 4) \leqslant 6/11$ and had many structural results (some of which we will extend). For $b \geqslant 3$, we know very little about $\delta_{\chi}(\sca{F}_{1, b}, b + 2)$ beyond it being at least $\delta_{\chi}(\sca{F}_{1, b}) = 1 - 1/b$ and at most $\delta_{\chi}(\sca{F}_{1, b}, b + 1) \leqslant 1 - 1/(b + 1/7)$. The question for $b = 3$ is of particular interest. We mention that the complement of the 9-cycle is locally tripartite, 5-chromatic and has minimum degree $6 = 2/3 \cdot 9$.

Is there a locally tripartite graph $G$ with minimum degree greater than $2/3 \cdot \ssize{G}$ which is not 4-colourable?

We now focus on $a$-locally bipartite graphs. The following theorem, which will be essential for extending the Andrásfai-Erdős-Sós theorem [12], should be compared to <Ref> – again we see that the key to understanding $a$-locally bipartite graphs is to understand locally bipartite ones. The proof is an induction combining our results for locally bipartite (<Ref>) and locally $b$-partite (<Ref>) graphs.

Let $G$ be an $a$-locally bipartite graph.

* If $\delta(G) > (1 - 1/(a + 4/3)) \cdot \ssize{G}$, then $G$ is $(a + 2)$-colourable. Blow-ups of $K_{a - 1} + \overline{C}_{7}$ show that this is tight.

* If $\delta(G) > (1 - 1/(a + 5/4)) \cdot \ssize{G}$, then $G$ is either $(a + 2)$-colourable or contains $K_{a - 1} + \overline{C}_{7}$.

* If $\delta(G) > (1 - 1/(a + 6/5)) \cdot \ssize{G}$, then $G$ is either $(a + 2)$-colourable or contains $K_{a - 1} + \overline{C}_{7}$ or $K_{a - 1} + H_{2}^{+}$.

* If $\delta(G) > (1 - 1/(a + 7/6)) \cdot \ssize{G}$, then $G$ is either $(a + 2)$-colourable or contains $K_{a - 1} + H_{2}$.

* If $\delta(G) > (1 - 1/(a + 8/7)) \cdot \ssize{G}$, then $G$ is either $(a + 2)$-colourable or contains $K_{a - 1} + H_{2}$ or $K_{a - 1} + T_{0}$.

* For any $\varepsilon > 0$, there is a constant $C$ such that if $\delta(G) > (1 - 1/(a + 1) + \varepsilon) \cdot \ssize{G}$, then $G$ is $C$-colourable.

* There are locally bipartite graphs, $G$, with minimum degree $(1 - 1/(a + 1) - o(1)) \cdot \ssize{G}$ and arbitrarily large chromatic number.

First note that the last two bullet points are just the statement that $\delta_{\chi}(\sca{F}_{a,2}) = 1 - 1/(a + 1)$ which follows from <Ref>. Also the suitable blow-ups mentioned in the first bullet point are balanced blow-ups of $K_{a - 1}(3) + \overline{C}_{7}$. Proving everything else is a simple induction on $a$ (with <Ref> covering the base case). Indeed we will just demonstrate it for the third last bullet point. Let $G$ be an $a$-locally bipartite graph with $\delta(G) > (1 - 1/(a + 8/7)) \cdot \ssize{G}$. Fix any vertex $u$ of $G$ and consider $G_{u}$: this is $(a - 1)$-locally bipartite and by <Ref>, $\delta(G_{u}) > (1 - 1/(a - 1 + 8/7)) \cdot \ssize{G_{u}}$. By induction, either $G_{u}$ contains one of $K_{a - 2} + H_{2}$, $K_{a - 2} + T_{0}$ or is $(a + 1)$-colourable. If there is some vertex $u$ with $G_{u}$ not $(a + 1)$-colourable, then $G$ contains one of $K_{a - 1} + H_{2}$, $K_{a - 1} + T_{0}$. Otherwise, $G$ is locally $(a + 1)$-partite. But, by <Ref>,

\begin{equation*}
\delta_{\chi}(\sca{F}_{1, a + 1}, a + 2) \leqslant 1 - \frac{1}{a + 8/7},
\end{equation*}

so $G$ is $(a + 2)$-colourable, as required.

§ ACKNOWLEDGEMENT

It is a pleasure to thank Andrew Thomason for many helpful discussions.

[1]
P. Allen, J. Böttcher, S. Griffiths, Y. Kohayakawa, and R. Morris.
The chromatic thresholds of graphs.
Advances in Mathematics, 235:261–295, 2013.

[2]
B. Andrásfai, P. Erdős, and V. T. Sós.
On the connection between chromatic number, maximal clique and
minimal degree of a graph.
Discrete Mathematics, 8(3):205–218, 1974.

[3]
I. Bárány.
A short proof of Kneser's conjecture.
Journal of Combinatorial Theory. Series A, 25:325–326, 1978.

[4]
S. Brandt and S. Thomassé.
Dense triangle-free graphs are four-colorable: a solution to the
Erdős-Simonovits problem, 2005.
Submitted. Available at
<http://perso.ens-lyon.fr/stephan.thomasse/> .

[5]
C. C. Chen, G. P. Jin, and K. M. Koh.
Triangle-free graphs with large degree.
Combinatorics, Probability and Computing, 6(4):381–396, 1997.

[6]
P. Erdős.
Some recent results on extremal problems in graph theory.
In Theory of Graphs (International Symposium, Rome,
1966), pages 117–123. Gordon and Breach, New York; Dunod, Paris, 1967.

[7]
P. Erdős.
On some new inequalities concerning extremal properties of graphs.
In Theory of Graphs (Proceedings of Colloquium, Tihany,
1966), pages 77–81. Academic Press, New York, 1968.

[8]
P. Erdős and M. Simonovits.
On a valence problem in extremal graph theory.
Discrete Mathematics, 5(4):323–334, 1973.

[9]
W. Goddard and J. Lyle.
Dense graphs with small clique number.
Journal of Graph Theory, 66(4):319–331, 2011.

[10]
R. Häggkvist.
Odd cycles of specified length in nonbipartite graphs.
Annals of Discrete Mathematics, 13:89–99, 1982.

[11]
F. Illingworth.
The chromatic profile of locally bipartite graphs, Dec 2020.
Submitted. Available at <https://arxiv.org/abs/2012.10409> .

[12]
F. Illingworth.
Minimum-degree stability of ${H}$-free graphs, 2021.
In preparation.

[13]
G. P. Jin.
Triangle-free four-chromatic graphs.
Discrete Mathematics, 145(1):151–170, 1995.

[14]
M. Kneser.
Aufgabe 360.
Jahresbericht der Deutschen Mathematiker-Vereinigung, 58, 1955.

[15]
L. Lovász.
Kneser's conjecture, chromatic number, and homotopy.
Journal of Combinatorial Theory. Series A, 25(3):319–324,

[16]
T. Łuczak and S. Thomassé.
Coloring dense graphs via VC-dimension, July 2010.
Available at <https://arxiv.org/abs/1007.1670> .

[17]
V. Nikiforov.
Chromatic number and mimimum degree of ${K}_{r}$-free graphs, Jan
Available at <https://arxiv.org/abs/1001.2070> .

[18]
A. Schrijver.
Vertex-critical subgraphs of Kneser graphs.
Nieuw Arch. Wisk., 26(3):454–461, 1978.

[19]
M. Simonovits.
A method for solving extremal problems in graph theory, stability
In Theory of Graphs (Proceedings of Colloquium, Tihany,
1966), pages 279–319. Academic Press, New York, 1968.

[20]
P. Turán.
Eine Extremalaufgabe aus der Graphentheorie.
Matematikai és Fizikai Lapok, 48:436–452, 1941.

§ VERIFYING <REF>

In this appendix we verify <Ref> which, for convenience, we display again here.

(H21) at (0,0)$H_{2}^{+}$;
(blank) [left = of H21]H1;
(C7) [left = of blank]$\overline{C}_{7}$;
(H12) [below = of H21]$H_{1}^{++}$;
(T0) [right = of H12]$T_{0}$;
(H2) [left = of H12]$H_{2}$;
(H1) [below = of H2]$H_{1}$;
(H0) [below = of H1]$H_{0}$;

[-Latex] (H2) – (H21);
[-Latex] (H2) – (C7);
[dashed, -Latex] (H12) – (H21);
[dashed, -Latex] (T0) – (H21);
[-Latex] (H1) – (H2);
[-Latex] (H1) – (H12);
[-Latex] (H0) – (H1);

The reader will recall that full arrows represent containment and dashed arrows represent homomorphisms. Furthermore, $H$ is homomorphic to $G$ in the diagram if there is a sequence of arrows starting at $H$ and ending at $G$.

All the containments are clear. The following figure gives a homomorphism from $H_{1}^{++}$ to $H_{2}^{+}$: the left diagram is a labelling of the vertices of $H_{1}^{++}$ and the right diagram shows the images of those vertices under the map.

in 0,1,...,6

(*360/7 + 90:1.5)v_

(ul,v_0 ul,v_2 ul,v_3 ur,v_0 ur,v_5 ur,v_3)
[below right = -4pt](ul)$a_{023}$
[above left = -2pt](ur)$a_{350}$

in 0,1,...,6

(*360/7 + 90:1.5)v_

(v_1,v_3,v_5,v_0, v_2,v_4,v_6)
(u,v_0 u,v_2 u,v_5)
[below](v_3)$a_{1}, a_{023}$

The following figures gives a homomorphism from $T_{0}$ to $H_{2}^{+}$: the left diagram is a labelling of the vertices of $T_{0}$ and the right diagram shows the images of those vertices under the map.

in 0,1,...,6

(*360/7 + 90:1.6)v_

(t,v_0 t,u_1 t,u_6)
in 0,2,3,4,5,6

in 0,1,2,3,4,5

[below right = -4pt](u_1)$u_{1}$
[below left = -4pt](u_6)$u_{6}$

in 0,1,...,6

(*360/7 + 90:1.5)v_

(v_1,v_3,v_5,v_0, v_2,v_4,v_6)
(u,v_0 u,v_2 u,v_5)
[below](v_3)$v_{2}, v_{4}$
[below](v_4)$v_{3}, v_{5}$

In particular, all arrows in <Ref> are correct. We need to show that further arrows could not be added. There are some subtleties in our notation that we now elucidate. Given a homomorphism $\varphi : H \rightarrow G$, we say $\varphi$ is surjective or injective if the map $\varphi : V(H) \rightarrow V(G)$ is surjective or injective, respectively. Note that $\varphi$ being injective implies that $H$ is actually a subgraph of $G$. By $\varphi(H)$ we mean the graph on vertex set $\varphi(V(H))$ and edge set $\varphi(E(H))$. In particular, this is a spanning subgraph of $G[\varphi(V(H))]$ but it may not have all the edges of $G[\varphi(V(H))]$. We make frequent use of the fact that $\chi(\varphi(H)) \geqslant \chi(H)$.

We first deal with left-hand side ($H_{0} \rightarrow H_{1} \rightarrow H_{2} \rightarrow \overline{C}_{7}$) of the figure: we need to show that $\overline{C}_{7} \nrightarrow H_{2}$, $H_{2} \nrightarrow H_{1}$ and $H_{1} \nrightarrow H_{0}$. The arguments are very similar, making use of the fact that $H_{0}$, $H_{1}$, $H_{2}$ and $\overline{C}_{7}$ are all vertex-critical 4-chromatic graphs on seven vertices, so we only give the explicit proof for $H_{2} \nrightarrow H_{1}$.

The graph $H_{2}$ is not homomorphic to $H_{1}$.

Suppose there is a homomorphism $\varphi: H_{2} \rightarrow H_{1}$. Then $\chi(\varphi(H_{2})) \geqslant \chi(H_{2}) = 4$. Now $H_{1}$ is a vertex-critical 4-chromatic graph, so $\varphi$ is surjective. But $H_{1}$ and $H_{2}$ both have seven vertices so $\varphi$ is injective. That is, $H_{1}$ must contain a copy of $H_{2}$, which is absurd as $e(H_{1}) < e(H_{2})$.

We now know that the left-hand side of <Ref> is correct and consider how $H_{2}^{+}$ relates to it. It suffices to show that $H_{2}^{+} \nrightarrow \overline{C}_{7}$ and $\overline{C}_{7} \nrightarrow H_{2}^{+}$ (note that $H_{2}^{+} \nrightarrow \overline{C}_{7}$ implies $H_{2}^{+} \nrightarrow H_{2}, H_{1}, H_{0}$). That $H_{2}^{+}$ is not homomorphic to $\overline{C}_{7}$ and vice versa follows from the next lemma, which appeared in [11] – both $\overline{C}_{7}$ and $H_{2}^{+}$ are edge-maximal locally bipartite graphs and neither is a subgraph of the other ($\overline{C}_{7}$ has fewer vertices than $H_{2}^{+}$ and $H_{2}^{+}$ does not have seven vertices all of degree at least four).

Let $F$ be an edge-maximal locally bipartite graph in which no two neighbourhoods are the same. Let $F$ be homomorphic to a locally bipartite graph $G$. Then $F$ is an induced subgraph of $G$.

Next we relate $H_{1}^{++}$ to the diagram. It suffices to show that $H_{1}^{++} \nrightarrow \overline{C}_{7}$ and $H_{2} \nrightarrow H_{1}^{++}$ (note that $H_{1}^{++} \nrightarrow \overline{C}_{7}$ implies $H_{1}^{++} \nrightarrow H_{2}, H_{1}, H_{0}$ while $H_{2} \nrightarrow H_{1}^{++}$ implies $\overline{C}_{7} \nrightarrow H_{1}^{++}$ and $H_{2}^{+} \nrightarrow H_{1}^{++}$).

The graph $H_{1}^{++}$ is not homomorphic to $\overline{C}_{7}$.

Suppose there is a homomorphism $\varphi : H_{1}^{++} \rightarrow \overline{C}_{7}$. Label the copy of $H_{1}^{++}$ as shown below and let $A = \set{a_{0}, a_{1}, \dotsc, a_{6}}$ so $H_{1}^{++}[A]$ is a copy of $H_{1}$. Note that $\chi(\varphi(H_{1}^{++}[A])) \geqslant \chi(H_{1}^{++}[A]) = 4$ and $\overline{C}_{7}$ is a vertex-critical 4-chromatic graph, so the restriction of $\varphi$ to $A$ is a surjection onto $\overline{C}_{7}$ and so $\varphi(a_{0}), \varphi(a_{1}), \dotsc, \varphi(a_{6})$ are all distinct.

in 0,1,...,6

(*360/7 + 90:1.5)v_

(ul,v_0 ul,v_2 ul,v_3 ur,v_0 ur,v_5 ur,v_3)
[below right = -4pt](ul)$a_{023}$
[above left = -2pt](ur)$a_{350}$

Now $a_{0}$ has degree 6 while $\varphi(a_{0}) \in \overline{C}_{7}$ only has degree 4. The four neighbours of $\varphi(a_{0})$ are $\varphi(a_{1}), \varphi(a_{2}), \varphi(a_{5}), \varphi(a_{6})$ and so $\varphi(a_{023})$ is one of these. Also $a_{2}$ has degree 5 while $\varphi(a_{2})$ only has degree 4. The four neighbours of $\varphi(a_{2})$ are $\varphi(a_{0}), \varphi(a_{1}), \varphi(a_{3}), \varphi(a_{4})$ and so $\varphi(a_{023})$ is one of these. Hence $\varphi(a_{023}) = \varphi(a_{1})$. Similarly, considering the neighbourhoods of $a_{0}$ and $a_{5}$, shows that $\varphi(a_{350}) = \varphi(a_{6})$. Then $\Gamma(\varphi(a_{3}))$ contains

\begin{equation*}
\set{\varphi(a_{2}), \varphi(a_{023}), \varphi(a_{350}), \varphi(a_{4}), \varphi(a_{5})} = \set{\varphi(a_{2}), \varphi(a_{1}), \varphi(a_{6}), \varphi(a_{4}), \varphi(a_{5})},
\end{equation*}

which has size 5. This contradicts the 4-regularity of $\overline{C}_{7}$.

The graph $H_{2}$ is not homomorphic to $H_{1}^{++}$.

Suppose there is a homomorphism $\varphi : H_{2} \rightarrow H_{1}^{++}$. Now $\chi(\varphi(H_{2})) \geqslant \chi(H_{2}) = 4$ and any 6-vertex subgraph of $H_{1}^{++}$ is 3-colourable (it is homomorphic to some 6-vertex subgraph of $H_{2}^{+}$) so $\varphi$ must be injective. Thus $H_{1}^{++}$ contains $H_{2}$. But $H_{1}^{++}$ only has 4 vertices of degree at least 4 while $H_{2}$ has 5 vertices of degree 4.

Finally we relate $T_{0}$ to the diagram. It suffices to show that $H_{0} \nrightarrow T_{0}$, $T_{0} \nrightarrow \overline{C}_{7}$ and $T_{0} \nrightarrow H_{1}^{++}$ (note that $H_{0} \nrightarrow T_{0}$ implies that no other graph in the diagram is homomorphic to $T_{0}$ while $T_{0} \nrightarrow \overline{C}_{7}$ implies that $T_{0} \nrightarrow H_{0}, H_{1}, H_{2}$). In all three proofs we use the label the copy of $T_{0}$ as follows.

in 0,1,...,6

(*360/7 + 90:1.6)v_

(t,v_0 t,u_1 t,u_6)
in 0,2,3,4,5,6

in 0,1,2,3,4,5

[below right = -4pt](u_1)$u_{1}$
[below left = -4pt](u_6)$u_{6}$

The graph $H_{0}$ is not homomorphic to $T_{0}$.

We first claim that any 7-vertex subgraph of $T_{0}$ is 3-colourable. Let $F$ be a 7-vertex subgraph of $T_{0}$. If $F$ contains all the $v_{i}$, then $F$ is a subgraph of a 7-cycle and so is 3-colourable. Otherwise $F$ is a subgraph of $T_{0} - v_{i}$ for some $i$. This graph is 3-colourable: 2-colour the remaining $v_{j}$ with colours 1 and 2, give $u_{1}$ and $u_{6}$ colour 3 and then give $t$ colour 1 or 2 (opposite to the colour of $v_{0}$ if it is present).

Suppose there is a homomorphism $\varphi : H_{0} \rightarrow T_{0}$. Then $\varphi(H_{0})$ is a subgraph of $T_{0}$ with at most 7 vertices, so is 3-colourable. But then $3 \geqslant \chi(\varphi(H_{0})) \geqslant \chi(H_{0}) = 4$.

The graph $T_{0}$ is not homomorphic to $\overline{C}_{7}$.

Suppose $\varphi : T_{0} \rightarrow \overline{C}_{7}$ is a homomorphism. Label the copy of $\overline{C}_{7}$ as follows.

in 0,1,...,6

(*360/7 + 90:1)v_

[below left](v_3)$a_{3}$
[below right](v_4)$a_{4}$

Without loss of generality we may assume $\varphi(u_{1}) = a_{0}$. The common neighbourhood $\Gamma(u_{1}, u_{6})$ contains the edge $tv_{0}$, so $\Gamma(\varphi(u_{1}), \varphi(u_{6}))$ contains an edge and so $\varphi(u_{6}) \in \set{a_{0}, a_{3}, a_{4}}$. By symmetry, we may assume $\varphi(u_{6}) \in \set{a_{0}, a_{3}}$.

First suppose that $\varphi(u_{6}) = a_{0}$. Then

\begin{equation*}
\varphi(\set{v_{0}, v_{1}, \dotsc, v_{6}}) \subset \varphi(\Gamma(u_{1}) \cup \Gamma(u_{6})) \subset \Gamma(\varphi(u_{1})) \cup \Gamma(\varphi(u_{6})) = \Gamma(a_{0}).
\end{equation*}

However, $v_{0}v_{1}\dotsc v_{6}$ form a 7-cycle which is 3-chromatic, while $\Gamma(a_{0})$ is a path of length 3 (which is bipartite).

Now suppose that $\varphi(u_{6}) = a_{3}$. The edge $tv_{0}$ is in $\Gamma(u_{1}, u_{6})$ so $\varphi(t)\varphi(v_{0})$ must be an edge in $\Gamma(a_{0}, a_{3})$. In particular, $\set{\varphi(t), \varphi(v_{0})} = \set{a_{1}, a_{2}}$. By symmetry we may assume that $\varphi(v_{0}) = a_{1}$. Now $v_{1} \in \Gamma(v_{0}, u_{6})$, so $\varphi(v_{1}) \in \Gamma(a_{1}, a_{3})$ and so $\varphi(v_{1}) = a_{2}$. Next $v_{2} \in \Gamma(u_{1}, u_{6}, v_{1})$, so $\varphi(v_{2}) \in \Gamma(a_{0}, a_{3}, a_{2})$ and so $\varphi(v_{2}) = a_{1}$. Working in this way round the outer 7-cycle gives $\varphi(v_{3}) = a_{2}$, $\varphi(v_{4}) = a_{1}$ and $\varphi(v_{5}) = a_{2}$. Finally $v_{6} \in \Gamma(u_{1}, v_{0}, v_{5})$ and so $\varphi(v_{6}) \in \Gamma(a_{0}, a_{1}, a_{2}) = \varnothing$, which is a contradiction.

The graph $T_{0}$ is not homomorphic to $H_{1}^{++}$.

Suppose $\varphi : T_{0} \rightarrow H_{1}^{++}$ is a homomorphism. If $x, y$ is a dense pair (see <Ref>) of vertices in $T_{0}$, then $\Gamma(x, y)$ contains an edge, so $\Gamma(\varphi(x), \varphi(y))$ contains an edge and so either $\varphi(x) = \varphi(y)$ or $\varphi(x), \varphi(y)$ is a dense pair in $H_{1}^{++}$.

For a graph $G$, let $\sca{D}G$ be the graph with vertex set $V(G)$ and with vertices $x$ and $y$ adjacent if $x, y$ is a dense pair in $G$. The previous paragraph shows that $\varphi$ maps any cycle in $\sca{D}T_{0}$ to a cycle, edge or single vertex in $\sca{D}H_{1}^{++}$. The graphs $\sca{D}T_{0}$ and $\sca{D}H_{1}^{++}$ are displayed below (we have used the same labelling of the vertices of $H_{1}^{++}$ as in <Ref>).

in 0,1,...,6

(*360/7 + 90:1.6)v_

in 0,1,...,6

(*360/7 + 90:1.5)v_

[below left = -2pt](ul)$a_{023}$
[below right = -2pt](ur)$a_{350}$

Now if $\varphi$ maps the 8-cycle $v_{0}v_{2}v_{4}v_{6}tv_{1}v_{3}v_{5}$ of $\sca{D}T_{0}$ to an edge or single vertex of $\sca{D}H_{1}^{++}$, then $\ssize{\varphi(T_{0})} \leqslant 4$ while $\chi(\varphi(T_{0})) \geqslant \chi(T_{0}) = 4$ so $\varphi(T_{0})$ is a 4-clique. However, $H_{1}^{++}$ is $K_{4}$-free, so

\begin{equation*}
\varphi(\set{v_{0}, v_{2}, v_{4}, v_{6}, t, v_{1}, v_{3}, v_{5}}) = \set{a_{1}, a_{023}, a_{4}, a_{350}, a_{6}, a_{2}, a_{5}} = V(H_{1}^{++}) - \set{a_{0}, a_{3}}.
\end{equation*}

Now $H_{1}^{++} - a_{0}$ and $H_{1}^{++} - a_{3}$ are both 3-colourable (they are both 2-degenerate) and $\chi(\varphi(T_{0})) \geqslant 4$, so $a_{0}, a_{3} \in \varphi(T_{0})$. In particular, $\varphi$ is surjective and $\varphi(\set{u_{1}, u_{6}}) = \set{a_{0}, a_{3}}$. By symmetry we may assume that $\varphi(u_{1}) = a_{0}$ and $\varphi(u_{6}) = a_{3}$. But then $\ssize{\varphi(\Gamma(u_{6}))} \leqslant \ssize{\Gamma(a_{3})} = 5$ and so

\begin{equation*}
\ssize{\varphi(T_{0})} \leqslant \ssize{\varphi(\Gamma(u_{6}))} + \ssize{\set{\varphi(u_{1}), \varphi(u_{6}), \varphi(v_{6})}} \leqslant 8 < \lvert H_{1}^{++} \rvert,
\end{equation*}

which contradicts the surjectivity of $\varphi$.