![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
Abstract
The vertex-arboricity of a graph
is the minimum number of subsets that the vertices of
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,
if and only if
is a cycle or a complete graph of odd order. We provide a short proof of this result using degeneracy.
Brooks’ Theorem is one of the most famous bounds for the chromatic number . 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 Citation[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 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
-degenerate if its vertices can be successively deleted so that when deleted, each has degree at most
. The degeneracy
of a graph
is the smallest
such that it is
-degenerate.
It is immediate from the definition of degeneracy that it is bounded by the minimum and maximum degrees, . There is a simple characterization of the extremal graphs for the upper bound, which is proved in Citation[2]. For simplicity, the statement is restricted to connected graphs.
Proposition 2
Let be a connected graph. Then
if and only if
is regular.
Greedily coloring a construction sequence of justifies the following bound on chromatic number.
Theorem 3
For any graph ,
.
To prove Brooks’ Theorem, we use an approach adapted from Lovasz Citation[3]. It begins with a lemma involving the connectivity .
Lemma 4
Given , if
is an
-regular 2-connected noncomplete graph, then
has a vertex
with two nonadjacent neighbors
and
such that
is connected.
Proof
If is 3-connected, let
be any vertex, and
and
be two nonadjacent neighbors of
, which must exist since
is noncomplete.
If , let
be any 2-vertex-cut of
. Then
, so
has at least two end-blocks, and
has neighbors in all of them. Let
,
be two such neighbors. They must be nonadjacent, and
is connected since blocks have no cut-vertices and
. □
Theorem 5
Brooks’ Theorem Citation[4] If is connected, then
if and only if
is complete or an odd cycle.
Proof
Equality certainly holds for cliques and odd cycles.
Let
satisfy the hypotheses. Then by Proposition 2,
is
-regular. The result certainly holds for
, so we may assume
. If
had a cut-vertex, each block could be colored with fewer than
colors to agree on that vertex, so we may assume
is 2-connected and to the contrary, not a clique.
By the lemma, we can establish a deletion sequence for starting with some vertex
and ending with its nonadjacent neighbors
and
so that all vertices but
have at most
neighbors when deleted. Reversing this yields a construction sequence, and coloring greedily gives
and
the same color, so
needs at most
colors.□
The chromatic number has color classes that induce empty sets; vertex-arboricity has color classes that induce forests.
Definition 6
The vertex-arboricity of a graph
is the minimum number of subsets that the vertices of
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
Citation[5] For any graph ,
.
Proof
Let , and greedily color a construction sequence of
using
vertex sets inducing forests (if nonempty). A vertex has at most
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
colored vertices, a contradiction.□
Theorem 7 implies that . There is a version of Brooks’ Theorem for vertex arboricity that characterizes the extremal graphs for this bound. Kronk and Mitchem’s proof Citation[6] is more than three pages, including essential lemmas. Adapting Lovasz’s proof of Brooks’ Theorem yields a significantly shorter proof.
Lemma 8
Given , if
is an
-regular 2-connected noncomplete graph, then
has a vertex
with three neighbors
,
, and
, not all adjacent, such that
is connected.
Proof
If is 4-connected, let
,
, and
be three neighbors of a vertex
with
not adjacent to
.
Assume . Among all minimum vertex cuts of
, let
be one so that
has a component
of smallest order. Choose
so that if some component
of
has
, then
has a neighbor in an end-block of
. Let
be any neighbor of
in
that is not a cut-vertex of
. By the minimality of
, each vertex in
has a neighbor in each component of
, so
is connected. Since
is connected,
is also connected.
Now cannot have only one neighbor
in
, for then
results in a smaller component. Thus
has at least two neighbors
and
in
, and
is not adjacent to
or
. Let
. The minimality of
implies that each component of
contains a vertex of
. If
has a neighbor other than
in
or
is connected, then
is connected.
Suppose that all neighbors of except
are in
and
is disconnected. By the minimality of
,
has no cut-vertex. Now
has at least three neighbors
,
, and
in
. If each pair of them are a cutset, then each pair would separate some distinct vertex of
from
, implying
, which is impossible. Renaming the pair from
that are not a cutset as
and
completes the proof. □
Theorem 9
Brooks’ Theorem for Vertex Arboricity Citation[6] If is connected, then
if and only if
is a cycle or a complete graph of odd order.
Proof
Equality certainly holds for cycles and odd cliques.
Let
satisfy the hypotheses. Then by Proposition 2,
is
-regular. The result certainly holds for
, so we may assume
is even,
. If
had a cut-vertex, each block could be partitioned into fewer than
sets inducing forests, and the sets made to agree on that vertex, so we may assume
is 2-connected and to the contrary, not a clique.
By the lemma, we can establish a deletion sequence for starting with some vertex
and ending with its neighbors
,
, and
, not all adjacent, so that all vertices but
have at most
neighbors when deleted. Use the corresponding construction sequence to color greedily using
colors, starting with
,
, and
in the same set. There is a color available for each vertex
since otherwise
would have at least
colored neighbors. Finally, there is a color available for
since else
has at least
neighbors.□
References
- CranstonD.RabernL., Brooks’ theorem and beyond J. Graph Theory 80 3 2015 199–225
- BickleA., Cores and shells of graphs Math. Bohem. 138 1 2013 43–59
- LovászL., Three short proofs in graph theory J. Combin. Theory Ser. B 191975 269–271
- BrooksR.L., On colouring the nodes of a network, Proc. Cambridge philosophical society Math. Phys. Sci. 371941 194–197
- ChartrandG.KronkH.V.WallC.E., The point arboricity of a graph Isreal J. Math. 61968 169–175
- KronkH.V.MitchemJ., Critical point arboritic graphs J. Lond. Math. Soc. 91974 459–466