Logo Oapen
  • Search
  • Join
    • Deposit
    • For Librarians
    • For Publishers
    • For Researchers
    • Funders
    • Resources
    • OAPEN
    • For Librarians
    • For Publishers
    • For Researchers
    • Funders
    • Resources
    • OAPEN
    View Item 
    •   OAPEN Home
    • View Item
    •   OAPEN Home
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Matching minors in bipartite graphs

    Thumbnail
    Download PDF Viewer
    Web Shop
    Author(s)
    Wiederrecht, Sebastian
    Collection
    AG Universitätsverlage
    Language
    English
    Show full item record
    Abstract
    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.
    URI
    https://library.oapen.org/handle/20.500.12657/57270
    Keywords
    matching minor; structural graph theory; bipartite; perfect matching
    DOI
    10.14279/depositonce-14958
    ISBN
    9783798332522, 9783798332539
    Publisher
    Universitätsverlag der Technischen Universität Berlin
    Publisher website
    https://verlag.tu-berlin.de/
    Publication date and place
    Berlin, 2022
    Series
    Foundations of computing, 16
    Pages
    476
    Rights
    https://creativecommons.org/licenses/by/4.0/
    • Imported or submitted locally

    Browse

    All of OAPENSubjectsPublishersLanguagesCollections

    My Account

    LoginRegister

    Export

    Repository metadata
    Logo Oapen
    • For Librarians
    • For Publishers
    • For Researchers
    • Funders
    • Resources
    • OAPEN

    Newsletter

    • Subscribe to our newsletter
    • view our news archive

    Follow us on

    License

    • If not noted otherwise all contents are available under Attribution 4.0 International (CC BY 4.0)

    Credits

    • logo EU
    • This project received funding from the European Union's Horizon 2020 research and innovation programme under grant agreement No 683680, 810640, 871069 and 964352.

    OAPEN is based in the Netherlands, with its registered office in the National Library in The Hague.

    Director: Niels Stern

    Address:
    OAPEN Foundation
    Prins Willem-Alexanderhof 5
    2595 BE The Hague
    Postal address:
    OAPEN Foundation
    P.O. Box 90407
    2509 LK The Hague

    Websites:
    OAPEN Home: www.oapen.org
    OAPEN Library: library.oapen.org
    DOAB: www.doabooks.org

     

     

    Export search results

    The export option will allow you to export the current search results of the entered query to a file. Differen formats are available for download. To export the items, click on the button corresponding with the preferred download format.

    A logged-in user can export up to 15000 items. If you're not logged in, you can export no more than 500 items.

    To select a subset of the search results, click "Selective Export" button and make a selection of the items you want to export. The amount of items that can be exported at once is similarly restricted as the full export.

    After making a selection, click one of the export format buttons. The amount of items that will be exported is indicated in the bubble next to export format.