Matching minors in bipartite graphs

 0 Người đánh giá. Xếp hạng trung bình 0

Tác giả: Sebastian Wiederrecht

Ngôn ngữ: eng

ISBN-13: 978-3798332522

ISBN: depositonce-14958

Ký hiệu phân loại:

Thông tin xuất bản: Berlin : Universitätsverlag der Technischen Universität Berlin, 2022

Mô tả vật lý: 1 electronic resource (476 p.)

Bộ sưu tập: Tài liệu truy cập mở

ID: 343267

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.
1. 
Tạo bộ sưu tập với mã QR

THƯ VIỆN - TRƯỜNG ĐẠI HỌC CÔNG NGHỆ TP.HCM

ĐT: (028) 71010608 | Email: tt.thuvien@hutech.edu.vn

Copyright @2024 THƯ VIỆN HUTECH