# Grid-drawings of graphs in three-dimensions

József Balogh  Department of Mathematics
University of Illinois Urbana-Champaign
1409 W. Green Street, Urbana IL 61801
United States<EMAIL_ADDRESS>and  Ethan Patrick White  Department of
Mathematics
University of Illinois Urbana-Champaign
1409 W. Green Street, Urbana IL 61801
United States<EMAIL_ADDRESS>
###### Abstract.

Using probabilistic methods, we obtain grid-drawings of graphs without
crossings with low volume and small aspect ratio. We show that every
$D$-degenerate graph on $n$ vertices can be drawn in $[m]^{3}$ where
$m=O(D^{5/3}n^{1/3}\log^{4/3}n)$. In particular, every graph of bounded
maximum degree can be drawn in a grid with volume $O(n\log^{4}n)$.

Balogh was supported in part by NSF grants DMS-1764123 and RTG DMS-1937241,
FRG DMS-2152488, the Arnold O. Beckman Research Award (UIUC Campus Research
Board RB 24012).

White is supported in part by an NSERC Postdoctoral Fellowship

##  1\. Introduction

A _grid-drawing_ of a graph $G$ is a representation of $G$ where vertices are
distinct points of $\mathbb{Z}^{d}$ and edges are straight-line segments such
that

  1. (i)

no edge intersects a vertex that it is not adjacent to in $G$;

  2. (ii)

no pair of edges have a common interior point.

The study of three-dimensional grid-drawings is in part motivated by problems
in circuit architecture [13] and data visualization [16].

For a positive integer $m$, let $[m]$ denote the set $\\{0,1,\ldots,m-1\\}$.
In contrast to the planar setting, a construction using a moment curve shows
that every $n$-vertex graph can be drawn in a $[n]\times[2n]\times[2n]$ grid,
and the size of this grid is tight up to a multiplicative constant [3]. Grid-
drawings have been studied with respect to many graph parameters, including
maximum degree, genus, path-width, and chromatic number [7, 9, 10, 11, 14].
Typically, we are interested in grid-drawings of minimum volume, and also
small aspect ratio, i.e., the ratio between the longest and shortest sides of
the grid. For a positive integer $D$, we say a graph $G$ is $D$-_degenerate_
if every subgraph of $G$ has a vertex of degree at most $D$. A long-standing
open problem of Pach, Thiele, and Tóth [14] is to determine if all graphs of
maximum degree $3$ have a grid-drawing with $O(n)$ volume. Our main result
resolves this problem up to logarithmic factors.

######  Theorem 1.

Let $G$ be a $D$-degenerate graph with $n$-vertices and $k$ edges. Then there
is a grid-drawing of $G$ in $[m]^{3}$ where
$m=O(D^{4/3}k^{1/3}\log^{4/3}n+Dn^{1/3}\log^{2/3}n)$.

Bose, Czyzowicz, Morin, and Wood [1] show that the maximum number of edges in
a grid-drawing is bounded by eight times the volume of the grid, and therefore
our bound is tight up to the logarithmic and degeneracy factors. The previous
best bound on the volume of a grid-drawing of bounded degeneracy graphs was
$O(n^{3/2})$. More precisely, it is known that there exists a grid-drawing of
every $D$-degenerate graph with $n$ vertices and $k$ edges in grids of volume
$O(D^{15/2}nk^{1/2})$ and $O(Dnk)$ [10, 11]. Our Theorem 1 is always an
improvement on the first of these bounds, and is an improvement on the latter
for $D\leq n^{1/3}\log^{-4/3}n$. Moreover, the grid-drawings behind these two
earlier bounds have large aspect ratios; there is a side of the grid with
length $\Omega(n)$.

Felsner, Liotta, and Wismath [12] posed the problem of determining if all
planar graphs on $n$ vertices can be drawn in a 3-dimensional grid with $O(n)$
volume. All progress on this problem was made by constructing so-called
_track-layouts_. Recent progress includes a volume bound of $O(n\log^{8}n)$ of
Di Battista, Frati, and Pach [4], and a bound of $O(n\log n)$ of Dujmović [6].
A breakthrough of Dujmović Joret, Micek, Morin, Ueckerdt, Wood [7] fully
resolved this conjecture by showing there exists a drawing of every $n$-vertex
planar graph in a grid with dimensions $O(1)\times O(1)\times O(n)$. In
general, the track-layout method produces a grid-drawing with one very large
dimension. In [3] the authors pose the problem of deciding if every
3-dimensional grid-drawing of an $n$-vertex planar graph requires all sides of
the grid to be $\Omega(n)$. Since planar graphs are $5$-degenerate, Theorem 1
shows that every planar graph can be drawn in a grid with all sides
$O(n^{1/3}\log^{4/3}n)$, thereby resolving this problem in a strong way.

Our method is to use random embeddings of graphs in grids. To determine the
probability that our embeddings do not have edge crossings we require
estimates on the number of point-tuples on affine subspaces in grids. In
Section 2 we prove the necessary lemmata about point-tuples. In Section 3 we
verify our probabilistic constructions. In Section 4 we discuss continuations
of this work and some other open problems.

##  2\. Counting tuples on affine subspaces

Edges that pass through other vertices are forbidden in our drawings. As a
result, we require an estimate on collinear triples. Versions of the following
lemma have appeared in the literature, see for example [17].

######  Lemma 2.

Let $d,k,m\geq 2$ be positive integers and $C_{d,k,m}$ denote the number of
collinear $k$-tuples in $[m]^{d}$. Then

$C_{d,k,m}=\begin{cases}O(m^{d+k-1})&\text{ if }k\geq d+2\\\ O(m^{d+k-1}\log
m)&\text{ if }k=d+1\\\ O(m^{2d})&\text{ if }d\geq k,\end{cases}$

where the implicit constants may depend on $d$ and $k$ but not $m$.

###### Proof.

By the symmetry of $[m]^{d}$, it is sufficient to count collinear tuples on a
line through the origin and then multiply by $m^{d}$. Let $v\in\mathbb{Z}^{d}$
be the direction of a line intersecting at least $k$ points of $[m]^{d}$. Note
that $\|v\|_{\infty}\leq m$. For each $1\leq s\leq m$, the number of choices
for $v$ such that $\|v\|_{\infty}=s$ is at most $ds^{d-1}$. Since the number
of points of $[m]^{d}$ on a line in direction $v$ is $\lceil
m/\|v\|_{\infty}\rceil$, the number of collinear tuples on lines through the
origin is at most

$\sum_{s=1}^{m}ds^{d-1}\left\lceil\frac{m}{s}\right\rceil^{k-1}\leq
d(2m)^{k-1}\sum_{s=1}^{m}s^{d-k}.$

After multiplying by $m^{d}$, the claimed bounds follow.

∎

If two edges cross in a three-dimensional graph drawing, then these edges lie
in a common plane. For this reason we need an estimate on the number of
coplanar four-tuples in grids. In the setting of arbitrary $N$ point sets with
at most $O(N^{1/2})$ coplanar points, Cardinal, Tóth, and Wood obtain a bound
on the number of coplanar four-tuples in $\mathbb{R}^{d}$ that matches the
bound given by our Proposition 4 for $d=3$ [2, Lemma 4.5]. A recent result of
Suk and Zeng improves the upper bound for the number of points in general
position in $d$-dimensional integer grids [15, Theorem 1.3].

######  Lemma 3.

Let $d\geq 2$ be a positive integer, and $a_{1},\ldots,a_{d}\in\mathbb{Z}$ not
be all zero with greatest common denominator 1. Let

