Bei der Partitionierung von Graphen versucht man, Strukturen in Graphen zu finden (etwa 3-Färbungen oder kleine Bisektionen). Mithilfe von Eigenwerten und Eigenvektoren können solche Probleme oftmals effizient gelöst werden. Wir stellen einen Algorithmus vor, der auf einem sehr allgemeinen Modell für zufällige Graphen bewiesenermaßen sehr gute Dienste leistet. Weiterhin untersuchen wir zufällige 3Sat-Formeln. Hier wollen wir mit Eigenwerten obere Schranken an die Anzahl der erfüllbaren Klauseln finden. Die gefundenen Schranken sind (in den meisten Fällen) nahezu optimal.

A b-coloring of G is a proper vertex coloring such that there is a vertex in each color class, which is adjacent to at least one vertex in every other color class. Such a vertex is called a color-dominating vertex. The b-chromatic number of G is the largest k such that there is a b-coloring of G by k colors. Moreover, if for every integer k, between chromatic number and b-chromatic number, there exists a b-coloring of G by k colors, then G is b-continuous. Determining the b-chromatic number of a graph G and the decision whether the given graph G is b-continuous or not is NP-hard. Therefore, it is interesting to find new results on b-colorings and b-continuity for special graphs. In this thesis, for several graph classes some exact values as well as bounds of the b-chromatic number were ascertained. Among all we considered graphs whose independence number, clique number, or minimum degree is close to its order as well as bipartite graphs. The investigation of bipartite graphs was based on considering of the so-called bicomplement which is used to determine the b-chromatic number of special bipartite graphs, in particular those whose bicomplement has a simple structure. Then we studied some graphs whose b-chromatic number is close to its t-degree. At last, the b-continuity of some graphs is studied, for example, for graphs whose b-chromatic number was already established in this thesis. In particular, we could prove that Halin graphs are b-continuous.

Im Jahre 2002 führten A. Hackmann, A. Kemnitz und M. Marangio das Konzept der [r, s, t]-Färbungen als eine Verallgemeinerung der Knoten-, Kanten- und Totalfärbungen von Graphen ein. Für gegebene nicht negative Zahlen r, s und t ist eine [r, s, t]-Färbung von einem Graphen G eine Abbildung c, von V(G) und E(G) auf die Menge {1, 2,…, k}, wobei c(v) und c(w) sich um mindestens r unterscheiden, für je zwei adjazente Konten v, w ; c(e) und c(f) unterscheiden sich um mindestens s für je zwei adjazente Kanten e, f ; und c(v) und c(e) unterscheiden sich um mindestens t für je zwei inzidente Knoten v und Kanten e . Die [r, s, t]-chromatische Zahl von G ist die kleinste Zahl k, für die eine solche Färbung für G existiert. In dieser Dissertation wird die [r, s, t]-chromatische Zahl für Wege, Kreise und Sterne mit drei Blättern vollständig bestimmt. Darüber hinaus werden Schranken für Sterne mit mehr als drei Blättern und weitere Ergebnisse für bipartite und vollständige Graphen vorgestellt.

Knotenfärbungen mit Abstandsbedingungen sind graphentheoretische Konzepte, motiviert durch das praktische Problem der Frequenzzuweisung in Mobilfunknetzen. In der Arbeit werden verschiedene Varianten solcher Färbungen vorgestellt. Für (Listen-)Färbungen mit einer beliebigen Anzahl r von Abstandsbedingungen werden allgemeine Eigenschaften und Schranken für die benötigte Anzahl von Farben bewiesen. Anschließend wird der Spezialfall r=2 behandelt. Färbungen mit zwei Abstandsbedingungen - die sogenannten L(d,s)-Labellings - werden für eine Reihe von Graphenklassen untersucht, u.a. für reguläre Parkettierungen, Weg- und Kreispotenzen und Graphen mit Durchmesser 2. Die Listenversion dieser Färbungen - die sogenannten L(d,s)-List Labellings - werden für Wege, Sterne, Kreise und Kakteen betrachtet. Ferner werden Untersuchungen zum Zusammenhang von L(2,1)-Labellings und L(2,1)-List Labellings bei speziellen Bäumen durchgeführt.

