# Graph Minors, Vertex Colourings and Vertex Arboricity.

A research project of Leif
K. Jørgensen
.
*This is an abstract of a talk I gave at some universities in
Israel
in 1999 and 2000.*

The most famous problem in the theory of graph minors is following conjecture
of Hadwiger (1943): for any natural number *k* , any graph with chromatic
number *k* (i.e., the vertex set cannot be partioned in fewer than *
k* independent sets) has a K_*k* minor (i.e., the vertex set can
be partitioned in *k* connected subgraphs, so that each pair of subgraphs
is connected). This was proved by Hadwiger for *k*<=4, and Wagner
(1937) and Robertson, Seymour and Thomas (1993) proved that for *k*=5
and *k*=6, respectively, it is equivalent to the four colour conjecture/theorem.

A generalization of Hadwiger's conjecture by Ding, Oporowski, Sanders and
Vertigan (200?) also claims that a graph with vertex arboricity *k*-1
(i.e., the vertex set cannot be partitioned in fewer than *k*-1 acuclic
sets) has a K_*k* minor.

We can prove this conjecture for *k*<=8 using the result that the
number of edges in a graph *n* vertices and and no K_*k* minor
is less than (*k*-2)*n*, which was proved by Mader (1968) for *
k*<=7 and by Jørgensen (1994) for *k*=8.

Woodall (1990) conjectured that the above conjectures hold with "K_*
k* minor" replaced by "K_*k* minor or B_(*k*+1) minor", where
B_(*k*+1) is the complete bipartite graph with parts of "almost equal
size".

We investigate this conjecture, for *k*<=7, using that the number
of edges in a 4-connected graph on n vertices with no K_(4,4) minor is at
most 4*n*-8 (Jørgensen 2001). In particular Woodall conjecture
that a graph with no K_7 minor and no K_(4,4) minor has vertex arboricity
at most 5. We can prove that it has vertex arboricity at most 4.

#### Some of my papers on Graph Minors:

Jørgensen 1994: L. K. Jørgensen, Contractions to
K_8, J. Graph Th. 18 (1994) 431-448.
Jørgensen 2001: L. K. Jørgensen, Vertex partitions
of K_4,4 minor free graphs, Graphs and Combinatorics 17 (2001) 265-274.