Document Type
Lecture
Publication Date
2-27-2003
Abstract
Let s1, s2, , sk be k positive integers. A graph G is said to be (s1 s2 linked if it has at least k i=1 si vertices and for any k disjoint vertex sets S1, S2, sk), Sk with Si = si, then G contains vertex-disjoint connected subgraphs F1, F2, , Fk such that Si V(Fi). The case s1 = s2 = = sk = 2 has been studied extensively. A (22 2)-linked graph is called a k-linked, i.e., for any 2k distinct vertices x1, y1, x2, y2, , xk, and yk there exist k vertexdisjoint paths P1, P2, , Pk such that Pi joins xi and yi, 1 i k. A graph H is a minor of a graph G if H can be obtained from G by deleting edges and/or vertices and contracting edges. An H-minor of G is a minor isomorphic to H. We will introduce some related concepts and study the relationship between the graph minors and linkages. Several interesting results and further research problems will be presented. We will also show the outlines of the proof ideas for some recent results. This is a joint work with Chen, Gould, Kawarabayashi and Pfender.
Relational Format
presentation
Recommended Citation
Wei, Bing, "Graph Minors and Linkages" (2003). Combinatorics Seminar. 116.
https://egrove.olemiss.edu/math_combinatorics/116
