View
0
Download
0
Category
Preview:
Citation preview
Sommerakademie La Villa 29.08.2004 - 11.09.2004
Graphen ohne kurze Kreise und großer Farbungszahl
Arbeitsgruppe 4: “Probabilistische Methoden”
Vortrag 9
gehalten von Sara (Elisabeth) Adams
Quellen:Stefanie Gerke: “Random Graphs”, Lecture Notes ETH Zurich, 2004M. Aigner, G. M. Ziegler: “Proofs from THE BOOK”, Springer, 2001
1
Begriffe
Sei G ein Graph mit Knotenmenge V (G) und Kantenmenge E(G). Wir benotigendie folgenden Bezeichnungen:
• Clique: C ⊂ V (G) : a, b ∈ C ⇒ (a, b) ∈ E(G) [clique]
• Cliquenzahl ω(G): maximale Große einer Clique von G [clique number]
• stabile Menge: S ⊂ V (G) : a, b ∈ S ⇒ (a, b) 6∈ E(G) [stable set]
• α(G): maximale Große einer stabilen Menge [stable set number]
• zulassige Farbung: je zwei Endpunkte einer Kante sind verschieden gefarbt
• Farbungszahl χ(G): kleinst mogliche Anzahl an verschiedenen Farben, um einenGraphen zulassig zu farben [chromatic number]
• Taillenweite γ(G): Große des kleinsten Kreises von G [girth]
2
Begriffe
Sei G ein Graph mit Knotenmenge V (G) und Kantenmenge E(G). Wir benotigendie folgenden Bezeichnungen:
• Clique: C ⊂ V (G) : a, b ∈ C ⇒ (a, b) ∈ E(G) [clique]
• Cliquenzahl ω(G): maximale Große einer Clique von G [clique number]
• stabile Menge: S ⊂ V (G) : a, b ∈ S ⇒ (a, b) 6∈ E(G) [stable set]
• α(G): maximale Große einer stabilen Menge [stable set number]
• zulassige Farbung: je zwei Endpunkte einer Kante sind verschieden gefarbt
• Farbungszahl χ(G): kleinst mogliche Anzahl an verschiedenen Farben, um einenGraphen zulassig zu farben [chromatic number]
• Taillenweite γ(G): Große des kleinsten Kreises von G [girth]
3
Begriffe
Sei G ein Graph mit Knotenmenge V (G) und Kantenmenge E(G). Wir benotigendie folgenden Bezeichnungen:
• Clique: C ⊂ V (G) : a, b ∈ C ⇒ (a, b) ∈ E(G) [clique]
• Cliquenzahl ω(G): maximale Große einer Clique von G [clique number]
• stabile Menge: S ⊂ V (G) : a, b ∈ S ⇒ (a, b) 6∈ E(G) [stable set]
• α(G): maximale Große einer stabilen Menge [stable set number]
• zulassige Farbung: je zwei Endpunkte einer Kante sind verschieden gefarbt
• Farbungszahl χ(G): kleinst mogliche Anzahl an verschiedenen Farben, um einenGraphen zulassig zu farben [chromatic number]
• Taillenweite γ(G): Große des kleinsten Kreises von G [girth]
4
Begriffe
Sei G ein Graph mit Knotenmenge V (G) und Kantenmenge E(G). Wir benotigendie folgenden Bezeichnungen:
• Clique: C ⊂ V (G) : a, b ∈ C ⇒ (a, b) ∈ E(G) [clique]
• Cliquenzahl ω(G): maximale Große einer Clique von G [clique number]
• stabile Menge: S ⊂ V (G) : a, b ∈ S ⇒ (a, b) 6∈ E(G) [stable set]
• α(G): maximale Große einer stabilen Menge [stable set number]
• zulassige Farbung: je zwei Endpunkte einer Kante sind verschieden gefarbt
• Farbungszahl χ(G): kleinst mogliche Anzahl an verschiedenen Farben, um einenGraphen zulassig zu farben [chromatic number]
• Taillenweite γ(G): Große des kleinsten Kreises von G [girth]
5
Begriffe
Sei G ein Graph mit Knotenmenge V (G) und Kantenmenge E(G). Wir benotigendie folgenden Bezeichnungen:
• Clique: C ⊂ V (G) : a, b ∈ C ⇒ (a, b) ∈ E(G) [clique]
• Cliquenzahl ω(G): maximale Große einer Clique von G [clique number]
• stabile Menge: S ⊂ V (G) : a, b ∈ S ⇒ (a, b) 6∈ E(G) [stable set]
• α(G): maximale Große einer stabilen Menge [stable set number]
• zulassige Farbung: je zwei Endpunkte einer Kante sind verschieden gefarbt
• Farbungszahl χ(G): kleinst mogliche Anzahl an verschiedenen Farben, um einenGraphen zulassig zu farben [chromatic number]
• Taillenweite γ(G): Große des kleinsten Kreises von G [girth]
6
Einfache Voruberlegungen
1. Jede Farbe induziert eine stabile Gruppe: ⇒ χ(G) ≥ |V (G)|α(G)
2. Jeder Knoten einer Clique muss anders gefarbt sein: ⇒ χ(G) ≥ ω(G)
Theorem
Fur jedes k, l existiert ein Graph, dessen Farbungszahl χ(G) ≥ k ist und dessenkleinster Kreis mindestens die Lange l hat, also γ(G) ≥ l.
k, l ∈ N ⇒ ∃ G : χ(G) ≥ k, γ(G) ≥ l
7
Einfache Voruberlegungen
1. Jede Farbe induziert eine stabile Gruppe: ⇒ χ(G) ≥ |V (G)|α(G)
2. Jeder Knoten einer Clique muss anders gefarbt sein: ⇒ χ(G) ≥ ω(G)
Theorem
Fur jedes k, l existiert ein Graph, dessen Farbungszahl χ(G) ≥ k ist und dessenkleinster Kreis mindestens die Lange l hat, also γ(G) ≥ l.
k, l ∈ N ⇒ ∃ G : χ(G) ≥ k, γ(G) ≥ l
8
Einfache Voruberlegungen
1. Jede Farbe induziert eine stabile Gruppe: ⇒ χ(G) ≥ |V (G)|α(G)
2. Jeder Knoten einer Clique muss anders gefarbt sein: ⇒ χ(G) ≥ ω(G)
Theorem
Fur jedes k, l existiert ein Graph, dessen Farbungszahl χ(G) ≥ k ist und dessenkleinster Kreis mindestens die Lange l hat, also γ(G) ≥ l.
k, l ∈ N ⇒ ∃ G : χ(G) ≥ k, γ(G) ≥ l
9
Brainstorming
Betrachte Zufallsgraphen mit Kantenwahrscheinlichkeit p:
• Wahle p “klein” ⇒ wahrscheinlich keine kurzen Kreise
• Wahle p “groß” ⇒ wahrscheinlich nur kleine stabile Mengen
Problematik:
p kann i.A. nicht so gewahlt werden, dass beide Bedingungen erfullt sind.
Ausweg:
• Existenz eines Hilfsgraphen
• Modifiziere diesen Hilfsgraphen
10
Brainstorming
Betrachte Zufallsgraphen mit Kantenwahrscheinlichkeit p:
• Wahle p “klein” ⇒ wahrscheinlich keine kurzen Kreise
• Wahle p “groß” ⇒ wahrscheinlich nur kleine stabile Mengen
Problematik:
p kann i.A. nicht so gewahlt werden, dass beide Bedingungen erfullt sind.
Ausweg:
• Existenz eines Hilfsgraphen
• Modifiziere diesen Hilfsgraphen
11
Brainstorming
Betrachte Zufallsgraphen mit Kantenwahrscheinlichkeit p:
• Wahle p “klein” ⇒ wahrscheinlich keine kurzen Kreise
• Wahle p “groß” ⇒ wahrscheinlich nur kleine stabile Mengen
Problematik:
p kann i.A. nicht so gewahlt werden, dass beide Bedingungen erfullt sind.
Ausweg:
• Existenz eines Hilfsgraphen
• Modifiziere diesen Hilfsgraphen
12
Brainstorming
Betrachte Zufallsgraphen mit Kantenwahrscheinlichkeit p:
• Wahle p “klein” ⇒ wahrscheinlich keine kurzen Kreise
• Wahle p “groß” ⇒ wahrscheinlich nur kleine stabile Mengen
Problematik:
p kann i.A. nicht so gewahlt werden, dass beide Bedingungen erfullt sind.
Ausweg:
• Existenz eines Hilfsgraphen
• Modifiziere diesen Hilfsgraphen
13
Brainstorming
Betrachte Zufallsgraphen mit Kantenwahrscheinlichkeit p:
• Wahle p “klein” ⇒ wahrscheinlich keine kurzen Kreise
• Wahle p “groß” ⇒ wahrscheinlich nur kleine stabile Mengen
Problematik:
p kann i.A. nicht so gewahlt werden, dass beide Bedingungen erfullt sind.
Ausweg:
• Beweise Existenz eines Hilfsgraphen
• Modifiziere diesen Hilfsgraphen
14
Brainstorming
Betrachte Zufallsgraphen mit Kantenwahrscheinlichkeit p:
• Wahle p “klein” ⇒ wahrscheinlich keine kurzen Kreise
• Wahle p “groß” ⇒ wahrscheinlich nur kleine stabile Mengen
Problematik:
p kann i.A. nicht so gewahlt werden, dass beide Bedingungen erfullt sind.
Ausweg:
• Beweise Existenz eines Hilfsgraphen
• Modifiziere diesen Hilfsgraphen
15
Aufbau des Beweises
Teil I:
Wahrscheinlichkeit, dass ein Graph mindestens n2 Kreise der Lange ≤ l besitzt
Teil II:
Wahrscheinlichkeit, dass ein Graph eine stabile Menge S besitzt mit |S| ≥ a
Teil III:
Abschluss des Beweises
16
Aufbau des Beweises
Teil I:
Wahrscheinlichkeit, dass ein Graph mindestens n2 Kreise der Lange ≤ l besitzt
Teil II:
Wahrscheinlichkeit, dass ein Graph eine stabile Menge S besitzt mit |S| ≥ a
Teil III:
Abschluss des Beweises
17
Aufbau des Beweises
Teil I:
Wahrscheinlichkeit, dass ein Graph mindestens n2 Kreise der Lange ≤ l besitzt
Teil II:
Wahrscheinlichkeit, dass ein Graph eine stabile Menge S besitzt mit |S| ≥ a
Teil III:
Abschluss des Beweises
18
I. Erwartungswert der Anzahl der Kreise mit Lange ≤ l
Sei n die Anzahl der Knoten und p := n− ll+1 die Wahrscheinlichkeit fur eine Kante.
Dann gilt:
E[X ] =∑l
i=3
(
ni
)
i! · pi =∑l
i=3n!
(n−i)!·ni ·n
il+1
2i ≤∑l
i=3n
il+1
2i ≤ lnl
l+1
(
ni
)
: Wahl der i Knoten
i! : Anordnen der i Knoten
pi : Wahrscheinlichkeit, dass alle Kanten auftreten1i
: Mehrfachzahlung auf Grund der Startknoten12
: Mehrfachzahlung auf Grund der Orientierung
19
I. Erwartungswert der Anzahl der Kreise mit Lange ≤ l
Sei n die Anzahl der Knoten und p := n− ll+1 die Wahrscheinlichkeit fur eine Kante.
Dann gilt:
E[X ] =∑l
i=3
(
ni
)
i!2i · p
i =∑l
i=3n!
(n−i)!·ni ·n
il+1
2i ≤∑l
i=3n
il+1
2i ≤ lnl
l+1
(
ni
)
: Wahl der i Knoten
i! : Anordnen der i Knoten
pi : Wahrscheinlichkeit, dass alle Kanten auftreten1i
: Mehrfachzahlung auf Grund der Startknoten12
: Mehrfachzahlung auf Grund der Orientierung
20
I. Erwartungswert der Anzahl der Kreise mit Lange ≤ l
Sei n die Anzahl der Knoten und p := n− ll+1 die Wahrscheinlichkeit fur eine Kante.
Dann gilt:
E[X ] =∑l
i=3
(
ni
)
i!2i · p
i =∑l
i=3n!
(n−i)!·ni ·n
il+1
2i ≤∑l
i=3n
il+1
2i ≤ lnl
l+1
(
ni
)
: Wahl der i Knoten
i! : Anordnen der i Knoten
pi : Wahrscheinlichkeit, dass alle Kanten auftreten1i
: Mehrfachzahlung auf Grund der Startknoten12
: Mehrfachzahlung auf Grund der Orientierung
21
I. Erwartungswert der Anzahl der Kreise mit Lange ≤ l
Sei n die Anzahl der Knoten und p := n− ll+1 die Wahrscheinlichkeit fur eine Kante.
Dann gilt:
E[X ] =∑l
i=3
(
ni
)
i!2i · p
i =∑l
i=3n!
(n−i)!·ni ·n
il+1
2i ≤∑l
i=3n
il+1
2i ≤ lnl
l+1
(
ni
)
: Wahl der i Knoten
i! : Anordnen der i Knoten
pi : Wahrscheinlichkeit, dass alle Kanten auftreten1i
: Mehrfachzahlung auf Grund der Startknoten12
: Mehrfachzahlung auf Grund der Orientierung
22
I. Erwartungswert der Anzahl der Kreise mit Lange ≤ l
Sei n die Anzahl der Knoten und p := n− ll+1 die Wahrscheinlichkeit fur eine Kante.
Dann gilt:
E[X ] =∑l
i=3
(
ni
)
i!2i · p
i =∑l
i=3n!
(n−i)!·ni ·n
il+1
2i ≤∑l
i=3n
il+1
2i ≤ lnl
l+1
(
ni
)
: Wahl der i Knoten
i! : Anordnen der i Knoten
pi : Wahrscheinlichkeit, dass alle Kanten auftreten1i
: Mehrfachzahlung auf Grund der Startknoten12
: Mehrfachzahlung auf Grund der Orientierung
23
I. Eine Abschatzung
Mit Markovs Ungleichung
P[|X| ≥ τ ] ≤E[|X|m]
τm
fur τ = n2 und m = 1 folgt
P[X ≥n
2] ≤ 2ln
ll+1−1 = 2ln− 1
l+1
Insbesondere gilt fur ausreichend großes n
P[X ≥n
2] <
1
2
24
I. Eine Abschatzung
Mit Markovs Ungleichung
P[|X| ≥ τ ] ≤E[|X|m]
τm
fur τ = n2 und m = 1 folgt
P[X ≥n
2] ≤ 2ln
ll+1−1 = 2ln− 1
l+1
Insbesondere gilt fur ausreichend großes n
P[X ≥n
2] <
1
2
25
I. Eine Abschatzung
Mit Markovs Ungleichung
P[|X| ≥ τ ] ≤E[|X|m]
τm
fur τ = n2 und m = 1 folgt
P[X ≥n
2] ≤ 2ln
ll+1−1 = 2ln− 1
l+1
Insbesondere gilt fur ausreichend großes n
P[X ≥n
2] <
1
2
26
II. Stabile Mengen
• a := d3pln ne + 1
• Wahrscheinlichkeit, dass eine Menge mit a Knoten stabil ist: (1 − p)(a2)
Zwei Voruberlegungen:
1 + x ≤ ex ⇒(
na
)
· (1 − p)(a2) ≤ na · (e−p)
a(a−1)2
p(a − 1) ≥ p · 3pln(n) = 3 ln(n) ⇒ n3 = e3 ln(n) ≤ ep(a−1) ⇒ ne−pa−1
2 ≤ n−12
Somit:
P[α(Gn,p) ≥ a] ≤(
na
)
(1 − p)(a2) ≤ (ne−pa−1
2 )a ≤ n−a2 ,
Es gilt also fur ausreichend großes n:
P[α(Gn,p) ≥ a] <1
2
27
II. Stabile Mengen
• a := d3pln ne + 1
• Wahrscheinlichkeit, dass eine Menge mit a Knoten stabil ist: (1 − p)(a2)
Zwei Voruberlegungen:
1 + x ≤ ex ⇒(
na
)
· (1 − p)(a2) ≤ na · (e−p)
a(a−1)2
p(a − 1) ≥ p · 3pln(n) = 3 ln(n) ⇒ n3 = e3 ln(n) ≤ ep(a−1) ⇒ ne−pa−1
2 ≤ n−12
Somit:
P[α(Gn,p) ≥ a] ≤(
na
)
(1 − p)(a2) ≤ (ne−pa−1
2 )a ≤ n−a2 ,
Es gilt also fur ausreichend großes n:
P[α(Gn,p) ≥ a] <1
2
28
II. Stabile Mengen
• a := d3pln ne + 1
• Wahrscheinlichkeit, dass eine Menge mit a Knoten stabil ist: (1 − p)(a2)
Zwei Voruberlegungen:
1 + x ≤ ex ⇒(
na
)
· (1 − p)(a2) ≤ na · (e−p)
a(a−1)2
p(a − 1) ≥ p · 3pln(n) = 3 ln(n) ⇒ n3 = e3 ln(n) ≤ ep(a−1) ⇒ ne−pa−1
2 ≤ n−12
Somit:
P[α(Gn,p) ≥ a] ≤(
na
)
(1 − p)(a2) ≤ (ne−pa−1
2 )a ≤ n−a2 ,
Es gilt also fur ausreichend großes n:
P[α(Gn,p) ≥ a] <1
2
29
II. Stabile Mengen
• a := d3pln ne + 1
• Wahrscheinlichkeit, dass eine Menge mit a Knoten stabil ist: (1 − p)(a2)
Zwei Voruberlegungen:
1 + x ≤ ex ⇒(
na
)
· (1 − p)(a2) ≤ na · (e−p)
a(a−1)2
p(a − 1) ≥ p · 3pln(n) = 3 ln(n) ⇒ n3 = e3 ln(n) ≤ ep(a−1) ⇒ ne−pa−1
2 ≤ n−12
Somit:
P[α(Gn,p) ≥ a] ≤(
na
)
(1 − p)(a2) ≤ (ne−pa−1
2 )a ≤ n−a2 ,
Es gilt also fur ausreichend großes n:
P[α(Gn,p) ≥ a] <1
2
30
II. Stabile Mengen
• a := d3pln ne + 1
• Wahrscheinlichkeit, dass eine Menge mit a Knoten stabil ist: (1 − p)(a2)
Zwei Voruberlegungen:
1 + x ≤ ex ⇒(
na
)
· (1 − p)(a2) ≤ na · (e−p)
a(a−1)2
p(a − 1) ≥ p · 3pln(n) = 3 ln(n) ⇒ n3 = e3 ln(n) ≤ ep(a−1) ⇒ ne−pa−1
2 ≤ n−12
Somit:
P[α(Gn,p) ≥ a] ≤(
na
)
(1 − p)(a2) ≤ (ne−pa−1
2 )a ≤ n−a2 ,
Es gilt also fur ausreichend großes n:
P[α(Gn,p) ≥ a] <1
2
31
II. Stabile Mengen
• a := d3pln ne + 1
• Wahrscheinlichkeit, dass eine Menge mit a Knoten stabil ist: (1 − p)(a2)
Zwei Voruberlegungen:
1 + x ≤ ex ⇒(
na
)
· (1 − p)(a2) ≤ na · (e−p)
a(a−1)2
p(a − 1) ≥ p · 3pln(n) = 3 ln(n) ⇒ n3 = e3 ln(n) ≤ ep(a−1) ⇒ ne−pa−1
2 ≤ n−12
Somit:
P[α(Gn,p) ≥ a] ≤(
na
)
(1 − p)(a2) ≤ (ne−pa−1
2 )a ≤ n−a2 ,
Es gilt also fur ausreichend großes n:
P[α(Gn,p) ≥ a] <1
2
32
II. Stabile Mengen
• a := d3pln ne + 1
• Wahrscheinlichkeit, dass eine Menge mit a Knoten stabil ist: (1 − p)(a2)
Zwei Voruberlegungen:
1 + x ≤ ex ⇒(
na
)
· (1 − p)(a2) ≤ na · (e−p)
a(a−1)2
p(a − 1) ≥ p · 3pln(n) = 3 ln(n) ⇒ n3 = e3 ln(n) ≤ ep(a−1) ⇒ ne−pa−1
2 ≤ n−12
Somit:
P[α(Gn,p) ≥ a] ≤(
na
)
(1 − p)(a2) ≤ (ne−pa−1
2 )a ≤ n−a2 ,
Es gilt also fur ausreichend großes n:
P[α(Gn,p) ≥ a] <1
2
33
III. Folgerung
Fur ausreichend großes n gilt also:
P[α(Gn,p) ≥ a] <1
2, P[X ≥
n
2] <
1
2
⇒ ∃ Graph mit n Knoten:
• α(G) ≤ 3nl
l+1 ln n + 1
• enthalt weniger als n2
Kreise der Lange ≤ l
34
III. Folgerung
Fur ausreichend großes n gilt also:
P[α(Gn,p) ≥ a] <1
2, P[X ≥
n
2] <
1
2
⇒ ∃ Graph mit n Knoten:
• α(G) ≤ 3nl
l+1 ln n + 1
• enthalt weniger als n2
Kreise der Lange ≤ l
35
III. Abschluss des Beweises
Sei G′ Graph, der dadurch entsteht, dass man von jedem Kreis von G einen Knoten-punkt entfernt.
• |V (G′)| ≥ n2
• α(G′) ≤ α(G)
Aus den Voruberlegungen: χ(G′) ≥ |V (G′)|α(G)
χ(G′) ≥n2
3nl
l+1 ln n + 1=
n1
l+1
6 ln n + 2
nl
l+1
>n
1l+1
6 ln n + 2
n ausreichend groß ⇒ n1
l+1
6 lnn+2 > k �
36
III. Abschluss des Beweises
Sei G′ Graph, der dadurch entsteht, dass man von jedem Kreis von G einen Knoten-punkt entfernt.
• |V (G′)| ≥ n2
• α(G′) ≤ α(G)
Aus den Voruberlegungen: χ(G′) ≥ |V (G′)|α(G)
χ(G′) ≥n2
3nl
l+1 ln n + 1=
n1
l+1
6 ln n + 2
nl
l+1
>n
1l+1
6 ln n + 2
n ausreichend groß ⇒ n1
l+1
6 lnn+2 > k �
37
III. Abschluss des Beweises
Sei G′ Graph, der dadurch entsteht, dass man von jedem Kreis von G einen Knoten-punkt entfernt.
• |V (G′)| ≥ n2
• α(G′) ≤ α(G)
Aus den Voruberlegungen: χ(G′) ≥ |V (G′)|α(G)
χ(G′) ≥n2
3nl
l+1 ln n + 1=
n1
l+1
6 ln n + 2
nl
l+1
>n
1l+1
6 ln n + 2
n ausreichend groß ⇒ n1
l+1
6 lnn+2 > k �
38
III. Abschluss des Beweises
Sei G′ Graph, der dadurch entsteht, dass man von jedem Kreis von G einen Knoten-punkt entfernt.
• |V (G′)| ≥ n2
• α(G′) ≤ α(G)
Aus den Voruberlegungen: χ(G′) ≥ |V (G′)|α(G)
χ(G′) ≥n2
3nl
l+1 ln n + 1=
n1
l+1
6 ln n + 2
nl
l+1
>n
1l+1
6 ln n + 2
n ausreichend groß ⇒ n1
l+1
6 lnn+2 > k �
39
III. Abschluss des Beweises
Sei G′ Graph, der dadurch entsteht, dass man von jedem Kreis von G einen Knoten-punkt entfernt.
• |V (G′)| ≥ n2
• α(G′) ≤ α(G)
Aus den Voruberlegungen: χ(G′) ≥ |V (G′)|α(G)
χ(G′) ≥n2
3nl
l+1 ln n + 1=
n1
l+1
6 ln n + 2
nl
l+1
>n
1l+1
6 ln n + 2
n ausreichend groß ⇒ n1
l+1
6 lnn+2 > k �
40
III. Abschluss des Beweises
Sei G′ Graph, der dadurch entsteht, dass man von jedem Kreis von G einen Knoten-punkt entfernt.
• |V (G′)| ≥ n2
• α(G′) ≤ α(G)
Aus den Voruberlegungen: χ(G′) ≥ |V (G′)|α(G)
χ(G′) ≥n2
3nl
l+1 ln n + 1=
n1
l+1
6 ln n + 2
nl
l+1
>n
1l+1
6 ln n + 2
n ausreichend groß ⇒ n1
l+1
6 lnn+2 > k �
41
III. Abschluss des Beweises
Sei G′ Graph, der dadurch entsteht, dass man von jedem Kreis von G einen Knoten-punkt entfernt.
• |V (G′)| ≥ n2
• α(G′) ≤ α(G)
Aus den Voruberlegungen: χ(G′) ≥ |V (G′)|α(G)
χ(G′) ≥n2
3nl
l+1 ln n + 1=
n1
l+1
6 ln n + 2
nl
l+1
>n
1l+1
6 ln n + 2
n ausreichend groß ⇒ n1
l+1
6 lnn+2 > k �
42
III. Abschluss des Beweises
Sei G′ Graph, der dadurch entsteht, dass man von jedem Kreis von G einen Knoten-punkt entfernt.
• |V (G′)| ≥ n2
• α(G′) ≤ α(G)
Aus den Voruberlegungen: χ(G′) ≥ |V (G′)|α(G)
χ(G′) ≥n2
3nl
l+1 ln n + 1=
n1
l+1
6 ln n + 2
nl
l+1
>n
1l+1
6 ln n + 2
n ausreichend groß ⇒ n1
l+1
6 lnn+2 > k �
43
Recommended