Immersions and edge-disjoint linkages

• Název práce v češtině: Immersions and edge-disjoint linkages
• Název v anglickém jazyce: Immersions and edge-disjoint linkages
• Klíčová slova: teorie grafů, imerze, stromová šířka
• Klíčová slova anglicky: graph theory, immersion, tree-width
• Akademický rok vypsání: 2010/2011
• Typ práce: diplomová práce
• Jazyk práce: angličtina
• Ústav: Katedra aplikované matematiky (32-KAM)
• Vedoucí / školitel: prof. Mgr. Zdeněk Dvořák, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 01.09.2010
• Datum zadání: 11.03.2011
• Datum a čas obhajoby: 15.09.2011 00:00
• Datum odevzdání elektronické podoby: 04.08.2011
• Datum odevzdání tištěné podoby: 05.08.2011
• Datum proběhlé obhajoby: 15.09.2011
• Oponenti: prof. RNDr. Daniel Kráľ, Ph.D., DSc.

Zásady pro vypracování

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.

Seznam odborné literatury

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).