Immersions and edge-disjoint linkages

• Thesis title in Czech: Immersions and edge-disjoint linkages
• Thesis title in English: Immersions and edge-disjoint linkages
• Key words: teorie grafů, imerze, stromová šířka
• English key words: graph theory, immersion, tree-width
• Academic year of topic announcement: 2010/2011
• Thesis type: diploma thesis
• Thesis language: angličtina
• Department: Department of Applied Mathematics (32-KAM)
• Supervisor: prof. Mgr. Zdeněk Dvořák, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 01.09.2010
• Date of assignment: 11.03.2011
• Date and time of defence: 15.09.2011 00:00
• Date of electronic submission: 04.08.2011
• Date of submission of printed version: 05.08.2011
• Date of proceeded defence: 15.09.2011
• Opponents: prof. RNDr. Daniel Kráľ, Ph.D., DSc.

Guidelines

Graph immersions are a natural counterpart to widely studied concepts of graph minors and topological graph minors, and yet their theory is much less developed. Similarly to the importance of linkages for the graph minor theory, edge-disjoint linkages (which were studied extensively) should be essential to the development of such a theory. In the proposed thesis, the student will focus on various problems arising in this area, such as finding sufficient conditions for the existence of the immersions, their relationships to the connectivity parameters of the graphs, and the properties of the graphs avoiding an immersion of a fixed graph.

References

Neil Robertson, Paul D. Seymour: Graph minors XXIII. Nash-Williams' immersion conjecture. J. Comb. Theory, Ser. B 100(2): 181-205 (2010).
Neil Robertson, Paul D. Seymour: Graph Minors XIII. The Disjoint Paths Problem. J. Comb. Theory, Ser. B 63(1): 65-110 (1995).
M. DeVos, K. Kawarabayashi, B. Mohar, H. Okamura, Immersing small complete graphs, manuscript.
Andreas Huck, A sufficient condition for graphs to be weakly k-linked. Graphs and Combinatorics 7(4): 323-351 (1991).