Immersions and Albertson’s Conjecture

We may assume that $k\ge 7$, since otherwise we obtain a weak immersion of $K_k$ by [16]. By possibly deleting vertices and edges, we may assume without loss of generality that $G$ is $k$-critical. Let $n=|V(G)|$ so $n\le 1.4(k-1)\le 2k-2$. By Lemma 5, there is a vertex partition $V(G)=V_1\cup \mathrm{\cdots }\cup V_t$, where $t\ge 2$, such that $V_i$ is complete to $V_j$ for each $i\ne j$, and the induced subgraph $G[V_i]$ is $k_i$-critical for each $i$ with $n_i\ge 2k_i-1$ vertices. Hence, $n={\sum }_{i=1}^t{n}_i$ and $k={\sum }_{i=1}^t{k}_i$. For each $i$, arbitrarily partition $V_i=U_i\cup W_i$ with $|U_i|=k_i$, so $|W_i|=n_i-k_i$. Let $U={\bigcup }_i{U}_i$.

In what follows, we will construct a weak immersion of $K_k$ with $U$ being the set of branch vertices. Moreover, we will use all edges in $U$ as paths of length one in the weak immersion. By the Gallai decomposition, each nonadjacent pair of vertices in $U$ has both of its vertices in $U_i$ for some $i$. For each $i$ and vertex $u\in U_i$, let $f_u$ be a one-to-one function from the set of non-neighbors of $u$ in $U_i\setminus \{u\}$ to the set of neighbors of $u$ in $W_i$. Such a function $f_u$ exists as the degree of $u$ in $G[V_i]$ is at least $k_i-1$, as $G[V_i]$ is $k_i$-critical. If a nonadjacent pair $(u,u^{\prime })$ of vertices in $U_i$ satisfies $f_u(u\mathrm{’})=f_{u^{\prime }}(u)$, then we connect $u$ and $u\mathrm{’}$ in the weak immersion by the path of length two with middle vertex $f_u(u\mathrm{’})$. Moreover, these paths will be edge-disjoint as $f_u$ is one-to-one. See Figure 1a.

So far we constructed edge-disjoint paths (which are of length one or two) connecting some pairs of branch vertices. We next describe how we connect the remaining pairs of vertices in $U$ by paths, which will each be of length four. For a pair $(u,u^{\prime })$ of nonadjacent vertices in $U_i$ with $f_u(u^{\prime })\ne f_{u^{\prime }}(u)$, we will pick a vertex $t\in U\setminus U_i$ and the path of length four connecting $u$ to $u^{\prime }$ will have the vertices in order as $u,f_u(u^{\prime }),t,f_{u^{\prime }}(u),u^{\prime }$. We next describe how to pick the vertex $t=t(u,u^{\prime })$ for each such pair $u,u^{\prime }$ of nonadjacent vertices in the same $U_i$ with $f_u(u^{\prime })\ne f_{u^{\prime }}(u)$. See Figure 1b.

Make an auxiliary multigraph $H_i$ on $W_i$ as follows. For each nonadjacent pair $(u,u\mathrm{’})$ with $u,u^{\prime }\in U_i$ and $f_u(u^{\prime })\ne f_{u^{\prime }}(u)$, we add an edge between $f_u(u^{\prime })$ and $f_{u^{\prime }}(u)$ in $H_i$. Clearly, $H_i$ does not contain loops as we require $f_u(u^{\prime })\ne f_{u^{\prime }}(u)$. Since $f_u$ is one-to-one, the maximum degree in $H_i$ is at most $|U_i|=k_i$. Being able to pick the desired vertex $t=t(u,u^{\prime })\in U\setminus U_i$ for each nonadjacent pair $u,u^{\prime }\in U_i$ with $f_u(u^{\prime })\ne f_{u^{\prime }}(u)$, in order to obtain the desired paths of length four for the immersion, is equivalent to being able to properly color the edges of $H_i$ with color set $U\setminus U_i$. As $n_i\ge 2k_i-1$, we have

where the last inequality follows from the fact that $n\le 1.4(k-1).$ This implies that

