Überdeckungszahlen in Theorie und Praxis

• Antragsteller: Privatdozent Dr. Torsten Ueckerdt
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2023
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 520723789

Graphfärbungen und -zerlegungen, im Allgemeinen Graphüberdeckungen, sind die klassischsten Problem der Graphentheorie und Kombinatorik. Dabei wird meistens die Anzahl der verwendeten Farben, das heißt die Anzahl der Teile in einer Überdeckung, minimiert, während die konkrete Problembeschreibung spezifiziert, welche Teilgraphen des gegebenen Graphen zulässige Teile einer Überdeckung darstellen. Zusammen mit einem Kollegen habe ich 2016 begonnen, eine Theorie zu formalisieren mit der Notationen und Techniken verschiedenster Überdeckungszahlen vereinheitlicht werden konnten; darunter echte Knotenfärbungen, Kantenfärbungen, Ramsey-Zahlen, splitting numbers, Knotenüberdeckungszahlen, Graphhomomorphismen, arboricities, boxicities, Graph-Faktoren und viele mehr. Wir haben das Konzept der globalen, union, lokalen und gefalteten Überdeckungszahlen bezüglich einer beliebigen Gastklasse die aus allen Graphen besteht die ein zulässiger Teil in einer Überdeckung sein dürfen, eingeführt. Dies umfasst zahllose bekannte Überdeckungs- und Färbungsprobleme und ermöglichte es uns, neue Verbindungen zwischen bekannten Problemen zu finden und auszunutzen. Darüber hinaus konnten wir so die relevanten offenen Fragen in mehreren Gebieten genau identifizieren. Insbesondere die lokalen Überdeckungszahlen haben seitdem bereits viel Beachtung in mehreren Gebieten der Mathematik und Informatik bekommen -- zum Beispiel durch unsere Einführung von lokaler Poset Dimension, lokaler boxicity von Graphen, sowie lokalen page numbers in den letzten Jahren. In diesem Projekt soll die Theorie der Überdeckungszahlen erweitert, verbessert und genutzt werden. Dies beinhaltet sechs Forschungsthemen die sich mit fundamentalen Eigenschaften, algorithmischen Aspekten, sparse graphs, Intervallgraphen, induzierten und ordered Varianten, sowie praktischen Anwendungen befassen. Während jedes einzelne Forschungsthema vielversprechende Richtungen mit konkreten offenen Fragen und Zielen bietet, soll das gesamte Projekt die Theorie der Überdeckungszahlen voranbringen, sowohl in konkreten Situationen, als auch in allgemeinen Zusammenhängen. Durch exzellente Forschung und Vorträge auf den wichtigsten Konferenzen mit starken Resultaten und nützlichen Verbindungen sollen die vier Überdeckungszahlen --global, union, lokal und gefaltet-- noch stärker in der wissenschaftlichen Welt präsentiert, etabliert und beworben werden, und die Graphentheorie ein Stück weiter voranbringen.

• DFG-Verfahren: Sachbeihilfen