Gexin Yu

Graph minors and graph linkage

Abstract: Graph minors are very important structures in graphs. Many central results and problems in graph theory are stated in terms of graph minors. For example, a graph is planar if and only if it doesn't contains K5 (the complete graph with five vertices) or K3,3 (the complete bipartite graph with three vertices on each side) as minors. Another example, Hadwiger's Conjecture, states that a k-chromatic graph contains a copy of Kk as a minor. We will talk about graph linkage, a key tool in the study of graph minors. We will also study the connectivity of minimal counterexamples to Hadwiger's Conjecture, with the help of graph linkage.