On the other hand, by Shannon’s theorem, we have ${\chi }^{\prime }(H_i)\le 3k_i/2\le 3(k-1)/5$. By combining the last two inequalities above, we have ${\chi }^{\prime }(H_i)\le |U\setminus U_i|$, and therefore, we are able to find such a proper edge-coloring, completing the proof. $◀$

Let $G$ be drawn in the plane with $\text{cr}(G)$ crossings. For a vertex $v$ of $G$, let $d(v)$ denote the degree of $v$ in $G$. By Theorem 2, $G$ contains $K_k$ as a weak immersion. Let $v_1,\mathrm{\dots },v_k$ be the branch vertices of the immersion, and let $P_{ij}$ be the path in $G$ used in the weak immersion with endpoints $v_i$ and $v_j$.

Consider a drawing of $K_k$ in the plane, with vertices $v_1,\mathrm{\dots },v_k$, where the edge between $v_i$ and $v_j$ is drawn along the path $P_{ij}$ such that it goes around every branch vertex that is an internal vertex of $P_{ij}$. By going either clockwise or counterclockwise around a branch vertex $v$, we can achieve that in the neighborhood of $v$, the drawing of the edge between $v_i$ and $v_j$ participates in at most $(d(v)-2)/2$ crossings. Apart from small neighborhoods of the branch vertices along the path $P_{ij}$, the drawing of the edge connecting $v_i$ to $v_j$ coincides with the drawing of $P_{ij}$. In particular, the drawing of the edge between $v_i$ and $v_j$ passes through every non-branch vertex that is an internal vertex of $P_{ij}$.

There are two types of crossings in this drawing of $K_k$. All crossings that are already crossings in the original drawing of $G$ are of type 1, so there are at most $\text{cr}(G)$ of them. The remaining crossings are of type 2. They occur in small neighborhoods of vertices of $G$. The latter crossings fall into two categories depending on whether they occur in a small neighborhood of a non-branch vertex or a branch vertex.

For non-branch vertices $v$, the number of crossings in the drawing of $K_k$ at $v$ is at most $\left(\genfrac{}{}{0pt}{}{f(v)}{2}\right)$, where $f(v)$ denotes the number of paths $P_{ij}$ in the $K_k$ immersion, in which $v$ is an internal vertex of the path $P_{ij}$. Note that $f(v)\le d(v)/2$, as $v$ is an internal vertex of at most $d(v)/2$ edge-disjoint paths. Obviously, $d(v)\le n-1$ and there are at most $n-k$ non-branch vertices. Therefore, at non-branch vertices, the total number of crossings of type 2 is at most

For each of the $k$ branch vertices $v_i$, there are $k-1$ paths $P_{ij}$ ending at $v_i$. Thus, $v_i$ is an internal vertex of at most $(d(v_i)-(k-1))/2\le (n-k)/2$ paths $P_{\mathrm{\ell }j}$. In the drawing of $K_k$, the edge from $v_{\mathrm{\ell }}$ to $v_j$ participates in at most crossings in the neighborhood of $v_i$, by going either clockwise or counterclockwise around $v_i$. Thus, in the neighborhoods of branch vertices, altogether there are at most

crossings of type 2.

Adding up the above two bounds and using our assumption that $n\le 1.4(k-1)$, we conclude that the total number of crossings in the drawing of $K_k$, which occur in small neighborhoods of the vertices of $G$ is at most . Thus, we have produced a drawing of $K_k$ with fewer than $\text{cr}(G)+k^3/3$ crossings. Consequently, we have

as desired. $◀$

The well-known crossing lemma discovered by Ajtai, Chvátal, Newborn, Szemerédi [2] and independently, by Leighton [18], states that every graph $G$ with $n$ vertices and $m\ge 4n$ edges satisfies $\text{cr}(G)\ge c{m}^3/n^2$, where $c>0$ is an absolute constant. The constant has been improved by several authors. The currently best constant is due to Büngener and Kaufmann.

We also need the following two simple lemmas.

