Lexikon der Mathematik: Eckenfärbung
Abbildung der Ecken eines Graphen in die natürlichen Zahlen.
Ist G ein gegebener Graph mit der Eckenmenge E(G), so ist eine Abbildung h : E(G) → {1, 2,…, k}, so daß h(x) ≠ h(y) für alle adjazenten Ecken x und y gilt, eine Ecken-färbung von G. Man spricht auch genauer von einer k-Eckenfärbung oder von einem k-färbbaren Graphen. Ist Ei die Menge aller Ecken von G mit der Farbe i, so nennt man Ei Farbenklasse. Die chromatische Zahl χ(G) von G ist die kleinste Zahl k, für die G eine k-Ecken-färbung besitzt. Ist χ(G) = k, so heißt G auch k-chromatischer Graph.
Färbt man jede Ecke eines Graphen mit einer anderen Farbe, so ist das eine Eckenfärbung, womit die Existenz der chromatischen Zahl gesichert ist. Bezeichnet ω(G) die Cliquenzahl eines Graphen G, so benötigt man natürlich mindestens ω(G) Farben für eine Eckenfärbung von G. Daher ergeben sich unmittelbar die Ungleichungen
\begin{eqnarray}\omega (G)\le \chi (G)\le \,|E(G)|.\end{eqnarray}
Ist h eine k-Eckenfärbung eines Graphen G und
\begin{eqnarray}{E}_{i}=\{x|x\in E(G)\,\rm{mit}\,h(x)=i\}\end{eqnarray}
\begin{eqnarray}E(G)=\displaystyle \underset{i=1}{\overset{k}{\cup }}{E}_{i}\end{eqnarray}
mit Ei ∩ Ej = ∅ für alle 1 ≤ i< j ≤ k, und jede Farbenklasse Ei ist eine unabhängige Eckenmenge von G. Daher ist jeder Graph G natürlich χ(G)-partit. Umgekehrt liefert jede Zerlegung von E(G) in k disjunkte unabhängige Eckenmengen eine k-Eckenfärbung von G.Das Entscheidungsproblem, ob ein gegebener Graph k-färbbar ist, zählt für k ≥ 3 zu den bekannten NP-vollständigen Problemen. Der folgende einfache Algorithmus liefert aber eine Methode, um die Ecken eines Graphen G mit δ(G) + 1 Farben zu färben, wobei δ(G) der Maximalgrad von G bedeutet.
Man wähle eine erste Ecke und färbe sie beliebig. Danach wird jeweils eine noch nicht gefärbte Ecke gewählt. Diese erhält eine andere Farbe als alle schon gefärbten Ecken, die mit ihr adjazent sind. Das ist stets möglich, da jeder Ecke mit höchstens δ(G) Ecken adjazent ist und nach Voraussetzung δ(G) + 1 Farben zur Verfügung stehen. Nach |E(G)| solcher Schritte hat man dann alle Ecken des Graphen gefärbt.
Dieses Verfahren liefert für jeden Graphen G insbesondere die Abschätzung
\begin{eqnarray}\chi (G)\le \Delta (G)+1.\end{eqnarray}
Ist H der vollständige Graph oder ein Kreis ungerader Länge, so gilt natürlich χ(H) = δ(H) + 1. Im Jahre 1941 hat R.L. Brooks aber nachgewiesen, daß dies die einzigen Graphen sind, die diese Gleichung erfüllen.
Ist G ein zusammenhängender Graph, der weder ein Kreis ungerader Länge noch vollständig ist, so gilt χ(G) ≤ δ(G).
Dieser Satz von Brooks spielt in der Theorie der Eckenfärbung eine wichtige Rolle.
Ein Graph G heißt kritisch, wenn für jeden echten TeilgraphenH die Ungleichung χ(H) < χ (G) gilt. Ist G kritisch mit χ(G) = k, so heißt G auch k-kritisch oder kritisch k-färbbarer Graph. Die folgenden Eigenschaften der kritischen Graphen stammen im wesentlichen von G.A. Dirac (1962).
Ein kritischer Graph ist zusammenhängend und besitzt keine Artikulation. Ist χ(G) = k ≥ 2, so enthält G einen k-kritischen Teilgraphen. Man erreicht dies durch sukzessive Herausnahme von Kanten und Ecken. Ist G ein k-kritischer Graph, so gilt k − 1 ≤ δ(G), wobei δ(G) der Minimalgrad bedeutet.
Der vollständige Graph K2 ist der einzige 2-kritische Graph. Die Menge der 3-kritischen Graphen besteht aus allen Kreisen ungerader Länge. Der Grötzsch-Graph ist ein 4-kritischer Graph. Darüber hinaus ist der Grötzsch-Graph derjenige 4-chromatische Graph ohne Kreise der Länge 3 mit minimaler Eckenzahl.
Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.