$\mathcal{L}=\\{(x_{1},\ldots,x_{d})\in\mathbb{Z}^{d}\colon\sum_{i=1}^{d}a_{i}x_{i}=0\\}.$

Let $s=\max_{i}\\{|a_{i}|\\}$, and $m\geq s$ be a positive integer. If
$\mathcal{L}\cap[m]^{d}$ spans a $(d-1)$-dimensional subspace, then
$|\mathcal{L}\cap[m]^{d}|\leq 3^{d}m^{d-1}/s$.

###### Proof.

Since $\mathcal{L}$ is a $(d-1)$-dimensional subspace we can find linearly
independent vectors $v_{1},\ldots,v_{d-1}\in\mathbb{Z}^{d}$ such that

$\mathcal{L}=\text{span}_{\mathbb{Z}}\\{v_{1},\ldots,v_{d-1}\\}.$

Moreover, since $\mathcal{L}\cap[m]^{d}$ spans a $(d-1)$-dimensional subspace
the $v_{i}$ can be chosen such that $\|v_{i}\|_{\infty}\leq m$ for all $1\leq
i\leq d-1$. Let $b\in\mathbb{R}^{d}$ be the unique vector such that for all
$x\in\mathbb{R}^{d}$:

$\langle b,x\rangle=\det(v_{1},\ldots,v_{d-1},x).$ (1)

It is straightforward to check that $b$ exists and is unique by taking $x$ to
be standard basis vectors. Since $b$ is perpendicular to $\mathcal{L}$, we see
that $a=(a_{1},\ldots,a_{d})$ and $b$ must be parallel. Moreover, since
$b\in\mathbb{Z}^{d}$ and the greatest common denominator of the entries in $a$
is 1, we conclude that $|b_{i}|\geq|a_{i}|$ for all $1\leq i\leq d$. Suppose
that $a_{d}\neq 0$ and so the projection of $\mathcal{L}$ to the first $d-1$
coordinates, call it $\mathcal{L}_{d}$, is a bijection. For $1\leq i\leq d-1$,
let $v_{i}^{(d)}\in\mathbb{R}^{d-1}$ be the vector $v_{i}$ with $d^{th}$
coordinate deleted. Observe that

$\mathcal{L}_{d}=\text{span}_{\mathbb{Z}}\\{v_{1}^{(d)},\ldots,v_{d-1}^{(d)}\\},$

and $|\mathcal{L}\cap[m]^{d}|=|\mathcal{L}_{d}\cap[m]^{d-1}|$. The fundamental
parallelepiped of $\mathcal{L}_{d}$ is the set

$\mathcal{P}_{d}=\left\\{\sum_{i=1}^{d-1}x_{i}v_{i}^{(d)}\colon 0\leq
x_{i}<1\right\\}.$

Let

$\mathcal{T}_{d}=\bigcup_{\begin{subarray}{c}t\in\mathcal{L}_{d}\\\
(\mathcal{P}_{d}+t)\cap\mathcal{L}_{d}\cap[m]^{d-1}\neq\emptyset\end{subarray}}(\mathcal{P}_{d}+t),$

be the union of all integer vector translates of $\mathcal{P}_{d}$ that have
nonempty intersection with $\mathcal{L}_{d}\cap[m]^{d-1}$. Since all entries
of all vectors in $\\{v_{i}\\}_{1\leq i\leq d-1}$ at most $m$ in absolute
value, we conclude that $\mathcal{T}_{d}\subseteq[-m,2m]^{d-1}$. Hence the
number of translates of $\mathcal{P}_{d}$ comprising $\mathcal{T}_{d}$ is at
most $(3m)^{d-1}/|\mathcal{P}_{d}|$, and consequently
$(3m)^{d-1}/|\mathcal{P}_{d}|$ is also an upper bound for
$|\mathcal{L}_{d}\cap[m]^{d-1}|$. Note that from (1) by taking $x$ to be the
$d^{th}$ elementary basis vector, we see
$|b_{d}|=\det(v_{1}^{(d)},\ldots,v_{d}^{(d)})=|\mathcal{P}_{d}|$. From
$|a_{d}|\leq|b_{d}|$ we conclude $|\mathcal{L}\cap[m]^{d}|\leq
3^{d}m^{d-1}/|a_{d}|$. Moreover, as this argument can repeated for any non-
zero coordinate of $a$, we conclude that $|\mathcal{L}\cap[m]^{d}|\leq
3^{d}m^{d-1}/s$.

∎

######  Proposition 4.

Let $m$ be a positive integer, the number of 3-tuples in $[m]^{3}$ that are
coplanar with the origin is $O(m^{6}\log m)$. Moreover, the number of coplanar
4-tuples in $[m]^{3}$ is $O(m^{9}\log m)$.

###### Proof.

The claimed bound on the number of coplanar $4$-tuples follows from the bound
on $3$-tuples on a common plane through the origin by symmetry of $[m]^{3}$.
We may restrict our attention to the case when the $3$-tuple spans a
$2$-dimensional subspace, since the number of collinear $3$-tuples through the
origin is $O(m^{3}\log m)$ by Lemma 2. Let $a\in\mathbb{Z}^{3}$ be the normal
of a plane through the origin intersecting at least three other points in
$[m]^{3}$. By Lemma 3 the number of points on such a plane is at most
$27m^{2}/\|a\|_{\infty}$. Since the vector $a$ can be determined as the cross-
product of two integer vectors in $[m]^{3}$, we know that $\|a\|_{\infty}\leq
m^{2}$. For $1\leq s\leq m^{2}$, the number of choices of such normal vector
$a$ with $\|a\|_{\infty}=s$ is at most $3s^{2}$. Putting these estimates
together, the number of $3$-tuples on a plane through the origin is bounded
above by

$\sum_{s=1}^{m^{2}}\left(\frac{27m^{2}}{s}\right)^{3}\cdot 3s^{2}=O(m^{6}\log
m).$

∎

##  3\. Probabilistic grid-drawings

All of our constructions use randomness. For an $n$-vertex graph $G$ and grid
$[m]^{3}$ we define a _random embedding_ to be a uniformly sampled embedding
of the vertices of $G$ into $[m]^{3}$ out of all $\binom{m^{3}}{n}n!$ possible
embeddings. Throughout this section we will use $\hat{G}$ to denote a random
embedding of $G$. Given a random embedding $\hat{G}$ in $[m]^{3}$, we say an
edge is in a _conflict_ if either (i) another edge intersects its interior; or
(ii) it contains a vertex in its interior. If no edge has a conflict in an
embedding, then $\hat{G}$ is a grid-drawing. Our next result is a toy-version
of our main theorem. It uses the tools from Section 2 in a similar way to the
proof of Theorem 1.

######  Theorem 5.

There exists an absolute constant $C$ such that the following holds. For every
graph $G$ on $n$ vertices with $k$ edges, if $m$ is a positive integer such
that $m\geq C((nk)^{1/3}+k^{2/3}(\log k)^{1/3})$, then there is a grid-drawing
of $G_{n}$ in $[m]^{3}$.

###### Proof.

Let $G$ be an $n$-vertex graph with $k$ edges, $m>n^{1/3}$ be a positive
integer to be determined later, and $\hat{G}$ be a random grid-drawing of $G$
in $[m]^{3}$. We estimate the expected number of edges of $\hat{G}$ in a
conflict. Let $e,u$ be an edge and vertex in $G$ where $u$ is not incident to
$e$. Fix a triple of collinear points $x,y,z\in[m]^{3}$ where $y$ is between
$x,z$. The probability that in $\hat{G}$ the endpoints of $e$ map to $x,z$ and
$u$ maps to $y$ is