If we take a uniform random subset $A$ of $a$ vertices, the expected number of edges in $A$ is $m\left(\genfrac{}{}{0pt}{}{a}{2}\right)/\left(\genfrac{}{}{0pt}{}{n}{2}\right)$, and hence, there is an induced subgraph with at least that many edges. $◀$

We are now ready to prove Theorem 4. We first prove a variant for $k$-critical graphs with at most $1.4(k-1)$ vertices.

The proof is by induction on $\mathrm{\ell }:=n-k$. The base case $\mathrm{\ell }=n-k=0$ is trivial, as in this case $G=K_k$. Let $\mathrm{\ell }$ be a positive integer and suppose we have established the desired result for smaller nonnegative integer values of $\mathrm{\ell }$. Let $k$ be a large constant that will be specified later, and let $G$ be a $k$-critical graph on $n\le 1.4(k-1)$ vertices with $n-k=\mathrm{\ell }$. By Lemma 5 (Gallai’s theorem), $G$ has a vertex partition

into $t\ge 2$ nonempty parts such that each $G[V_i]$ is $k_i$-critical with $n_i$ vertices with $n_i\ge 2k_i-1$, and every pair of vertices in different parts are adjacent. In particular, we have ${\sum }_{i=1}^t{k}_i=k$ and ${\sum }_{i=1}^t{n}_i=n$. Set $ϵ=1/8$, ${ϵ}^{\prime }=2^{-8}$, and $c=2^{-44}$, say. We distinguish three cases.

There is a part $V_i$ with .

Add missing edges to $V_i$, one at a time, until $V_i$ is complete. Each time we add an edge, we upper bound the increase of the crossing number by applying Lemma 10. As $G[V_i]$ is $k_i$-critical, each vertex in $G[V_i]$ has degree at least $k_i-1$. Hence, the number of nonadjacent pairs in $G[V_i]$ is at most $n_i(n_i-k_i)/2$. In total, by making $G[V_i]$ complete, we increase the crossing number by at most $n^2{n}_i(n_i-k_i)/4$. The resulting graph $G^{\prime }$, obtained by completing part $V_i$, has $n$ vertices and is $k^{\prime }$-critical with $k^{\prime }=k+n_i-k_i$. Thus,

where in the last inequality we used that $n\le 1.4(k-1)$, $n_i\le k/8$, and $c=2^{-44}.$

Applying the induction hypothesis to $G^{\prime }$, we obtain

Note that by averaging, we have

where in the last inequality we used Lemma 6.

Putting (1)–(3) together, we obtain

This completes the proof in this case.

There is a part $V_i$ with $k_i\ge {ϵ}^{\prime }k$.

Applying Theorem 2 to $G$, we obtain $K_k$ as a weak immersion in $G$. By the proof of Lemma 8, the number of crossings between the edges used in this weak immersion is at least

Furthermore, the proof of Theorem 2 shows that no matter how we partition part $V_i$ into $V_i=U_i\cup W_i$ with $|U_i|=k_i$, the edges in $G[W_i]$ are not used in the weak immersion. Note that $G[V_i]$ has minimum degree at least $k_i-1$, and hence, has at least $n_i(k_i-1)/2$ edges. By Lemma 11, we can pick this partition $V_i=W_i\cup U_i$ so that the number of edges in $G[W_i]$ is at least

As all three numbers $k$, $k_i\ge {ϵ}^{\prime }k$, and $n_i-k_i\ge k_i-1$ are sufficiently large, we have $m_i\ge 6.95(n_i-k_i)$. Thus, we can apply Lemma 9 to obtain that

We obtain that

In the last inequality, we used that $k$ is sufficiently large, $k_i\ge {ϵ}^{\prime }k$, $n_i-k_i\ge k_i-1$, $n\le 1.4(k-1)$, and $c\le 2^{-44}.$ This completes the proof in Case 2.

Each part $V_i$ is either a singleton or satisfies $n_i>ϵk$ and .

