A short proof of Brooks’ Theorem for vertex arboricity

Abstract

The vertex-arboricity $a\left(G\right)$ of a graph $G$ is the minimum number of subsets that the vertices of $G$ can be partitioned so that the subgraph induced by each set of vertices is a forest. Kronk and Mitchem proved a generalization of Brooks’ Theorem for vertex arboricity, $a\left(G\right)=1+\frac{1}{2}△\left(G\right)$ if and only if $G$ is a cycle or a complete graph of odd order. We provide a short proof of this result using degeneracy.

Keywords:

• Brooks’ Theorem
• Vertex arboricity
• Degeneracy
• Vertex coloring

Brooks’ Theorem is one of the most famous bounds for the chromatic number $\chi \left(G\right)$. There are many proofs of this theorem, and many extensions of it. Proofs of Brooks’ Theorem and extensions for chromatic number are surveyed by Cranston and Rabern [1]. There are also analogous versions of Brooks’ Theorem for other forms of vertex coloring. This paper provides a short proof of Brooks’ Theorem for vertex arboricity. This proof uses the concept of degeneracy.

Definition 1

A deletion sequence of a graph $G$ is a sequence of its vertices formed by iterating the operation of deleting a vertex of smallest degree and adding it to the sequence until no vertices remain. A construction sequence of a graph is the reversal of a corresponding deletion sequence. A graph is $k$-degenerate if its vertices can be successively deleted so that when deleted, each has degree at most $k$. The degeneracy $D\left(G\right)$ of a graph $G$ is the smallest $k$ such that it is $k$-degenerate.

It is immediate from the definition of degeneracy that it is bounded by the minimum and maximum degrees, $\delta \left(G\right)\le D\left(G\right)\le \Delta \left(G\right)$. There is a simple characterization of the extremal graphs for the upper bound, which is proved in [2]. For simplicity, the statement is restricted to connected graphs.

Proposition 2

Let $G$ be a connected graph. Then $D\left(G\right)=\Delta \left(G\right)$ if and only if $G$ is regular.

Greedily coloring a construction sequence of $G$ justifies the following bound on chromatic number.

Theorem 3

For any graph $G$,$\chi \left(G\right)\le 1+D\left(G\right)$.

To prove Brooks’ Theorem, we use an approach adapted from Lovasz [3]. It begins with a lemma involving the connectivity $\kappa \left(G\right)$.

Lemma 4

Given $r\ge 3$, if $G$ is an$r$-regular 2-connected noncomplete graph, then $G$ has a vertex $v$ with two nonadjacent neighbors $x$ and $y$ such that $G-x-y$ is connected.

Proof

If $G$ is 3-connected, let $v$ be any vertex, and $x$ and $y$ be two nonadjacent neighbors of $v$, which must exist since $G$ is noncomplete.

If $\kappa \left(G\right)=2$, let $\left\{u,v\right\}$ be any 2-vertex-cut of $G$. Then $\kappa \left(G-v\right)=1$, so $G-v$ has at least two end-blocks, and $v$ has neighbors in all of them. Let $x$, $y$ be two such neighbors. They must be nonadjacent, and $G-x-y$ is connected since blocks have no cut-vertices and $r\ge 3$. □

Theorem 5

Brooks’ Theorem [4] If $G$ is connected, then $\chi \left(G\right)=1+△\left(G\right)$ if and only if $G$ is complete or an odd cycle.

Proof

$\left(\Leftarrow \right)$ Equality certainly holds for cliques and odd cycles.

$\left(\Rightarrow \right)$ Let $G$ satisfy the hypotheses. Then by Proposition 2, $G$ is $r$-regular. The result certainly holds for $r\le 2$, so we may assume $r\ge 3$. If $G$ had a cut-vertex, each block could be colored with fewer than $r+1$ colors to agree on that vertex, so we may assume $G$ is 2-connected and to the contrary, not a clique.

By the lemma, we can establish a deletion sequence for $G$ starting with some vertex $v$ and ending with its nonadjacent neighbors $x$ and $y$ so that all vertices but $v$ have at most $r-1$ neighbors when deleted. Reversing this yields a construction sequence, and coloring greedily gives $x$ and $y$ the same color, so $G$ needs at most $r$ colors.□

The chromatic number has color classes that induce empty sets; vertex-arboricity has color classes that induce forests.

Definition 6

The vertex-arboricity $a\left(G\right)$ of a graph $G$ is the minimum number of subsets that the vertices of $G$ can be partitioned so that the subgraph induced by each set of vertices is a forest.

There is an upper bound for vertex-arboricity that is analogous to Theorem 3.