$\frac{2(m^{3}-3)(m^{3}-4)\cdots(m^{3}-n+1)}{m^{3}(m^{3}-1)\cdots(m^{3}-n+1)}=O(m^{-9}).$

By Lemma 2, the number of collinear triples in $[m]^{3}$ is $O(m^{6})$. Since
the number of edge-vertex pairs in $G$ is $nk$ we conclude that the expected
number of edge-vertex pairs in $\hat{G}$ such that the vertex is in the
interior of the edge is $O(nkm^{-3})$. Similarly, the probability that a
particular pair of edges in $G$ are randomly assigned to a particular
collinear $4$-tuple in $[m]^{3}$ is

$\frac{24(m^{3}-4)(m^{3}-5)\cdots(m^{3}-n+1)}{m^{3}(m^{3}-1)\cdots(m^{3}-n+1)}=O(m^{-12}).$

By Proposition 4, there are $O(m^{9}\log m)$ collinear 4-tuples in $[m]^{3}$.
Since the number of edge pairs is $O(k^{2})$ we see that the expected number
of edges in conflict is

$O\left(m^{-3}\cdot nk+m^{-3}\log m\cdot k^{2}\right).$

It follows that there exists a constant $C$ such that if $m\geq
C((nk)^{1/3}+k^{2/3}(\log k)^{1/3})$, then the expected number of edges in a
conflict is less than $1$, and so there is a grid-drawing of $G$ in $[m]^{3}$.

∎

Since the number of edges in a planar graph is at most $3n$, Theorem 5 shows
that every planar graph can be drawn in a grid with all sides $O(n^{2/3}(\log
n)^{2/3})$, thereby answering Question 2 of Cohen, Eades, Lin, and Ruskey [3].
To prove our main theorem, we begin with a random embedding of the blow-up of
a graph, and then greedily find a copy of our graph without any edge
conflicts.

Let $G$ be an $n$-vertex graph with vertices $v_{1},\ldots,v_{n}$. For a
positive integer $t$, the $t$-blowup $G(t)$ of $G$ has $nt$ vertices, where
the vertices are partitioned into $n$ sets $V_{1},\ldots,V_{n}$ each of size
$t$. If $v_{i}v_{j}$ is an edge in $G$ then every pair of vertices in
$V_{i},V_{j}$ is an edge. For a subset of vertices $S$ in $G_{n}$ we denote by
$G_{n}[S]$ the subgraph of $G_{n}$ induced by $S$. If $G$ is a $D$-degenerate
graph then there exists an ordering of the vertices $v_{1},\ldots,v_{n}$ of
$G$ such that the degree of $v_{i}$ in $G_{n}[v_{i},\ldots,v_{n}]$ is at most
$D$. For the rest of this section, the vertices of $D$-degenerate graphs will
always be labeled in this way. This ordering is called a _degeneracy
ordering_. In a $t$-blowup of $G$, and a subset
$S\subseteq\\{V_{1},\ldots,V_{n}\\}$ of the cloned vertex sets, we use
$G(t)[S]$ to denote the subgraph of $G(t)$ induced by the vertices in
$\cup_{i\in S}V_{i}$.

In the following lemma we prove that few edges are in a conflict for a random
embedding of a blow-up. By Proposition 4 there is a constant $C_{1}$ such that
for any point $v\in[m]^{3}$ the number of triples coplanar to $v$ is at most
$C_{1}m^{6}\log m$. By Lemma 2, there is a constant $C_{2}$ such that for any
point $v\in[m]^{3}$ the number of pairs of points collinear to $v$ is at most
$C_{2}m^{3}$. We will use the constants $C_{1},C_{2}$ below.

######  Lemma 6.

Let $G$ be an $n$-vertex graph with $k$ edges and degeneracy $D$. Suppose
$\epsilon>0$ is such that

$n^{1+\epsilon/(3-\epsilon)}=\max\left\\{300C_{1}D^{4}k\log^{4}n,160C_{2}D^{3}n\log^{2}n\right\\}.$

Let $\ell=\lceil\frac{1}{3}\log Dn\rceil$, $t=D\ell$, and $m=\lceil
n^{1/3+\epsilon/(9-3\epsilon)}\rceil$. Let $\hat{G}(t)$ be a random embedding
of the $t$-blowup $G(t)$ in $[m]^{3}$. Then with probability at least $1/2$
for every $1\leq i\leq n$ and every $v\in V_{i}$, the number of edges incident
to $v$ in a conflict in the subgraph $\hat{G}(t)[V_{i},\ldots,V_{n}]$ is less
than $\ell$.

###### Proof.

Note that $nt<m^{3}$ and so it is possible to embed $G(t)$ in $[m]^{3}$. Fix
$1\leq i\leq n$ and choose an arbitrary vertex $v\in V_{i}$. In
$G(t)[V_{i},\ldots,V_{n}]$, choose an arbitrary $\ell$-tuple
$(e_{i})_{i=1}^{\ell}$ of edges incident to $v$, and a second $\ell$-tuple of
edges $(e_{i}^{\prime})_{i=1}^{\ell}$ not incident to $v$. We estimate the
probability $P_{\text{cross}}$ that in $\hat{G}(t)$ each $e_{i}^{\prime}$ is
crossed by $e_{i}$ in its interior. The number of choices to embed $v$ is
$m^{3}$. Let $(T_{1},\ldots,T_{\ell})$ be an $\ell$-tuple of point triples
such that $T_{i}\cup\\{v\\}$ is a set of four coplanar points for all $1\leq
i\leq\ell$. The number of ways to embed $e_{i},e_{i}^{\prime}$ in $T_{i}$ is
6. By Proposition 4 the total number of $\ell$-tuples
$(T_{1},\ldots,T_{\ell})$ is less than $C_{1}^{\ell}m^{6\ell}\log^{\ell}m$. It
follows that

$\displaystyle P_{\text{cross}}$ $\displaystyle\leq\frac{m^{3}\cdot
C_{1}^{\ell}m^{6\ell}\log^{\ell}m\cdot
6^{\ell}(m^{3}-3\ell-1)\cdots(m^{3}-n+1)}{m^{3}(m^{3}-1)\cdots(m^{3}-n+1)}$
$\displaystyle\leq\frac{6^{\ell}C_{1}^{\ell}m^{6\ell}\log^{\ell}m}{(m^{3}-3\ell)^{3\ell}}\leq\frac{6^{\ell}C_{1}^{\ell}m^{6\ell}\log^{\ell}m}{m^{9\ell}(1-9m^{-3}\ell^{2})}\leq
2\cdot 6^{\ell}C_{1}^{\ell}m^{-3\ell}\log^{\ell}m.$

The number of ways to choose $(e_{i})_{i=1}^{\ell}$ is at most $(Dt)^{\ell}$.
The number of ways to choose $(e_{i}^{\prime})_{i=1}^{\ell}$ is at most
$(kt^{2})^{\ell}$. Therefore the probability that $v$ is incident to at least
$\ell$ crossed edges is less than

$P_{\text{cross}}\cdot(Dt)^{\ell}\cdot(kt^{2})^{\ell}\leq 2\cdot
6^{\ell}C_{1}^{\ell}D^{4\ell}k^{\ell}\ell^{3\ell}m^{-3\ell}\log^{\ell}m.$ (2)

