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.

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.

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

The history of silicon technology showed that controlled doping was a key step for the realization of e®ective, stable and reproducible devices. When the conduction type was no longer determined by impurities but could be controlled by doping, the breakthrough of classical microelectronics became possible. Unlike inorganic semiconductors, organic dyes are up to now usually prepared in a nominally undoped form. However, controlled and stable doping is desirable in many organic-based devices as well. If we succeed in shifting the Fermi level towards the transport states, this could reduce ohmic losses, ease carrier injection from contacts and increase the built-in potential of Schottky- or pn-junctions.

The history of silicon technology showed that controlled doping was a key step for the realization of e®ective, stable and reproducible devices. When the conduction type was no longer determined by impurities but could be controlled by doping, the breakthrough of classical microelectronics became possible. Unlike inorganic semiconductors, organic dyes are up to now usually prepared in a nominally undoped form. However, controlled and stable doping is desirable in many organic-based devices as well. If we succeed in shifting the Fermi level towards the transport states, this could reduce ohmic losses, ease carrier injection from contacts and increase the built-in potential of Schottky- or pn-junctions.