Theorem 7

[5] For any graph $G$,$a\left(G\right)\le 1+⌊\frac{1}{2}D\left(G\right)⌋$.

Proof

Let $k=D\left(G\right)$, and greedily color a construction sequence of $G$ using $1+⌊\frac{1}{2}k⌋$ vertex sets inducing forests (if nonempty). A vertex has at most $k$ neighbors when colored, and it can be added to one of the vertex sets unless it is adjacent to two vertices in each set. But then it is adjacent to at least $2\left(1+⌊\frac{1}{2}k⌋\right)\ge k+1$ colored vertices, a contradiction.□

Theorem 7 implies that $a\left(G\right)\le 1+\frac{1}{2}△\left(G\right)$. There is a version of Brooks’ Theorem for vertex arboricity that characterizes the extremal graphs for this bound. Kronk and Mitchem’s proof [6] is more than three pages, including essential lemmas. Adapting Lovasz’s proof of Brooks’ Theorem yields a significantly shorter proof.

Lemma 8

Given $r\ge 4$, if $G$ is an$r$-regular 2-connected noncomplete graph, then $G$ has a vertex $v$ with three neighbors $x$,$y$, and$z$, not all adjacent, such that $G-x-y-z$ is connected.

Proof

If $G$ is 4-connected, let $x$, $y$, and $z$ be three neighbors of a vertex $v$ with $x$ not adjacent to $z$.

Assume $2\le \kappa \left(G\right)\le 3$. Among all minimum vertex cuts of $G$, let $S$ be one so that $G-S$ has a component $H$ of smallest order. Choose $v\in S$ so that if some component $K$ of $G-H-S$ has $\kappa \left(K\right)=1$, then $v$ has a neighbor in an end-block of $K$. Let $z$ be any neighbor of $v$ in $K$ that is not a cut-vertex of $K$. By the minimality of $S$, each vertex in $S$ has a neighbor in each component of $G-H-S$, so $G-H$ is connected. Since $K-z$ is connected, $G-H-v-z$ is also connected.

Now $v$ cannot have only one neighbor $u$ in $H$, for then $S-\left\{v\right\}\cup \left\{u\right\}$ results in a smaller component. Thus $v$ has at least two neighbors $x$ and $y$ in $H$, and $z$ is not adjacent to $x$ or $y$. Let $F=G\left[V\left(H\right)\cup S\right]$. The minimality of $S$ implies that each component of $F-x-y$ contains a vertex of $S$. If $v$ has a neighbor other than $z$ in $G-H$ or $F-x-y$ is connected, then $G-x-y-z$ is connected.

Suppose that all neighbors of $v$ except $z$ are in $H$ and $F-x-y$ is disconnected. By the minimality of $S$, $F$ has no cut-vertex. Now $v$ has at least three neighbors $w$, $x$, and $y$ in $H$. If each pair of them are a cutset, then each pair would separate some distinct vertex of $S$ from $F$, implying $\left|S\right|\ge 4$, which is impossible. Renaming the pair from $\left\{w,x,y\right\}$ that are not a cutset as $x$ and $y$ completes the proof. □

Theorem 9

Brooks’ Theorem for Vertex Arboricity [6] If $G$ is connected, then $a\left(G\right)=1+\frac{1}{2}△\left(G\right)$ if and only if $G$ is a cycle or a complete graph of odd order.

Proof

$\left(\Leftarrow \right)$ Equality certainly holds for cycles and odd cliques.

$\left(\Rightarrow \right)$ Let $G$ satisfy the hypotheses. Then by Proposition 2, $G$ is $r$-regular. The result certainly holds for $r\le 2$, so we may assume $r$ is even, $r\ge 4$. If $G$ had a cut-vertex, each block could be partitioned into fewer than $1+\frac{r}{2}$ sets inducing forests, and the sets made to agree on that vertex, so we may assume $G$ is 2-connected and to the contrary, not a clique.

By the lemma, we can establish a deletion sequence for $G$ starting with some vertex $v$ and ending with its neighbors $x$, $y$, and $z$, not all adjacent, so that all vertices but $v$ have at most $r-1$ neighbors when deleted. Use the corresponding construction sequence to color greedily using $\frac{r}{2}$ colors, starting with $x$, $y$, and $z$ in the same set. There is a color available for each vertex $u\ne v$ since otherwise $u$ would have at least $2\cdot \frac{r}{2}=r$ colored neighbors. Finally, there is a color available for $v$ since else $v$ has at least $3+2\cdot \left(\frac{r}{2}-1\right)=r+1$ neighbors.□