The only other way that an edge incident to $v$ can be in a conflict is if
another vertex lies in its interior. Fix an $\ell$-tuple of vertices
$(u_{i})_{i=1}^{\ell}$ in $G(t)$. We estimate the probability $P_{\text{int}}$
that in $\hat{G}(t)$ each $e_{i}$ contains $u_{i}$ in its interior. Let
$(S_{1},\ldots,S_{\ell})$ be an $\ell$-tuple of point pairs such that
$S_{i}\cup\\{v\\}$ is a set of three collinear points for all $1\leq
i\leq\ell$. The number of ways to embed $u_{i},e_{i}$ in $S_{i}$ is $2$. By
Lemma 2 the total number of $\ell$-tuples $(S_{1},\ldots,S_{\ell})$ is less
than $C_{2}^{\ell}m^{3\ell}$. It follows that

$P_{\text{int}}\leq\frac{m^{3}\cdot C_{2}^{\ell}m^{3\ell}\cdot
2^{\ell}(m^{3}-2\ell-1)\cdots(m^{3}-n+1)}{m^{3}(m^{3}-1)\cdots(m^{3}-n+1)}\leq
2\cdot 2^{\ell}C_{2}^{\ell}m^{-3\ell}.$

Since the number of $\ell$-tuple of vertices in $G(t)$ is at most
$(nt)^{\ell}$ the probability that $v$ is incident to at least $\ell$ edges
each containing another vertex in their interior is less than

$P_{\text{int}}\cdot(Dt)^{\ell}\cdot(nt)^{\ell}\leq 2\cdot
2^{\ell}C_{2}^{\ell}D^{3\ell}\ell^{2\ell}m^{-3\ell}n^{\ell}.$ (3)

We finish by using the estimates (2), (3) together with the union bound over
all $nt$ vertices. For any choice $1\leq i\leq n$, and vertex $v\in V_{i}$,
the probability that at least $\ell$ edges incident to $v$ are in a conflict
in $\hat{G}(t)[V_{i},\ldots,V_{n}]$ is at most

$nt\cdot 2\cdot
6^{\ell}C_{1}^{\ell}D^{4\ell}k^{\ell}\ell^{3\ell}m^{-3\ell}\log^{\ell}m+nt\cdot
2\cdot 2^{\ell}C_{2}^{\ell}D^{3\ell}\ell^{2\ell}m^{-3\ell}n^{\ell}.$ (4)

To bound the above, we consider the $1/\ell$-power of the two terms. The first
is:

$\displaystyle\hskip 15.36429pt6C_{1}\cdot(Dn\ell)^{1/\ell}\cdot\ell^{3}\cdot
2^{1/\ell}\cdot D^{4}k\log m\cdot m^{-3}$ $\displaystyle\leq
6C_{1}\cdot(Dn)^{3/\log(Dn)}\cdot\left((1/3)\log
Dn\right)^{3}\cdot(2\ell)^{1/\ell}\cdot D^{4}k\log n\cdot
n^{-1-\epsilon/(3-\epsilon)}$ $\displaystyle\leq 75C_{1}\cdot
D^{4}k\log^{4}n\cdot n^{-1-\epsilon/(3-\epsilon)}<1/4,$

where the final inequality follows from our choice of $\epsilon$. The
$1/\ell$-power of the second term in (4) is

$\displaystyle\hskip 15.36429pt2C_{2}\cdot(Dn\ell)^{1/\ell}\cdot\ell^{2}\cdot
2^{1/\ell}\cdot D^{3}n\log m\cdot m^{-3}$ $\displaystyle\leq
2C_{2}\cdot(Dn)^{3/\log(Dn)}\cdot\left((1/3)\log
Dn\right)^{2}\cdot(2\ell)^{1/\ell}\cdot D^{3}n\log n\cdot
n^{-1-\epsilon/(3-\epsilon)}$ $\displaystyle\leq 40C_{2}\cdot
D^{3}k\log^{3}n\cdot n^{-1-\epsilon/(3-\epsilon)}<1/4.$

It follows that (4) is at most $2^{-2\ell+1}<1/2$, as required. In fact,
$2^{-2\ell+1}<2\cdot n^{-0.46}$, and so the conclusion of the lemma holds with
probability tending to 1 as $n\to\infty$.

∎

The main idea behind the proof of Theorem 1 can be described by the following
randomized algorithm.

######  Algorithm 1.

  1. 1:

Input: $n$-vertex graph $G$ with degeneracy $D$ and $k$ edges.

  2. 2:

Find minimum $\epsilon>0$ such that

$n^{1+\epsilon/(3-\epsilon)}=\max\left\\{300C_{1}D^{4}k\log^{4}n,160C_{2}D^{3}n\log^{2}n\right\\}.$

Put $\ell=\lceil\frac{1}{3}\log Dn\rceil$, $t=D\ell$, and $m=\lceil
n^{1/3+\epsilon/(9-3\epsilon)}\rceil$.

  3. 3:

Construct $\hat{G}(t)$, a random embedding of the $t$-blowup $G(t)$ in
$[m]^{3}$. Let $V_{1},\ldots,V_{n}$ be the sets of $t$ vertices corresponding
to a vertex in $G$, where these sets are labelled according to a degeneracy
ordering for $G$.

  4. 4:

Initialize $H=\emptyset$. For $i=n,n-1\ldots,1$:

    1. i.

Select an arbitrary (undeleted) vertex in $v_{i}\in V_{i}$ and add it to $H$.

    2. ii.

For every vertex $w$ in $\hat{G}(t)$ such that $v_{i}w$ is an edge in a
conflict, delete the vertex $w$.

  5. 5:

Output: $H$.

###### Proof of Theorem 1.

We show that with probability at least $1/2$, Algorithm 1 outputs a set of
vertices that induce a grid-drawing of $G$. By Lemma 6, with probability at
least $1/2$, every vertex of $\hat{G}(t)$ is incident to less than $\ell$
edges with a conflict. Note that $\hat{G}(t)[H]$, i.e, the embedded graph
induced by the outputted vertex set $H$ does not have any edge in a conflict
because of Step 4.ii. It remains to show that Step 4.i can always be carried
out, i.e., there is vertex $v_{i}\in V_{i}$ after all previous deletions. When
carrying out iteration $i$ of Step 4, vertices in $V_{i}$ have been deleted in
at most $D$ previous iterations of Step 4. Therefore at iteration $i$, less
than $D\ell$ vertices from $V_{i}$ have been deleted. Since $t=D\ell$, there
is a vertex that can be selected and it will not form a conflicting edge with
any of the previously chosen vertices in $H$.

∎

##  4\. Open problems

  1. 1.

May the dependence on $D$ in Theorem 1 be improved? Can the logarithmic term
be removed? A positive answer to this second question would fully resolve the
problem of Pach, Thiele, and Tóth [14]. Dujmović, Morin, and Sheffer [8]
estimate $\text{ncs}_{d}(N)$, i.e., the number graphs that can be drawn in a
grid with volume $N$ in dimension $d\geq 4$. They pose the problem of
estimating $\text{ncs}_{3}(N)$, attributed to D. R. Wood, and show that if
$\text{ncs}_{3}(N)=2^{o(N\log N)}$ then not every $n$-vertex graph with
maximum degree 3 can be drawn in an $O(n)$ volume grid.

  2. 2.

Another open problem of Pach, Thiele, and Tóth [14] is the following. What is
the smallest $m=m(n)$ such that $K_{n,n}$ can be drawn in $[m]^{3}$? It is
known that $K_{n,n}$ can be drawn in a $O(\sqrt{n})\times O(\sqrt{n})\times
O(n)$ grid, and that a volume of $\Omega(n^{2})$ is necessary. No grid-
drawings with an aspect ratio of less than $\sqrt{n}$ are known.

  3. 3.