It is known to be an NP-complete problem to color a graph with a given number of colors. We present some approximation algorithms which come close to the desired number of colors. We also develop an algorithm that colors k-colorable graphs with ~O(n^a(k)) colors, where a(2)=0, a(3)=3/14 and a(k)=1 - 6/(k+4+3(1-2/k)/(1-a(k-2))) for k >= 4, as presented in [20]. This formula has been generalized for new possible base algorithms. / Das Problem, einen Graphen mit einer gegebenen Anzahl Farben zu färben, ist als NP-vollständig bekannt. Hier werden einige Algorithmen vorgestellt, die für dieses Problem eine gute Approximation liefern. Des Weiteren wird ein allgemeines Färbungsverfahren hergeleitet, das für k-färbbare Graphen den bisher besten existierenden Algorithmus darstellt. Es können k-färbbare Graphen mit ~O(n^a(k)) Farben gefärbt werden, wobei a(2)=0, a(3)=3/14 und a(k) = 1 - 6/(k+4+3(1-2/k)/(1-a(k-2))) für k >= 4 gilt [20]. Diese Formel wurde für neue Basisalgorithmen verallgemeinert.

Bei der Partitionierung von Graphen versucht man, Strukturen in Graphen zu finden (etwa 3-Färbungen oder kleine Bisektionen). Mithilfe von Eigenwerten und Eigenvektoren können solche Probleme oftmals effizient gelöst werden. Wir stellen einen Algorithmus vor, der auf einem sehr allgemeinen Modell für zufällige Graphen bewiesenermaßen sehr gute Dienste leistet. Weiterhin untersuchen wir zufällige 3Sat-Formeln. Hier wollen wir mit Eigenwerten obere Schranken an die Anzahl der erfüllbaren Klauseln finden. Die gefundenen Schranken sind (in den meisten Fällen) nahezu optimal.

Im Jahre 2002 führten A. Hackmann, A. Kemnitz und M. Marangio das Konzept der [r, s, t]-Färbungen als eine Verallgemeinerung der Knoten-, Kanten- und Totalfärbungen von Graphen ein. Für gegebene nicht negative Zahlen r, s und t ist eine [r, s, t]-Färbung von einem Graphen G eine Abbildung c, von V(G) und E(G) auf die Menge {1, 2,…, k}, wobei c(v) und c(w) sich um mindestens r unterscheiden, für je zwei adjazente Konten v, w ; c(e) und c(f) unterscheiden sich um mindestens s für je zwei adjazente Kanten e, f ; und c(v) und c(e) unterscheiden sich um mindestens t für je zwei inzidente Knoten v und Kanten e . Die [r, s, t]-chromatische Zahl von G ist die kleinste Zahl k, für die eine solche Färbung für G existiert. In dieser Dissertation wird die [r, s, t]-chromatische Zahl für Wege, Kreise und Sterne mit drei Blättern vollständig bestimmt. Darüber hinaus werden Schranken für Sterne mit mehr als drei Blättern und weitere Ergebnisse für bipartite und vollständige Graphen vorgestellt.

Knotenfärbungen mit Abstandsbedingungen sind graphentheoretische Konzepte, motiviert durch das praktische Problem der Frequenzzuweisung in Mobilfunknetzen. In der Arbeit werden verschiedene Varianten solcher Färbungen vorgestellt. Für (Listen-)Färbungen mit einer beliebigen Anzahl r von Abstandsbedingungen werden allgemeine Eigenschaften und Schranken für die benötigte Anzahl von Farben bewiesen. Anschließend wird der Spezialfall r=2 behandelt. Färbungen mit zwei Abstandsbedingungen - die sogenannten L(d,s)-Labellings - werden für eine Reihe von Graphenklassen untersucht, u.a. für reguläre Parkettierungen, Weg- und Kreispotenzen und Graphen mit Durchmesser 2. Die Listenversion dieser Färbungen - die sogenannten L(d,s)-List Labellings - werden für Wege, Sterne, Kreise und Kakteen betrachtet. Ferner werden Untersuchungen zum Zusammenhang von L(2,1)-Labellings und L(2,1)-List Labellings bei speziellen Bäumen durchgeführt.