In this case, as $\mathrm{\ell }=n-k>0$, we must have at least one part that is not a singleton. Recall that and $n-k={\sum }_i(n_i-k_i)$. For every $i$ for which $V_i$ is not a singleton, we have $n_i-k_i>ϵk-{ϵ}^{\prime }k=(ϵ-{ϵ}^{\prime })k$. Thus, the number of parts that are not singletons is smaller than , which implies that there are at most three non-singleton parts.

Let $A$ be the union of the singleton parts and $B=V(G)\setminus A\ne \mathrm{\varnothing }$. Since $B$ is the union of non-singleton parts $V_i$, each of which is larger than $ϵk$, we have $|B|>ϵk$. The chromatic number of $G$ is $k$. The chromatic number of $G[B]$, the subgraph of $G$ induced by $B$, is smaller than $3{ϵ}^{\prime }k$. Using that $A\cup B$ is a vertex partition of $G$, we obtain that the chromatic number of $G[A]$ is larger than $k-3{ϵ}^{\prime }k$. As $G[A]$ is a clique, we have $|A|>k-3{ϵ}^{\prime }k=(1-3{ϵ}^{\prime })k$.

It follows by averaging over all cliques of size $k$ in $K_{k+1}$, just like in (3), that $\text{cr}(K_k)/\left(\genfrac{}{}{0pt}{}{k}{4}\right)$ is a monotonically increasing function. Since it is bounded from above, it must converge. As $|A|>(1-3{ϵ}^{\prime })k$, we obtain that

provided that $k$ is sufficiently large.

Notice that the clique $G[A]$ and the complete bipartite graph between $A$ and $B$ are disjoint subgraphs of $G$. Therefore, we get

Here the second inequality follows by substituting in the bound from Lemma 7 on the crossing number of complete bipartite graphs and using the bound $\text{cr}(K_k)\le k^4/64.$ The last inequality holds with $c=2^{-44}$, say, because $◀$

It suffices to prove the statement for $k$-critical graphs as every graph of chromatic number $k$ has a $k$-critical subgraph. So let $G$ be a $k$-critical graph with chromatic number $k$ with $n\le (1.4+\delta )k$ vertices. If $n\le 1.4(k-1)$, then the statement already follows from Theorem 12. So we may assume $1.4(k-1)\le n\le (1.4+\delta )k$.

Consider a proper $k$-coloring of $G$. Let $k^{\prime }=(1-3\delta )k$. Let $A$ be the union of the $3\delta k$ largest color classes of this proper $k$-coloring. Either each of these color classes has size at least two, or the remaining color classes forms a clique on $k^{\prime }$ vertices.

In the first case, $|A|\ge 6\delta k$, and the remaining induced subgraph after deleting $A$ has chromatic number $k^{\prime }$. Let $B$ be the vertex set of a $k^{\prime }$-critical subgraph of the induced subgraph on $V(G)\setminus A$. Observe that

provided that $\delta k\ge 7/4$, which holds as $k$ is sufficiently large. By Theorem 12, the induced subgraph on $B$ has crossing number at least $\text{cr}(K_{k^{\prime }})+c(|B|-k^{\prime })k^{\prime 3}$, where $c>0$ is an absolute constant (We have seen that $c=2^{-44}$ will do.) If $|B|\ge 1.2k$, this induced subgraph already has crossing number at least

where we used $\delta =2^{-45}$. Otherwise, as $G$ is $k$-critical, each vertex of $G$ has degree at least $k-1$, and there at least $(n-|B|)(k-1)/2\ge k^2/16$ edges not in $G[B]$. Let $G_0$ denote the subgraph of $G$ consisting of the edges of $G$ not in $G[B]$. Applying the crossing number bound (Lemma 9) to $G_0$ and using , we obtain that

Then

where we used $\delta =2^{-45}$.

In the second case, $|A|=n-k^{\prime }$ and the edges between $A$ and $B$ form a complete bipartite graph in $G$ with $|A|\ge 2k/5$ and $|B|\ge 4k/5$. This complete bipartite graph has crossing number at least $k^4/200$ by Lemma 7. Together with the $\text{cr}(K_{k^{\prime }})$ crossings between the edges of the clique of size $k^{\prime }$, we obtain

$◀$