In [10] the authors ask if every $n$-vertex graph with $k$ edges can be drawn
in a grid with volume $O(kn)$. Theorem 1 answers this affirmatively for
$D$-degenerate graphs with $D=O(n^{1/4}\log^{-1}n)$.

## Acknowledgements

The authors thank Fabrizio Frati for introducing us to various problems on
three-dimensional graph drawing, and thank Martin Balko for helpful
conversations. The authors are also grateful to Andrew Suk for organizing
_Workshop on Graph Drawing and Intersection Graphs_ at UCSD from January
20–21, 2024.

## References

  * [1] P. Bose, J. Czyzowicz, P. Morin, D. R. Wood, The maximum number of edges in a three-dimensional grid-drawing. _J. Graph Algorithms Appl._ 8(1) (2004) 21–26. MR2112260
  * [2] J. Cardinal, Cs. D. Tóth, D. R. Wood, General position subsets and independent hyperplanes in d-space. _J. Geometry_ 108 (2017) 33–43. MR3631869
  * [3] R. F. Cohen, P. Eades, T. Lin, R. Ruskey, Three-dimensional graph drawing. Algorithmica 17(2) (1996) 199–208. MR1425733
  * [4] G. Di Battista, F. Frati, J. Pach, On the queue number of planar graphs. SIAM J. Comput. 42(6) (2013) 2243–2285.
  * [5] W. Didimo, G. Liotta, F. Montecchiani, A Survey on Graph Drawing Beyond Planarity. ACM Comput. Surv. 52(1), Art. 4 (2019).
  * [6] V. Dujmović, Graph layouts via layered separators. J. Combin. Theory Series B. 110 (2015) 79–89. MR3279388
  * [7] V. Dujmović, G. Joret, P. Micek, P. Morin, T. Ueckerdt, D. Wood, Planar graphs have bounded queue-number. J. ACM 67(4) (2020). MR4148600
  * [8] V. Dujmović, P. Morin, A. Sheffer, Crossings in grid drawings. _Electron. J. Combin._ 21(1) (2014). MR3177536
  * [9] V. Dujmović, P. Morin, D. R. Wood, Path-Width and Three-Dimensional Straight-Line Grid Drawings of Graphs. In M.T. Goodrich, S.G. Kobourov, eds., _Proc. 10th Int’l Symp. on Graph Drawing_ (GD’02), volume 2528 of _Lecture Notes in Comput. Sci._ , 42–53. Springer, 2002.
  * [10] V. Dujmović, D. R. Wood, Three-dimensional grid drawings with sub-quadratic volume. In János Pach, ed., Towards a Theory of Geometric Graphs, volume 342 of Contemporary Mathematics, pp. 55–66. Amer. Math. Soc., 2004.
  * [11] V. Dujmović, D. R. Wood, Upward three-dimensional grid drawings of graphs. Order 23(1) (2006) 1–20. MR2258457
  * [12] S. Felsner, G. Liotta, S. K. Wismath, Straight-line drawings on restricted integer grids in two and three dimensions. In P. Mutzel, M. Jünger, S. Leipert, eds., _Proc. 9th Int’l Symp. on Graph Drawing_ (GD’01), volume 2265 of _Lecture Notes in Comput. Sci._ , 328–342. Springer, 2002.
  * [13] F. T. Leighton, A. L. Rosenberg, Three-dimensional circuit layouts. _SIAM J. Comput._ 15(3) (1986) 793–813. MR0850424
  * [14] J. Pach, T. Thiele, G. Tóth, Three-dimensional grid drawings of graphs. In G. Di Battista, ed., _Proc. 5th Int’l Symp. On Graph Drawing_ (GD’97), volume 1353 of _Lecture Notes in Comput. Sci._ , 47–51. Springer, 1997.
  * [15] A. Suk, J. Zeng, On higher dimensional point sets in general position, in: E. W. Chambers, J. Gudmundsson, eds., $39^{th}$ ISCG, Schloss Dagstuhl, 2023. MR4603985
  * [16] C. Ware, P. Mitchell, Visualizing graphs in three dimensions. _ACM Trans. Appl. Percept._ 5(1) (2008).
  * [17] Z. Zheng, A note on arrays of dots with distinct slopes. _Combinatorica_ 13(1) (1993) 127–128.


# Vertex-critical graphs far from edge-criticality

Anders Martinsson  and  Raphael Steiner

###### Abstract.

Let $r$ be any positive integer. We prove that for every sufficiently large
$k$ there exists a $k$-chromatic vertex-critical graph $G$ such that
$\chi(G-R)=k$ for every set $R\subseteq E(G)$ with $|R|\leq r$. This partially
solves a problem posed by Erdős in 1985, who asked whether the above statement
holds for $k\geq 4$.

Department of Computer Science, Institute of Theoretical Computer Science, ETH
Zürich, Switzerland<EMAIL_ADDRESS>Research of R.S. funded by SNSF Ambizione grant No. 216071.

##  1\. Introduction

The chromatic number $\chi(G)$ of a graph $G$ is among the oldest and most
fundamental graph parameters, but despite its intensive study by researchers
across the field for more than a century, many fundamental open problems
remain. In many instances, we would like to show that for some number $k$, all
graphs in an infinite class $\mathcal{G}$ of graphs have chromatic number less
than $k$. Often times, the graph class $\mathcal{G}$ at hand will also have
the property that it is closed under taking induced, or even arbitrary,
subgraphs. In this case, a central idea for bounding the chromatic number is
to consider the _minimal_ graphs in $\mathcal{G}$ with chromatic number $k$.
These graphs have the special property that removing any vertex (if
$\mathcal{G}$ is closed under induced subgraphs) or any edge (if $G$ is closed
under subgraphs) reduces the chromatic number from $k$ to $k-1$. This enforces
many constraints on such minimal graphs, for instance sufficiently high
minimum degree and edge-connectivity, among others. Such properties can then
prove useful when showing the non-existence of minimal $k$-chromatic graphs in
$\mathcal{G}$, which in turn establishes that the chromatic number of graphs
in $\mathcal{G}$ is less than $k$.

Because of this and many other applications, the notion of _color-critical
graphs_ has emerged. Given an integer $k$, a graph $G$ is called _$k$
-chromatic vertex-critical_ if $\chi(G)=k$, but $\chi(G-v)=k-1$ for every
$v\in V(G)$. Similarly, it is called _$k$ -chromatic edge-critical_, if
$\chi(G)=k$ but $\chi(G-e)=k$ for every $e\in E(G)$. Note that edge-
criticality implies vertex-criticality if we exclude redundant cases in which
$G$ has isolated vertices.

A considerable amount of effort has been put into understanding how different
the notions of vertex-criticality and edge-criticality can be. Already in
1970, G. Dirac [5] conjectured that for every integer $k\geq 4$, there exists
a $k$-chromatic vertex-critical graph $G$ which at the same time is very much
not edge-critical, in the sense that the deletion of any single edge does
_not_ lower its chromatic number. In the following, let us say that such a
graph _has no critical edges_. Dirac’s problem for a long time remained poorly
understood. It was not before 1992 that Brown [1] finally found a first
construction of some vertex-critical graph with no critical edges, in fact, he
found such a construction for $k=5$. Later, in 2002, Lattanzio [5] found a
more general construction which proved Dirac’s conjecture for every integer
$k\geq 5$ such that $k-1$ is not a prime number. Shortly after, Jensen [6]
provided a construction of $k$-chromatic vertex-critical graphs with no
critical edges for every $k\geq 5$. This leaves only the case $k=4$ of Dirac’s
conjecture open today, which remains an intriguing open problem. A wide-
ranging strengthening of Dirac’s conjecture was proposed by Erdős in 1985 [4],
as follows.

