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
Identifer | oai:union.ndltd.org:nusl.cz/oai:invenio.nusl.cz:405420 |
Date | January 2019 |
Creators | Hruška, Michal |
Contributors | Dvořák, Zdeněk, Klimošová, Tereza |
Source Sets | Czech ETDs |
Language | English |
Detected Language | English |
Type | info:eu-repo/semantics/masterThesis |
Rights | info:eu-repo/semantics/restrictedAccess |
Page generated in 0.0025 seconds