Minimum degree and immersions of complete graphs

In this thesis, all graphs are finite and may have loops and multiple edges. Let uw and wv be two distinct adjacent edges in a graph G. To lift the edges uw and wv, is to delete them from G and add a new edge uv. A graph G is said to contain an H-immersion, if a graph isomorphic to H can be obtained from a subgraph of G by lifting pairs of edges (and possibly removing isolated vertices). 

The classical conjecture of Hadwiger relates the clique minor containment in a graph G and the chromatic number χ(G) of G. Hadwiger's conjecture states that every loopless graph without a Kt-minor is (t-1)-colourable, suggesting a far-reaching generalization of the Four-Colour Theorem. It remains one of the deepest open problems in Graph Theory. Consequently, relations between the chromatic number of a graph G and the largest size of a complete graph contained in G attracted a lot of interest. Regarding immersion, the conjecture of Abu-Khzam and Langston states that the graph Kt can be immersed in any t-chromatic graph. 

A variant of this regards the minimum degree of a graph instead of the chromatic number as follows: Let d(t) be the smallest integer such that every simple graph of minimum degree at least d(t) contains an immersion of Kt, then d(t) = t - 1. In this thesis, we analyse the proof for the values t ∈ {5, 6, 7} (as proven by DeVos, Kawarabayashi, Mohar and Okamura). Furthermore, we study the reason the conjecture does not hold for t ∈ {8, 9, 11} along with a counterexample of Seymour for t = 10 resulting that d(t) ≥ t for t ≥ 10. Finally, two upper bounds are presented, one of the function d(t) regarding weak immersions showing that d(t) ≤ 200t and another one for strong immersions indicating that d(t) ≤ 7t+7.