I recently heard from Toft the following conjecture of Dirac: Is it true that
for every $k\geq 4$ there is a $k$-chromatic vertex-critical graph which
remains $k$-chromatic if any of its edges is omitted. If the answer as
expected is yes, then one could ask whether it is true that for every $k\geq
4$ and $r$ there is a vertex-critical $k$-chromatic graph which remains
$k$-chromatic if any $r$ of its edges are omitted.

(Paul Erdős, 1985, top of page 113 in [4])

This problem is also mentioned in several other sources, for instance it is
listed as Problem 5.14 in the book [8] by Jensen and Toft and on page 66 in
Chapter 4 of the Erdős open problem collection by Chung and Graham [2], see
also the online version of the problem [3].

The question of Erdős can be rephrased as asking whether for arbitrarily large
numbers $r$ there exist $k$-chromatic vertex-critical graphs for $k\geq 4$
that are “pretty far” from any of their $(k-1)$-chromatic spanning subgraphs,
in the sense that one has to remove more than $r$ edges to reach any such
subgraph. As described above, the case $r=1$ of this problem is well-
understood, however, not much seems to be known beyond that, when $r\geq 2$.

### Our contribution.

In this paper, we resolve the problem by Erdős for any value $r$ and all
sufficiently large values $k$. To the best of our knowledge, these are the
first known examples of such graphs for arbitrarily large values of $r$.

######  Theorem 1.

For every $r\in\mathbb{N}$ there is some $k_{0}\in\mathbb{N}$ such that for
every $k\geq k_{0}$ there exists a $k$-chromatic vertex-critical graph $G$
such that $\chi(G-R)=k$ for every $R\subseteq E(G)$ with $|R|\leq r$.

Our result still leaves open Erdős’ question when $k\geq 4$ is fixed as a
small value and $r$ tends to infinity, and this remains an interesting open
case of the problem. The rest of this note is devoted to presenting our proof
of Theorem 1. The main idea of the construction is to use the existence of
uniform hypergraphs that admit a perfect matching upon the removal of any
single vertex, but at the same time are locally rather sparse. Such
hypergraphs in turn can be constructed randomly, using the recent advances on
Shamir’s hypergraph matching problem.

### Notation.

For a graph $G$ and a subset $X\subseteq V(G)$ of its vertices, $G[X]$ denotes
the subgraph of $G$ induced by $X$. A _hypergraph_ is a tuple $(V,E)$ where
$V$ is a finite set and $E\subseteq 2^{V}\setminus\\{\emptyset\\}$. Given a
hypergraph $H=(V,E)$, we denote by $V(H)=V$ its vertex- and by $E(H)=E$ its
hyperedge-set. For $v\in V(H)$, we denote by $H-v$ the hypergraph with vertex-
set $V(H)\setminus\\{v\\}$ and hyperedge-set $\\{e\in E(H)|v\notin e\\}$. For
$e\in E(H)$, $H-e:=(V(H),E(H)\setminus\\{e\\})$ is the hypergraph obtained by
omitting $e$. Given a hypergraph $H$, its _$2$ -section_ is the graph
$G_{2}^{H}$ on the same vertex-set $V$ and where $uv\in E(G_{2}^{H})$ if and
only if there is some $e\in E(H)$ with $u,v\in e$.

##  2\. Proof of Theorem 1

In the following, given positive integers $n,k$ and a probability value
$p\in[0,1]$, we denote by $\mathcal{H}_{s}(n,p)$ the binomial $s$-uniform
random hypergraph on vertex-set $V=[n]=\\{1,\ldots,n\\}$, obtained by
including every $s$-subset of $V$ as a hyperedge independently with
probability $p$. Given a hypergraph $H$, a _perfect matching_ of $H$ is a
collection $\\{e_{1},\ldots,e_{t}\\}\subseteq E(H)$ of hyperedges that form a
set-partition of $V(H)$. Note that if $H$ is an $s$-uniform hypergraph, then
the existence of a perfect matching necessitates $|V(H)|\equiv 0\text{
}(\text{mod }s)$. One of the most famous problems in probabilistic graph
theory for a long time was _Shamir’s problem_ , that asked to determine the
threshold for the random hypergraph $\mathcal{H}_{s}(n,p)$ with $n\equiv
0\text{ }(\text{mod }s)$ to contain a perfect matching. This threshold was
determined up to a multiplicative error in a breakthrough-result by Johannson,
Kahn and Vu [9] in 2008, as follows.

######  Theorem 2 (cf. [9]).

For every integer $s\geq 1$ there exists a constant $C=C(s)>0$ such that with
$p=p(n)=\frac{C\log n}{n^{s-1}}$ it holds that $\mathcal{H}_{s}(n,p)$ has a
perfect matching w.h.p. provided that $n\equiv 0\text{ }(\text{mod }s)$.

We remark that recently, Kahn [10] has determined the threshold in Shamir’s
problem even more precisely, showing that taking $C=(1+o(1))(s-1)!$ is
sufficient (and best-possible). We now use this probabilistic result to deduce
the existence of uniform hypergraphs with special properties, as follows.

######  Lemma 3.

Let $s\geq 2,m\geq 1$ be fixed integers. Then for every sufficiently large
integer $n$ such that $n\equiv 1\text{ }(\text{mod }s)$, there exists an
$s$-uniform hypergraph $H$ on $n$ vertices with the following properties.

  1. (i)

For every $v\in V(H)$, the hypergraph $H-v$ admits a perfect matching.

  2. (ii)

For every set $F\subseteq E(H)$ of hyperedges with $|F|\leq m$, we have

$\left|\bigcup_{e\in F}{e}\right|\geq(s-1)|F|.$

###### Proof.

Let $p(n):=\frac{C\log n}{n^{s-1}}$ be as in the statement of Theorem 2. Then,
for every $n\equiv 1\text{ }(\text{mod }s)$ chosen large enough, by Theorem 2
we have

$\mathbb{P}(\mathcal{H}_{s}(n-1,p(n-1))\text{ has a perfect
matching})\geq\frac{1}{2}.$

Now, define $q(n):=\lceil 2\log_{2}(n)\rceil
p(n-1)=\Theta\left(\frac{\log^{2}n}{n^{s-1}}\right)$. In the following, we
show that $\mathcal{H}_{s}(n,q(n))$ satisfies both (i) and (ii) w.h.p.
provided $n\equiv 1\text{ }(\text{mod }s)$, which will then imply the
statement of the lemma.

Imagine sampling a random $s$-uniform hypergraph $\tilde{H}$ on vertex-set
$[n]$ as the union of $l:=\lceil 2\log_{2}(n)\rceil$ independently generated
instances of $\mathcal{H}_{s}(n,p(n-1))$, which we call $H_{1},\ldots,H_{l}$.
Note that the distribution of the random hypergraph
$\tilde{H}=H_{1}\cup\dots\cup H_{l}$ follows that of a binomial random
hypergraph $\mathcal{H}_{s}(n,q^{\prime}(n))$ with edge-probability
$q^{\prime}(n)=1-(1-p(n-1))^{l}=1-(1-p(n-1))^{\lceil 2\log_{2}(n)\rceil}\leq
q(n)$. Now fix a vertex $v\in[n]$. From the above we have, since the property
of having a perfect matching is monotone,

