Matching minors in bipartite graphs
In this thesis we adapt fundamental parts of the Graph Minors series of Robertson and Seymour for the study of matching minors and investigate a connection to the study of directed graphs. We develope matching theoretic to established results of graph minor theory: We characterise the existence of...
Shranjeno v:
| Glavni avtor: | |
|---|---|
| Format: | Online |
| Jezik: | angleščina |
| Izdano: |
Universitätsverlag der Technischen Universität Berlin
2022
|
| Teme: | |
| Online dostop: | OCN: 1367233217 |
| Oznake: |
Brez oznak, prvi označite!
|
| _version_ | 1869516412846866432 |
|---|---|
| author | Wiederrecht, Sebastian |
| author_browse | Wiederrecht, Sebastian |
| author_facet | Wiederrecht, Sebastian |
| author_sort | Wiederrecht, Sebastian |
| collection | Directory of Open Access Books |
| description | In this thesis we adapt fundamental parts of the Graph Minors series of Robertson and Seymour for the study of matching minors and investigate a connection to the study of directed graphs. We develope matching theoretic to established results of graph minor theory: We characterise the existence of a cross over a conformal cycle by means of a topological property. Furthermore, we develope a theory for perfect matching width, a width parameter for graphs with perfect matchings introduced by Norin. here we show that the disjoint alternating paths problem can be solved in polynomial time on graphs of bounded width. Moreover, we show that every bipartite graph with high perfect matching width must contain a large grid as a matching minor. Finally, we prove an analogue of the we known Flat Wall theorem and provide a qualitative description of all bipartite graphs which exclude a fixed matching minor. |
| format | Online |
| id | doab-20.500.12854ir-87653 |
| institution | Directory of Open Access Books |
| language | eng |
| publishDate | 2022 |
| publishDateRange | 2022 |
| publishDateSort | 2022 |
| publisher | Universitätsverlag der Technischen Universität Berlin |
| publisherStr | Universitätsverlag der Technischen Universität Berlin |
| record_format | ojs |
| spelling | doab-20.500.12854ir-876532025-04-03T09:05:12Z Matching minors in bipartite graphs Wiederrecht, Sebastian matching minor; structural graph theory; bipartite; perfect matching In this thesis we adapt fundamental parts of the Graph Minors series of Robertson and Seymour for the study of matching minors and investigate a connection to the study of directed graphs. We develope matching theoretic to established results of graph minor theory: We characterise the existence of a cross over a conformal cycle by means of a topological property. Furthermore, we develope a theory for perfect matching width, a width parameter for graphs with perfect matchings introduced by Norin. here we show that the disjoint alternating paths problem can be solved in polynomial time on graphs of bounded width. Moreover, we show that every bipartite graph with high perfect matching width must contain a large grid as a matching minor. Finally, we prove an analogue of the we known Flat Wall theorem and provide a qualitative description of all bipartite graphs which exclude a fixed matching minor. 2022-07-09T04:07:37Z 2022-07-09T04:07:37Z 2022-07-08T09:56:49Z 2022 book OCN: 1367233217 https://library.oapen.org/handle/20.500.12657/57270 9783798332522 https://directory.doabooks.org/handle/20.500.12854/87653 eng Foundations of computing open access image/jpeg image/jpeg image/jpeg image/jpeg Attribution 4.0 International Attribution 4.0 International Attribution 4.0 International Attribution 4.0 International https://library.oapen.org/bitstream/20.500.12657/57270/1/wiederrecht_sebastian.pdf https://library.oapen.org/bitstream/20.500.12657/57270/1/wiederrecht_sebastian.pdf https://library.oapen.org/bitstream/20.500.12657/57270/1/wiederrecht_sebastian.pdf https://library.oapen.org/bitstream/20.500.12657/57270/1/wiederrecht_sebastian.pdf Universitätsverlag der Technischen Universität Berlin 10.14279/depositonce-14958 10.14279/depositonce-14958 e39576fc-df94-4af7-8fbe-4f7c2d6b68f3 9783798332522 AG Universitätsverlage 476 Berlin open access |
| spellingShingle | matching minor; structural graph theory; bipartite; perfect matching Wiederrecht, Sebastian Matching minors in bipartite graphs |
| title | Matching minors in bipartite graphs |
| title_full | Matching minors in bipartite graphs |
| title_fullStr | Matching minors in bipartite graphs |
| title_full_unstemmed | Matching minors in bipartite graphs |
| title_short | Matching minors in bipartite graphs |
| title_sort | matching minors in bipartite graphs |
| topic | matching minor; structural graph theory; bipartite; perfect matching |
| topic_facet | matching minor; structural graph theory; bipartite; perfect matching |
| url | OCN: 1367233217 |
| work_keys_str_mv | AT wiederrechtsebastian matchingminorsinbipartitegraphs |