Please use this identifier to cite or link to this item: doi:10.22028/D291-29620
Title: On some covering, partition and connectivity problems in graphs
Author(s): Issac, Davis
Language: English
Year of Publication: 2019
DDC notations: 004 Computer science, internet
Publikation type: Doctoral Thesis
Abstract: We look at some graph problems related to covering, partition, and connectivity. First, we study the problems of covering and partitioning edges with bicliques, especially from the viewpoint of parameterized complexity. For the partition problem, we develop much more efficient algorithms than the ones previously known. In contrast, for the cover problem, our lower bounds show that the known algorithms are probably optimal. Next, we move on to graph coloring, which is probably the most extensively studied partition problem in graphs. Hadwiger’s conjecture is a long-standing open problem related to vertex coloring. We prove the conjecture for a special class of graphs, namely squares of 2-trees, and show that square graphs are important in connection with Hadwiger’s conjecture. Then, we study a coloring problem that has been emerging recently, called rainbow coloring. This problem lies in the intersection of coloring and connectivity. We study different variants of rainbow coloring and present bounds and complexity results on them. Finally, we move on to another parameter related to connectivity called spanning tree congestion (STC). We give tight bounds for STC in general graphs and random graphs. While proving the results on
Wir betrachten einige Graphprobleme mit Bezug auf Abdeckung, Partition und Konnektivität. Zunächst untersuchen wir Kantenabdeckung und -partition mit Bicliquen, insbesondere im Hinblick auf parametrisierte Komplexität. Für das Partitionierungsproblem entwickeln wir sehr viel effizientere Algorithmen als die bisher bekannten. Für das Abdeckungsproblem hingegen zeigen unsere unteren Schranken, dass die bereits bekannten Algorithmen wahrscheinlich optimal sind. Als Nächstes betrachten wir Graphfärbung, das wahrscheinlich am meisten untersuchte Partitionsproblem in Graphen. Hadwigers Vermutung ist ein seit Langem bestehendes offenes Problem bezüglich der Knotenfärbung. Wir beweisen diese Vermutung für eine spezielle Graphklasse, nämlich Quadrate von 2-Bäumen, und zeigen, dass Quadratgraphen wichtig in Bezug auf Hadwigers Vermutung sind. Danach untersuchen wir das Problem der sogenannten Regenbogenfärbung. Dieses erst kürzlich entstandene Problem liegt im Schnittpunkt der Probleme Färbung und Konnektivität. Wir untersuchen verschiedene Varianten der Regenbogenfärbung und zeigen Schranken und Komplexitätsergebnisse. Schließlich gehen wir über zu einem weiteren Konnektivitätsparameter, der sogenannten spanning tree congestion (STC). Wir präsentieren scharfe Schranken für STC in allgemeinen und zufällig generierten Graphen. Unsere Ergebnisse in diesem Bereich leisten darüberhinaus einen Beitrag zu dem verwandten Gebiet der verbundenen Partitionierung.
Link to this record: urn:nbn:de:bsz:291--ds-296205
hdl:20.500.11880/28007
http://dx.doi.org/10.22028/D291-29620
Advisor: Karrenbauer, Andreas
Date of oral examination: 9-Sep-2019
Date of registration: 7-Oct-2019
Faculty: MI - Fakultät für Mathematik und Informatik
Department: MI - Informatik
Collections:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Files for this record:
File Description SizeFormat 
Davis Issac_thesis.pdf3,43 MBAdobe PDFView/Open


Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.