$\displaystyle\mathbb{P}(\mathcal{H}_{s}(n,q(n))-v\text{ has no perfect
matching})$ $\displaystyle\leq\>$
$\displaystyle\mathbb{P}(\mathcal{H}_{s}(n,q^{\prime}(n))-v\text{ has no
perfect matching})$ $\displaystyle=\>$
$\displaystyle\mathbb{P}(\tilde{H}-v\text{ has no perfect matching})$
$\displaystyle\leq\>$ $\displaystyle\prod_{i=1}^{l}{\mathbb{P}(H_{i}-v\text{
has no perfect matching})}.$

Since for every $i$ the distribution of $H_{i}-v$ follows that of an
$\mathcal{H}_{s}(n-1,p(n-1))$, from the above we have that
$\mathbb{P}(H_{i}-v\text{ has no perfect matching})\leq\frac{1}{2}$ for
$i=1,\ldots,l$. Altogether, it follows that

$\mathbb{P}(\mathcal{H}_{s}(n,q(n))-v\text{ has no perfect
matching})\leq\left(\frac{1}{2}\right)^{2\log_{2}(n)}=\frac{1}{n^{2}}.$

Using a union bound over all choices of $v$, this implies that

$\mathbb{P}\left(\bigcup_{v\in[n]}\\{\mathcal{H}_{s}(n,q(n))-v\text{ has no
perfect matching}\\}\right)\leq\frac{n}{n^{2}}=\frac{1}{n}.$

Thus, w.h.p. $\mathcal{H}_{s}(n,q(n))$ satisfies property (i).

Let us now move on to property (ii). For that purpose, we want to show that
w.h.p. for every number $f=1,\ldots,m$, no subset of $[n]$ of size $(s-1)f-1$
contains $f$ hyperedges from $\mathcal{H}_{s}(n,q(n))$. Let $T(s,f)$ denote
the number of labelled hypergraphs on $(s-1)f-1$ vertices containing $f$
hyperedges. Using a simple union bound over all choices of subsets of $[n]$ of
size $(s-1)f-1$ and the possible configurations of edges on those subsets, we
obtain that the probability that there exist $f$ hyperedges in
$\mathcal{H}_{s}(n,q(n))$ spanning less than $(s-1)f$ vertices is at most

$\binom{n}{(s-1)f-1}\cdot T(s,f)\cdot
q(n)^{f}=O\left(n^{(s-1)f-1}\cdot\left(\frac{\log^{2}n}{n^{s-1}}\right)^{f}\right)=O\left(\frac{\log^{2f}n}{n}\right).$

Thus, w.h.p. we have that $\mathcal{H}_{s}(n,q(n))$ also satisfies item (ii)
of the lemma. This concludes the proof. ∎

Next, would like to use the hypergraphs from the previous lemma to construct
graphs that satisfy the conditions of Theorem 1. To do so, we first need to
prove a technical result about the number of edges that can be spanned by any
$(s+1)$-subset of vertices in the $2$-section of these hypergraphs, namely
Lemma 5. To prove Lemma 5, we first establish an auxiliary result on
hypergraphs in the form of Lemma 4, which in turn needs the following
elementary but important observation.

######  Observation 1.

Let $H=(V,E)$ be a connected hypergraph (that is, $G_{2}^{H}$ is connected).
Then

$|V|\leq 1+\sum_{e\in E}{(|e|-1)}.$

###### Proof.

Let $T$ be a spanning tree of $G_{2}^{H}$. For every edge $t\in E(T)$, assign
a hyperedge $e(t)\in E$ such that $t\subseteq e(t)$. For each $e\in E$, let
$T_{e}\subseteq T$ be the forest induced by the edges $\\{t\in
E(T)|e(t)=e\\}$. Clearly, $V(T_{e})\subseteq e$ for every $e\in E$, and thus

$|V|-1=|E(T)|=\sum_{e\in E}{|E(T_{e})|}\leq\sum_{e\in
E}{\max\\{0,|V(T_{e})|-1\\}}\leq\sum_{e\in E}{(|e|-1)},$

as desired. ∎

######  Lemma 4.

Let $H=(V,E)$ be a hypergraph with $|V|\geq 4$ and $V\notin E$. Suppose
further that for every set $F\subseteq E$ of hyperedges, we have

$\left|\bigcup_{e\in F}{e}\right|\geq\sum_{e\in F}{(|e|-1)}.$

Then there exists a set $W\subseteq V$ of size at most $2$ such that
$G_{2}^{H}-W$ is disconnected.

###### Proof.

Suppose first that there exists at least one hyperedge $e_{0}\in E$ with
$|e_{0}|\geq 3$. By assumption, $V\notin E$, and thus there exists some vertex
$v\in V\setminus e_{0}$. Let us now consider the graph $G=G_{2}^{H-e_{0}}$,
the $2$-section of the hypergraph $H-e_{0}$ obtained from $H$ by deleting
$e_{0}$. Let $C$ be the vertex-set of the unique connected component of $G$
that contains $v$. We claim that $|C\cap e_{0}|\leq 2$. To that end, define
$F$ as the set of hyperedges of $H$ that are contained in $C$. Clearly,
$e_{0}\notin F$, since $v\in C$ and $v\notin e_{0}$. Note that, since every
hyperedge $e\in E\setminus\\{e_{0}\\}$ induces a clique in $G$, we have that
$\bigcup_{e\in F}{e}=C$ and that the hypergraph $H^{\prime}=(C,F)$ is
connected. These facts imply via Observation 1 that

$\left|\bigcup_{e\in F}{e}\right|=|C|\leq 1+\sum_{e\in F}{(|e|-1)}.$

On the other hand, by applying the assumption of the lemma to the edge-set
$F\cup\\{e_{0}\\}$, we find

$\sum_{e\in F\cup\\{e_{0}\\}}{(|e|-1)}\leq\left|e_{0}\cup\bigcup_{e\in
F}{e}\right|=|e_{0}\cup C|=|e_{0}|+|C|-|e_{0}\cap C|.$

Subtracting $(|e_{0}|-1)$ from both sides yields

$\sum_{e\in F}{(|e|-1)}\leq|C|+1-|e_{0}\cap C|.$

Plugging the above into the first inequality we get $|C|\leq|C|+2-|e_{0}\cap
C|,$ and thus $|e_{0}\cap C|\leq 2$, as claimed. We now set $W:=e_{0}\cap C$
and claim that $G_{2}^{H}-W$ is disconnected. Indeed, it follows readily from
the definition of $C$ that no edge in $G_{2}^{H}-W$ connects a vertex in
$C\setminus W=C\setminus e_{0}$ to a vertex in $V\setminus C$. Further, since
$v\in C\setminus e_{0}$ we have that the first set is non-empty, and since
$|V\setminus C|\geq|e_{0}\setminus C|=|e_{0}|-|e_{0}\cap C|\geq 3-2=1>0$, the
second set is also non-empty. Thus, $G_{2}^{H}-W$ is indeed disconnected,
which concludes the proof in this case.

