On density of $\mathbb{Z}_{3}$-flow-critical graphs

Critical graphs play an important role in graph coloring theory: A graph $G$ is $c$-critical if $\chi(G)=c$, but every proper subgraph of $G$ is $(c-1)$-colorable. Hence, a graph is $k$-colorable if and only if it does not contain a $(k+1)$-critical subgraph. In particular, interesting results regarding the chromatic number of graphs on surfaces can be obtained by combining lower bounds on the density of critical graphs with the upper bounds on the density of graphs of given genus arising from the generalized Euler’s formula.

As an example, Gallai [8] proved that for $c\geq 3$, every $c$-critical graph different from $K_{c}$ has average degree at least $c-1+\frac{c-3}{c^{2}-3}$, and in particular, any $4$-critical graph other than $K_{4}$ has average degree at least $3+\frac{1}{13}$. On the other hand, a graph of girth at least six with $n$ vertices drawn on a surface $\Sigma$ of Euler genus $\gamma$ has average degree at most $3+3(\gamma-2)/n$. Hence, if such a graph is $4$-critical, it has at most $39(\gamma-2)$ vertices; and consequently, the 3-colorability of graphs of girth at least six drawn on $\Sigma$ is characterized by a finite number of forbidden subgraphs. Analogously, the same is true for 4-colorability of triangle-free graphs and for 6-colorability.

Let us remark that Gallai’s bound was subsequently improved in [16, 13], and finally an asymptotically tight bound was given by Kostochka and Yancey [15]: Any $c$-critical graph with $n$ vertices has average degree at least $\frac{(c+1)(c-2)}{c-1}-O(1/n)$.

Tutte [25] famously observed that coloring is dual to nowhere-zero flows. To state the result, we need several definitions, which we present in a slightly more general setting that will be useful later. We allow graphs to have parallel edges, but no loops. Let $\Gamma$ be an abelian group¹¹1We will implicitly assume that $\Gamma$ is nontrivial, i.e. that it contains at least 2 elements although most of the results hold also for the one-element group.. A $\Gamma$-boundary for a graph $G$ is a function $\beta:V(G)\to\Gamma$ such that $\sum_{v\in V(C)}\beta(v)=0$ for every component $C$ of $G$. If $\beta$ is a $\Gamma$-boundary for $G$, we say that the pair $\mathbb{G}=(G,\beta)$ is a $\Gamma$-bordered graph (or a graph with boundary). A symmetric orientation $\overleftrightarrow{G}$ of $G$ is the directed graph obtained by replacing every edge $e=uv$ of $G$ by a pair of oppositely directed edges $e_{u}$ (directed towards $u$) and $e_{v}$ (directed towards $v$). A function $f:E(\overleftrightarrow{G})\to\Gamma$ is antisymmetric if for every $e=uv\in E(G)$, $f(e_{u})=-f(e_{v})$. A flow in $(G,\beta)$ is an antisymmetric function $f:E(\overleftrightarrow{G})\to\Gamma$ such that for every $u\in V(G)$,

The flow is nowhere-zero if it does not use the value $0$. By a $\Gamma$-flow in a graph $G$, we mean a flow in $(G,0)$, where $0$ is the $\Gamma$-boundary assigning to each vertex the value $0$.

Note that only the size of the group matters, and indeed, Tutte proved that if $\Gamma$ and $\Gamma^{\prime}$ are abelian groups of the same order, then the number of nowhere-zero $\Gamma$-flows is equal to the number of nowhere-zero $\Gamma^{\prime}$-flows in any graph. Tutte also stated a number of influential conjectures on the existence of nowhere-zero flows, generalizing the Five Color Theorem, the Four Color Theorem, and Grötzsch theorem, respectively.

While these conjectures are still open, Seymour [24] proved existence of nowhere-zero $\mathbb{Z}_{k}$-flows for every $k\geq 6$, Robertson, Seymour, and Thomas [22] claimed the proof of existence of nowhere-zero $\mathbb{Z}_{4}$-flows in subcubic graphs with no Petersen minor (with one of the basic cases later appearing in [6] and another one still unpublished [23]), and Lovász et al. [19] proved existence of nowhere-zero $\mathbb{Z}_{3}$-flows in 6-edge-connected graphs.

