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 4n-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.