For the second case, assume that $|e|\leq 2$ for every $e\in E$. W.l.o.g.
(since they do not have an effect on $G_{2}^{H}$) we may assume that $H$
contains no hyperedges of size $1$, i.e., $H$ is a graph and $G_{2}^{H}=H$. If
$H$ has a vertex of degree at most $1$, then the statement of the lemma
trivially holds, so suppose that $H$ has minimum degree at least $2$. The
condition of the lemma now yields $|E|=\sum_{e\in
E}{(|e|-1)}\leq|\bigcup_{e\in E}{e}|\leq|V|$. This directly implies via the
handshake-lemma that $H$ is a $2$-regular graph. It is trivial to see that
every such graph on at least $4$ vertices contains a cut-set $W$ consisting of
at most $2$ vertices, and this concludes the proof. ∎

######  Lemma 5.

Let $s\geq 3$ be an integer, let $H$ be an $s$-uniform hypergraph such that
$\left|\bigcup_{e\in F}{e}\right|\geq(s-1)|F|$ holds for all $F\subseteq E(H)$
with $|F|<2^{s+1}$. Let $G$ be the $2$-section of $H$. Then, for every set
$X\subseteq V(G)$ of size $s+1$, it holds that $|E(G[X])|\leq\binom{s}{2}+2$.

###### Proof.

Let $H_{X}$ denote the hypergraph obtained by _restricting_ $H$ to $X$, that
is, $V(H_{X}):=X$ and $E(H_{X})=\\{e\cap X|e\in E(H),|e\cap X|\geq 2\\}$. Note
that the $2$-section of $H_{X}$ equals $G[X]$. Further note that for every
subset $F\subseteq E(H)$ of size less than $2^{s+1}$, it holds that

$\left|\bigcup_{e\in F}{(e\cap X)}\right|\geq\left|\bigcup_{e\in
F}{e}\right|-\sum_{e\in F}{|e\setminus X|}$ $\geq(s-1)|F|-\sum_{e\in
F}{|e\setminus X|}=\sum_{e\in F}{(s-1-|e\setminus X|)}=\sum_{e\in F}{(|e\cap
X|-1)}.$

This directly implies that $\left|\bigcup_{e\in F}{e}\right|\geq\sum_{e\in
F}{(|e|-1)}$ for every subset $F\subseteq E(H_{X})$. We can therefore apply
Lemma 4, which implies that there exists a set $W\subseteq X$ of size at most
$2$ such that $G[X]-W$ is disconnected. Thus, there exist disjoint non-empty
sets $A,B$ such that $A\cup B=X\setminus W$ and no edge in $G[X]$ connects $A$
and $B$. Note that as $|A|,|B|\geq 1$ and $|A|+|B|=|X|-|W|\geq(s+1)-2=s-1$, we
have $|A||B|\geq s-2$. We conclude that

$|E(G[X])|\leq\binom{s+1}{2}-|A||B|\leq\binom{s+1}{2}-(s-2)=\binom{s}{2}+2.$

This concludes the proof. ∎

###### Proof of Theorem 1.

Let an integer $r\geq 1$ be given. Define $s:=r+3$ and $m:=2^{s+1}$. By Lemma
3 there exists some $n_{0}\in\mathbb{N}$ such that for every integer $n\geq
n_{0}$ with $n\equiv 1\text{ }(\text{mod }s)$, there exists an $s$-uniform
hypergraph $H$ on $n$ vertices with the following properties.

  * •

For every $v\in V(H)$, the hypergraph $H-v$ admits a perfect matching.

  * •

For every set $F\subseteq E(H)$ of hyperedges with $|F|\leq m=2^{s+1}$, we
have

$\left|\bigcup_{e\in F}{e}\right|\geq(s-1)|F|.$

Define $k_{0}:=\lceil\frac{n_{0}-1}{s}\rceil+1$ and let $k\geq k_{0}$ be any
given integer. Let $H$ be an $s$-uniform hypergraph on $n:=s(k-1)+1\geq n_{0}$
vertices satisfying the properties above. Finally, we define a graph $G$ as
the complement of the $2$-section $G_{2}^{H}$ of $H$. We claim that it
satisfies the properties required by the theorem, that is,

  * •

$G-v$ is $(k-1)$-colorable for every $v\in V(G)$, and

  * •

for every set $R\subseteq E(G)$ of edges with $|R|\leq r$, we have
$\chi(G-R)\geq k$.

To verify the first statement, consider any vertex $v$ and a perfect matching
of $H-v$. Since $H$ is $s$-uniform, the perfect matching forms a partition of
$V(H)\setminus\\{v\\}=V(G)\setminus\\{v\\}$ into $\frac{n-1}{s}=k-1$ sets,
each inducing a hyperedge in $H$ and thus an independent set in $G$. Hence we
have $\chi(G-v)\leq k-1$.

Now let $R\subseteq E(G)$ with $|R|\leq r$ be given. We claim that
$\alpha(G-R)\leq s$, i.e., that there exists no independent set in $G-R$ of
size $s+1$, which will then imply
$\chi(G-R)\geq\frac{n}{\alpha(G-R)}\geq\frac{n}{s}>k-1$, as desired. Suppose
towards a contradiction that there is some $X\subseteq V(G)$ of size $s+1$
that is independent in $G-R$. Then $G[X]$ contains at most $r$ edges, and thus
its complement graph, namely $G_{2}^{H}[X]$, contains at least
$\binom{s+1}{2}-r=\binom{s}{2}+s-r=\binom{s}{2}+3$ edges. However, by Lemma 5
applied to $H$, we find that $|E(G_{2}^{H}[X])|\leq\binom{s}{2}+2$, a
contradiction. This shows that indeed, $\alpha(G-R)\leq s$ for every
$R\subseteq E(G)$ with $|R|\leq r$, concluding the proof. ∎

## References

  * [1] J. I. Brown. A vertex critical graph without critical edges. _Discrete Mathematics_ , 102(1), 99–101 (1992).
  * [2] F. Chung and R. Graham. Erdős on graphs: His legacy of unsolved problems. CRC Press (1998).
  * [3] F. Chung. Vertex-critical graphs with many extra edges. _Online-database for Erdős’ problems on graphs_ , https://mathweb.ucsd.edu/~erdosproblems/erdos/newproblems/NoncriticalEdges.html.
  * [4] P. Erdős. On some aspects of my work with Gabriel Dirac. In Graph Theory in Memory of G. A. Dirac, Sandbjerg, 1985, _Annals of Discrete Mathematics_ , 41, 111-116, North-Holland, Amsterdam-New York, 1989. https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.105.1732&rep=rep1&type=pdf
  * [5] J. J. Lattanzio. A note on a conjecture of Dirac. _Discrete Mathematics_ , 258 (1–3), 323–330 (2002).
  * [6] T. R. Jensen. Dense critical and vertex-critical graphs. _Discrete Mathematics_ , 258, 63–84 (2002).
  * [7] T. R. Jensen. Structure of critical graphs. _PhD thesis_ , Odense University, Denmark (1996).
  * [8] T. R. Jensen and B. Toft. Graph coloring problems. John Wiley and Sons, Wiley-Interscience Series in Discrete Mathematics and Optimization, R. L. Graham, J. K. Lenstra, R. E. Tarjan (eds.) (1995).
  * [9] A. Johansson, J. Kahn, V. Vu. Factors in random graphs. _Random Structures & Algorithms_, 33(1), 1–28 (2008).
  * [10] J. Kahn. Asymptotics for Shamir’s problem. _Advances in Mathematics_ , 422, 109019 (2023).
  * [11] J. Wang. Infinite family from each vertex $k$-critical graph without any critical edge. In: _Du, DZ., Hu, X., Pardalos, P.M. (eds.), Combinatorial Optimization and Applications. COCOA 2009_ , Lecture Notes in Computer Science, 5573, 238–248 (2009).