Given the importance of critical graphs for coloring, it is natural to consider the dual concept of flow-critical graphs, with the definition based on the observation that edge removal in a plane graph corresponds to contraction of the corresponding edge in the dual graph.

For a partition ${\mathcal{P}}$ of the vertex set of a graph $G$, let $G/{\mathcal{P}}$ be the graph obtained by identifying the vertices in each part of ${\mathcal{P}}$ to a single vertex and then removing all resulting loops. If $\beta$ is a $\Gamma$-boundary for $G$, then let $\beta/{\mathcal{P}}$ be the $\Gamma$-boundary for $G/{\mathcal{P}}$ obtained by setting $(\beta/{\mathcal{P}})(p)=\sum_{v\in P}\beta(v)$ for each $P\in{\mathcal{P}}$ identified to the vertex $p$. For a $\Gamma$-bordered graph $\mathbb{G}=(G,\beta)$, we define $\mathbb{G}/{\mathcal{P}}=(G/{\mathcal{P}},\beta/{\mathcal{P}})$. For a set $B\subseteq V(G)$, we define $G/B$ and $\mathbb{G}/B$ as $G/{\mathcal{P}}_{B}$ and $\mathbb{G}/{\mathcal{P}}_{B}$ for the partition ${\mathcal{P}}_{B}$ consisting of $B$ and single-vertex sets $\{v\}$ for $v\in V(G)\setminus B$. If each part of ${\mathcal{P}}$ induces a connected subgraph of $G$, we say that ${\mathcal{P}}$ is $G$-connected, and that $G/{\mathcal{P}}$ (or $\mathbb{G}/{\mathcal{P}}$) is a contraction of $G$ (or $\mathbb{G}$). The partition ${\mathcal{P}}$ is non-trivial if at least one part contains more than one vertex, and in this case we call the contraction proper. We say a $\Gamma$-bordered graph $\mathbb{G}$ is flow-critical if $\mathbb{G}$ is connected and $\mathbb{G}$ has no nowhere-zero flow, but every proper contraction of $\mathbb{G}$ has a nowhere-zero flow. We say that a graph $G$ is $\Gamma$-flow-critical if the $\Gamma$-bordered graph $(G,0)$ is flow-critical. Clearly, a graph $H$ has a nowhere-zero $\Gamma$-flow if and only if no component of $H$ has a $\Gamma$-flow-critical contraction.

Given the results outlined above, $K_{2}$ is the only $\Gamma$-flow-critical graph when $|\Gamma|\geq 6$, and Tutte’s 5-flow conjecture is equivalent to the claim that there are no $\mathbb{Z}_{5}$-flow-critical graphs other than $K_{2}$. Hence, the notion of $\Gamma$-flow-criticality is interesting only for $\Gamma\in\{\mathbb{Z}_{3},\mathbb{Z}_{4},\mathbb{Z}_{2}^{2}\}$ (and possibly $\Gamma=\mathbb{Z}_{5}$). The study of flow-critical graphs was started by Nunes da Silva and Lucchesi [3], who showed some of their basic properties. Recently, Li et al. [18] considered the extremal question of the density of $\mathbb{Z}_{3}$-flow-critical graphs, which is also the subject of this paper.

As observed by Li et al. [18], dualizing the results of Kostochka and Yancey [15] shows that if $G$ is a planar $\mathbb{Z}_{3}$-flow-critical graph, then $|E(G)|\leq\frac{5|V(G)|-8}{2}$. Li et al. [18] also demonstrated that this upper bound cannot be extended to non-planar graphs: For $n\geq 7$, the graph $K_{3,n-3}^{+}$ obtained from the complete bipartite graph $K_{3,n-3}$ by adding an edge joining two of the vertices of degree $n-3$ is $\mathbb{Z}_{3}$-flow-critical, and it has $3n-8$ edges. They conjectured that this bound is best possible.

Let us remark that Li et al. [18] only state the version of the conjecture for graphs with at least seven vertices, but the version without this restriction follows by a straightforward inspection of graphs with at most $6$ vertices. Li et al. [18] proved a weakening of this conjecture.