A b-coloring of G is a proper vertex coloring such that there is a vertex in each color class, which is adjacent to at least one vertex in every other color class. Such a vertex is called a color-dominating vertex. The b-chromatic number of G is the largest k such that there is a b-coloring of G by k colors. Moreover, if for every integer k, between chromatic number and b-chromatic number, there exists a b-coloring of G by k colors, then G is b-continuous. Determining the b-chromatic number of a graph G and the decision whether the given graph G is b-continuous or not is NP-hard. Therefore, it is interesting to find new results on b-colorings and b-continuity for special graphs. In this thesis, for several graph classes some exact values as well as bounds of the b-chromatic number were ascertained. Among all we considered graphs whose independence number, clique number, or minimum degree is close to its order as well as bipartite graphs. The investigation of bipartite graphs was based on considering of the so-called bicomplement which is used to determine the b-chromatic number of special bipartite graphs, in particular those whose bicomplement has a simple structure. Then we studied some graphs whose b-chromatic number is close to its t-degree. At last, the b-continuity of some graphs is studied, for example, for graphs whose b-chromatic number was already established in this thesis. In particular, we could prove that Halin graphs are b-continuous.:Contents 1 Introduction 2 Preliminaries 2.1 Basic terminology 2.2 Colorings of graphs 2.2.1 Vertex colorings 2.2.2 a-colorings 3 b-colorings 3.1 General bounds on the b-chromatic number 3.2 Exact values of the b-chromatic number for special graphs 3.2.1 Graphs with maximum degree at most 2 3.2.2 Graphs with independence number close to its order 3.2.3 Graphs with minimum degree close to its order 3.2.4 Graphs G with independence number plus clique number at most number of vertices 3.2.5 Further known results for special graphs 3.3 Bipartite graphs 3.3.1 General bounds on the b-chromatic number for bipartite graphs 3.3.2 The bicomplement 3.3.3 Bicomplements with simple structure 3.4 Graphs with b-chromatic number close to its t-degree 3.4.1 Regular graphs 3.4.2 Trees and Cacti 3.4.3 Halin graphs 4 b-continuity 4.1 b-spectrum of special graphs 4.2 b-continuous graph classes 4.2.1 Known b-continuous graph classes 4.2.2 Halin graphs 4.3 Further graph properties concerning b-colorings 4.3.1 b-monotonicity 4.3.2 b-perfectness 5 Conclusion Bibliography

It is known to be an NP-complete problem to color a graph with a given number of colors. We present some approximation algorithms which come close to the desired number of colors. We also develop an algorithm that colors k-colorable graphs with ~O(n^a(k)) colors, where a(2)=0, a(3)=3/14 and a(k)=1 - 6/(k+4+3(1-2/k)/(1-a(k-2))) for k >= 4, as presented in [20]. This formula has been generalized for new possible base algorithms. / Das Problem, einen Graphen mit einer gegebenen Anzahl Farben zu färben, ist als NP-vollständig bekannt. Hier werden einige Algorithmen vorgestellt, die für dieses Problem eine gute Approximation liefern. Des Weiteren wird ein allgemeines Färbungsverfahren hergeleitet, das für k-färbbare Graphen den bisher besten existierenden Algorithmus darstellt. Es können k-färbbare Graphen mit ~O(n^a(k)) Farben gefärbt werden, wobei a(2)=0, a(3)=3/14 und a(k) = 1 - 6/(k+4+3(1-2/k)/(1-a(k-2))) für k >= 4 gilt [20]. Diese Formel wurde für neue Basisalgorithmen verallgemeinert.