Abstract

Kantenfärbungen mit Gleichmäßigkeitsbedingungen
- Polynomiell lösbare Spezialfälle Ines Maria Raschendorfer, TU Kaiserslautern
ZUSAMMENFASSUNG
Das theoretische Interesse an Graphenfärbungen reicht bis Mitte des 19. Jahrhunderts zurück,
als eines der wohl bekanntesten Färbungsprobleme, das sogenannte Vier-Farben Problem, formuliert
wurde. Es wurde hierbei die Frage gestellt, ob vier Farben im Allgemeinen ausreichend sind, um
eine beliebige (Land-)Karte in der Ebene derart zu färben, dass benachbarte Gebiete paarweise
unterschiedlich gefärbt sind.
Im Laufe der Jahre wurden immer mehr, häufig praktisch motivierte, Färbungsprobleme in
Graphen aufgestellt. Diese Arbeit beschäftigt sich mit gleichmäßigen Kantenfärbungsproblemen. Für
diese wird gefordert, dass sich die Anzahlen zweier beliebiger Farben unter den inzidenten Kanten
eines jeden Knotens (bei gegebener Farbanzahl) um höchstens eins unterscheiden dürfen. Auch
dieses Färbungsproblem verfügt über eine gewisse praktische Relevanz, z.B. in der Schulstundenplanung. So wäre es etwa möglich, jedem Lehrer und jeder Klasse einen Knoten in einem Graphen
zuzuordnen und dann jeweils pro Termin, an dem ein Lehrer eine Klasse in der zu planenden
Woche unterrichten soll, eine Kante zwischen dem entsprechenden Lehrer- und Klassen-Knoten
einzufügen. Wird in diesem Graphen dann eine gleichmäßige Kantenfärbung mit fünf Farben (eine
Farbe pro Wochentag) bestimmt, so ist gewährleistet, dass die Arbeitsverteilung der Lehrer und
der Schüler über die Woche hinweg ausgewogen ist.
Kantenfärbungsprobleme dieser Art werden bereits seit den siebziger Jahren betrachtet. Der
Hauptfokus in der vorhandenen Literatur liegt dabei auf hinreichenden Bedingungen über die
Existenz von gleichmäßigen Kantenfärbungen bei gegebener Farbanzahl. Diese Arbeit legt den
Schwerpunkt auf die algorithmische Seite des Problems und dabei insbesondere auf polynomiell
lösbare Spezialfälle.
Zu Beginn der Arbeit wird das soeben vorgestellte Färbungsproblem motiviert und das weitere
Vorgehen zusammengefasst. Es folgt eine Einführung in die in der Arbeit verwendete allgemeine
mathematische Terminologie und anschließend wird das gleichmäßige Kantenfärbungsproblem
formal definiert. Dabei werden Beispiele betrachtet und weitergehende Nebenbedingungen beschrieben. Zusätzlich werden verallgemeinernde Konzepte erläutert und es wird ein Literaturüberblick gegeben. Als Nächstes werden die zugehörigen Entscheidungsversionen formuliert und
es wird gezeigt, dass die betrachteten Probleme N P -vollständig sind. Somit ist eine Motivation
für die Suche nach polynomiell lösbaren Spezialfällen gegeben. Es werden in der Arbeit sowohl
bereits in der Literatur behandelte Graphenklassen untersucht und näher analysiert, als auch
Graphenklassen betrachtet, die bisher noch nicht in diesem Zusammenhang untersucht worden
sind. Ein besonderes Augenmerk wird dabei auf vollständige Graphen gelegt. Für diese existiert
bereits ein notwendiges und hinreichendes Existenzkriterium, das allerdings nicht unter dem
Gesichtspunkt effizienter Algorithmen inklusive Laufzeitanalysen gezeigt wurde. Eben solche
werden in dieser Arbeit unter Verwendung eines bekannten Algorithmus für minimale gewöhnliche Kantenfärbungen, von Regenbogen-Matchings und von Hamilton-Zerlegungen entwickelt. Im
Bereich der Regenbogen-Matchings wird die Literatur durch die Erarbeitung einer rekursiven
Formel zur Auffindung eines solchen Matchings mit beschränkter Kantenanzahl in einem geraden
vollständigen Graphen ergänzt.
1
ABSTRACT
The theoretical discussions on the topic of graph coloring date back until the 19th century, when
one of the most famous coloring problems was formulated: the Four-Color problem. This problem
poses the question, if four colors are sufficient to color an arbitrary map on the plane such that
there is no conflict w.r.t. colors between two neighboring areas, i.e., none of these can be given the
same color.
Over the years, more coloring problems in graphs were invented and discussed. A lot of them
were motivated by practical applications. In this thesis the so called equitable edge-coloring problem
is considered. In this case, it is asked, that the numbers of two arbitrary colors amongst all edges
incident with a vertex differ by at most one and this for all vertices of the graph and an a priori
given number of colors. This coloring problem can e.g. be used to model a timetabling problem in a
school. Imagine therefor that each teacher and each class is identified with a vertex in a graph. This
graph is complemented by an edge between a class-vertex and a teacher-vertex for each meeting
that class and teacher should have in the course of the week that is to be planned. By determining
an equitable edge-coloring using five colors (one color per day of the week), one assures a balanced
weekly workload for teachers and pupils alike.
Edge-coloring problems of this type have been considered since the seventies. The main research
interest in the literature lies with sufficient conditions for the existence of equitable edge-colorings
with a given number of colors. This thesis focuses on the algorithmic part of the problem and in
particular on polynomially solvable special cases.
At the beginning of the thesis, the coloring problem introduced above is motivated and the
further proceeding is summarized. It follows an introduction to the general mathematical nomenclature used in the thesis and then a formal definition of the equitable edge-coloring problem is
given. Examples are discussed and further constraints introduced. Moreover, a thorough literature
review is presented and generalizing concepts are discussed. Thereafter, the previously introduced coloring problems are formulated in their decision versions and it is shown, that they are
N P -complete. These results give rise to the search of polynomially solvable special cases. In the
thesis, graph classes for which results are already known from the literature are discussed and
analyzed in (more) detail, as well as graph classes that have not yet been considered w.r.t. equitable
edge-colorings. Special attention is paid to the class of complete graphs. For these graphs there
already exists a necessary and sufficient condition for the existence of equitable edge-colorings,
however, not proved with a focus on the development of efficient algorithms. Algorithms of exactly
that kind are presented in this thesis. For that purpose an algorithm from the literature to compute
a minimal usual edge-coloring is utilized, as well as the concepts of rainbow matchings and Hamilton
decompositions. Further, a recursive formula for computing efficiently a rainbow matching with
a bounded number of edges in an even complete graph is developed. This finding supplements
already known results from the literature.
2

Download Report