The Euler genus of the surface obtained from the plane by adding $h$ handles and $c$ crosscaps is $2h+c$, and the Euler genus $g(G)$ of a graph $G$ is the minimum Euler genus of surfaces in which $G$ can be drawn without crossings. Note that the graph $K_{3,n-3}^{+}$ is far from being planar; indeed, it has Euler genus $\lceil\tfrac{n-5}{2}\rceil$ (see Ringel [21]). Given that the bound for planar graphs is substantially smaller than the bound for general graphs in Conjecture 1.3, it is natural to ask whether a better bound holds when the genus is bounded. As our main result, we prove that this is indeed the case.

Theorem 1.5 implies Conjecture 1.3 for graphs $G$ whose Euler genus is at most $(|V(G)|-8)/5$, and shows that for any fixed surface $\Sigma$, the conjecture can be verified for graphs drawn in $\Sigma$ by examining a finite number of graphs. Let us remark that there exist infinitely many planar $\mathbb{Z}_{3}$-flow-critical graphs $G$ satisfying $|E(G)|=\frac{5|V(G)|-8}{2}$, and thus the bound in Theorem 1.5 cannot be improved to $c|V(G)|+f(g(G))$ for $c<5/2$ and any function $f$. On the other hand, the dependence on genus is likely not the best possible.

Theorem 1.5 and the example of $K_{3,n-3}^{+}$ show that $1\leq\alpha\leq 5/2$.

Our proof technique is a variation on the potential method argument of Kostochka and Yancey [15], and it naturally leads us to work in a more general setting of graphs with boundary. Hence, we in fact prove the following more general version of Theorem 1.5.

For an abelian group $\Gamma$, a graph $G$ is said to be $\Gamma$-connected if $(G,\beta)$ has a nowhere-zero flow for every $\Gamma$-boundary $\beta$. Many of the results on the existence of nowhere-zero flows are known to be true in the group-connectivity setting as well; for instance, 6-edge-connected graphs are $\mathbb{Z}_{3}$-connected [19]. Moreover, the following group-connectivity analogue to the 3-flow conjecture was proposed.

Let us remark that the 3-flow conjecture can be reduced to 5-edge-connected graphs [11], and thus it is implied by Conjecture 1.8. By Theorem 1.7, every flow-critical $\mathbb{Z}_{3}$-bordered graph of Euler genus at most one has average degree less than five. Since every contraction of a 5-edge-connected graph has minimum degree at least five, it follows that Conjecture 1.8 holds for planar and projective-planar graphs; this was previously proved in [20, 5]. Similarly, Theorem 1.7 implies Conjecture 1.8 for graphs that can be made planar by removal of at most three edges (even in the stronger setting where we can prescribe the flow on the removed edges arbitrarily).

As our second result, we show that Conjecture 1.8 implies the first part of Conjecture 1.3.

The rest of the paper is organized as follows. In Section 2, we present basic auxiliary results. In Section 3, we prove a strengthening of Theorem 1.7, which includes the characterization of the graphs for which the bound is tight. In Section 4, we prove Theorem 1.9.

Let us now proceed with the proof of Theorem 1.7, which we now reformulate and strengthen. For a graph $G$, let us define

Note that if $G$ is exceptional, then $\pi(G)=8$. We say that $G$ is sparse if $G$ is exceptional or $\pi(G)\geq 9$.

The rest of this section is devoted to the proof of Theorem 3.1. A $\mathbb{Z}_{3}$-bordered graph is a minimal counterexample if it is flow-critical, not sparse, and every $\mathbb{Z}_{3}$-bordered flow-critical graph with smaller number of vertices is sparse. We will prove Theorem 3.1 by showing that there are no minimal counterexamples. Note that by Observation 2.1, if $(G,\beta)$ is a minimal counterexample, then $G$ is a $2$-connected simple graph. Corollary 2.7 can be restated as follows.

Moreover, small graphs are not counterexamples.

For a $G$-connected partition ${\mathcal{P}}$ of the vertex set of a graph $G$, let $k(G,{\mathcal{P}})$ be the number of parts of ${\mathcal{P}}$ inducing an exceptional subgraph of $G$, let $n(G,{\mathcal{P}})$ be the number of parts of size greater than one that do not induce an exceptional subgraph, and let

In case the graph $G$ is clear from the context, we use $k({\mathcal{P}})$, $n({\mathcal{P}})$, and $w({\mathcal{P}})$ for brevity. Let us now state the crucial lemma forming the basis for the application of the potential method.