Originators: Faisal Abu-Khzam and Michael Langston (presented by D. Stolee - REGS 2010)
Definitions: A relation is a well-quasi-order if it is reflexive and transitive and every infinite set of elements contains a minimal element and contains two comparable elements. For natural relations on graphs, every set has at least one minimal element, so the crucial property is that infinite antichains are forbidden.
When H and G are simple graphs, H is a minor of G (denoted H ≤m G) if some sequence of deletions and edge contractions from G produces a graph isomorphic to H; that is, H is isomorphic to a contraction of a subgraph of G. An H-immersion in G consists of a map π: V(H) → V(G) and a map σ that takes each edge uv of H to a path joining π(u) and π(v) in G such that the paths given by σ are edge-disjoint. We write H ≤i G when there is an immersion of H in G.
In the definition of H-immersion, normally we require π to be injective. Alternative models allow π to be any function, or allow images under π to appear internally in paths given by σ, or require π to be order-preserving when V(H) and V(G) are contained in a well-quasi-order. We use only the standard definition.
If the paths under σ are internally disjoint, then we have an H-subdivision in G. Hence, G contains an H-immersion whenever G contains an H-subdivision.
Background: In a series of papers from 1983 to 2007, Robertson and Seymour proved the famous Graph Minor Theorem, which states that the minor order on graphs is well-quasi-ordered. In particular, every minor-closed family (closed under taking minors) is characterized by a finite family of forbidden minors. Robertson and Seymour [RS] also proved the analogous statement for the immersion order; it is well-quasi-ordered. Equivalently, for any infinite set of graphs, there are two where one contains an immersion of the other, and each immersion-closed family of graphs is characterized by a finite family of forbidden immersions.
Hadwiger's Conjecture [H] states that a graph is t-colorable if and only if it does not have the complete graph Kt+1 as a minor. This is known for t≤5 [RST].
Conjecture: (Abu-Khzam and Langston [AL]) A graph is t-colorable if and only if it does not contain an immersion of Kt+1.
Problem: What immersion-closed families correspond to particular forbidden immersions? For example, which are the planar graphs containing no immersion of K5 or K3,3? Which are the outerplanar graphs containing no immersion of K4 or K2,3?
Comments: Kuratowski [K] proved that a graph is planar if and only if it contains no subdivision of K5 or K3,3. Wagner [W] proved that a graph is planar if and only if it does not have K5 or K3,3 as a minor. The family of planar graph is closed under taking minors, but every graph has an immersion in some planar graph: draw the graph in the plane and add vertices at the points where edges cross.
Mader [M] proved that if H has h vertices, then every n-vertex graph not having H as a minor has at most O(nh√(log h)) edges.
References:
[AL] F. N. Abu-Khzam, M. A. Langston, Graph Coloring and the
Immersion Order, Computing and combinatorics,
Lecture Notes in Comput. Sci., 2697 (Springer, Berlin 2003) 394-403.
[H] Hadwiger, H. Über eine Klassifikation der Streckenkomplexe. (German)
Vierteljschr. Naturforsch. Ges. Zürich 88, (1943) 133--142.
[K] Kuratowski, K.; Sur le problème des courbes gauches en
topologie, Fund. Math. 15 (1930) 271--283.
[M] Mader, W.; Homomorphieeigenschaften und mittlere Kantendichte von Graphen.
Math. Ann. 174 (1967) 265--268.
[RS] N. Robertson, P. Seymour; Graph Minors XXIII: Nash-Williams'
immersion conjecture, (2009).
[RST]
Robertson, Neil; Seymour, Paul; Thomas, Robin
Hadwiger's conjecture for K6-free graphs.
Combinatorica 13 (1993), no. 3, 279--361.
[W] Wagner, K.; Über eine Eigenschaft der ebenen Komplexe. Math. Ann. 114
(1937), no. 1, 570--590.