Original title: Strukturální teorie grafových imerzí
Translated title: Structural Theory of Graph Immersions
Authors: Hruška, Michal ; Dvořák, Zdeněk (advisor) ; Klimošová, Tereza (referee)
Document type: Master’s theses
Year: 2019
Language: eng
Abstract: [eng] [cze]
Immersion is a notion of graph inclusion related to the notion of graph minors. While the structural theory of graph minors is extensive, there are still numerous open problems in the structural theory of graph immersions. Kuratowski's theorem claims that the class of graphs that do not contain a subdivision of the graphs K3,3 and K5 is exactly the class of planar graphs. The main goal of this thesis is to describe the structure of the graphs that do not contain an immersion of K3,3. Such graphs can be separated by small edge cuts into small graphs or planar 3-regular graphs. 1 Imerze je pojem inkluze grafů související s pojmem grafových minorů. Zatímco strukturální teorie grafových minorů je rozsáhlá, ve strukturální teorii grafových imerzí je stále velké množství otevřených problémů. Kuratowského věta tvrdí, že třída grafů, které neobsahují dělení grafů K3,3 a K5 je právě třída rovinných grafů. Hlavním cílem práce je popsat strukturu grafů neobsahujících imerzi K3,3. Takové grafy mohou být rozděleny pomocí malých hranových řezů na malé grafy nebo rovinné 3-regulární grafy. 1
Keywords: decomposition theorems; graph immersions; structural graph theory; grafové imerze; grafové rozklady; strukturální teorie grafů

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/108944

Permalink: http://www.nusl.cz/ntk/nusl-405420


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Master’s theses