WYKŁAD 6. 

Kolorowanie krawędzi

Przykład:

 W turnieju szachowym, w 

którym biorą udział szachistki 
A,B,C,D,E,F, pozostały do 
rozegrania mecze pomiędzy 
parami  AE, AF, BC, BD, BF, CD, 
DE, EF. W ilu rundach można 
zakończyć ten turniej?

 

 

Ilustracja

A

B

C

D

E

F

 

 

Indeks chromatyczny

• Zbiór niezależny  skojarzenie
• Liczba chromatyczna χ  

indeks 

chromatyczny χ’

• Indeks chromatyczny

 to najmniejsza 

liczba kolorów, którymi można 
pomalować krawędzie grafu tak, by 
krawędzie o wspólnym końcu miały 
różne kolory.

 

 

Inaczej

• χ’(G) 

to minimalna liczba skojarzeń, 

którymi można pokryć zbiór E(G).

• χ’(G)= χ(L(G))

χ’=3

)

(

)

(

'

G

G







χ’=4

 

 

Tw. Vizinga

Tw. (Vizing,1964) 

Dla każdego grafu G

 

1

)

(

)

(

'

)

(











G

G

G



Mówimy, że G jest 

k-krawędziowo-

kolorowalny, 

gdy

k

G 

)

(

'



 

 

Lemat

Lemat. 

Dane są: liczba naturalna k, graf G i 

wierzchołek v tego grafu. Jeśli 

   

(i) wierzchołek v oraz wszyscy jego 
sąsiedzi mają stopień nie większy niż k,

   (ii) co najwyżej jeden sąsiad v ma stopień 

równy k, oraz

   

(iii) graf G-v jest k-krawędziowo-
kolorowalny,

to G jest k-krawędziowo-kolorowalny.

 

 

Dowód Tw. Vizinga

• Indukcja względem n=|V(G)|. 
• Prawda dla n=1.
• Załóżmy, że to prawda dla n i weźmy 

dowolny graf G na n+1 wierzchołkach.

• Niech v będzie dowolnym wierzchołkiem G.

• Na podstawie zał. ind. G-v jest (Δ+1)-

krawędziowo-kolorowalny

.

•  

Na podstawie Lematu z k= Δ+1, G jest 

(Δ+1)-krawędziowo-kolorowalny

. 

 

 

Dowód Lematu

• Indukcja względem k; k=0,1 – 

trywialne.

• Załóżmy prawdziwość dla k-1.

• Dodając, jeśli trzeba, wierzchołki 

wiszące, można założyć, że jeden 
sąsiad v ma stopień k, a pozostali 
stopień k-1.

 

 

Ilustracja k=4

v

 

 

Dowód Lematu – c.d.

• c: E(G-v) 



 {1,...,k} 

• N_i – zbiór sąsiadów v bez koloru i, i=1,...,k

FAKT

: 

Istnieje c takie, że |N_l|=1 dla 

pewnego l.

• Przyjmijmy b.s.o., że |N_k|=1, N_k={u}.

 

• G’=G bez krawędzi uv i bez krawędzi koloru 

k

• G’ spełnia założenia Lematu z v i k-1, więc z 

zał. ind. jest (k-1)-krawędziowo-kolorowalny.

• G=G’ plus skojarzenie, więc jest                    

   k-krawędziowo-kolorowalny.

 

 

 

Ilustracja k=4

v

u

 

 

Ilustracja k=4 – c.d.

v

u

 

 

Dowód Faktu

FAKT

: 

Istnieje c takie, że |N_l|=1 dla pewnego l.

Dowód: 

Wybierzmy c tak, by zminimalizować

2

1

|

|

i

k

i

N





Zauważmy, że

1

2

1

)

(

2

|

|

1













k

v

d

N

k

i

i

Stąd, istnieją i i j: |N_i|<2, |N_j| -- 

nieparzyste.

 

 

Dowód Faktu – c.d.

• Przypuśćmy, że żadne |N_l| nie jest równe 1.

• Wtedy |N_i|=0, a |N_j|>2.

• Spójrzmy na maksymalną ścieżkę 

naprzemienną P w kolorach i i j, zaczynającą 

się w N_j.

• Jeśli P kończy się sąsiadem v, to musi on 

należeć do N_j. 

• Tak czy owak, zamieniając kolory i i j na P, 

otrzymujemy kolorowanie c’, w którym 1 lub 

2 wierzchołki ,,przeszły” z N_j do N_i; zatem







2

2

|

|

|'

|

i

i

N

N

-- 

sprzeczność.

 

 

Ilustracja dowodu Faktu

v

N_j

N_i=pusty

P

|

N’_i

|=2, |

N’_j

|=1: 4+1<0+9

 

 

Dwa typy grafów

Typ I : 

χ’(G) =Δ(G): 

np.

 

P_n, C_{2n}, K_{2n}

Typ I I:  

χ’(G) =Δ(G)+1: 

np. 

 

C_{2n+1}, 

K_{2n+1}

Grafy dwudzielne? Graf Petersena ???

II

 

 

Grafy dwudzielne są typu 

I (König 1916)

• Każdy dwudzielny graf G jest podgrafem 

Δ(G)-regularnego dwudzielnego grafu H

 

(ćwiczenia).

• H posiada, zgodnie z Wnioskiem z Tw. 

Halla, Δ(G) rozłącznych skojarzeń 

doskonałych, które pokrywają cały zbiór 

E(H) 

(ćwiczenia).

• Zatem zbiór E(G) jest pokryty przez Δ(G) 

rozłącznych skojarzeń, tzn. χ’(G) =Δ(G).

 

 

Faktoryzacja

• Jeśli regularny graf G jest typu I, tzn. 

χ’(G) 

=Δ(G), 

to mówimy, że ma 

faktoryzację, 

zwaną też 

1-faktoryzacją.

• Krawędzie tego samego koloru tworzą 

skojarzenia doskonałe, zwane 

1-faktorami

.

• Dwudzielne grafy regularne są 

faktoryzowalne, grafy pełne K_{2n} też.

• Grafy pełne K_{2n+1} nie mogą mieć 

faktoryzacji.

• Graf Petersena???

 

 

Faktoryzacja -- ilustracja

K_6

 

 

2-faktoryzacja

• 2-faktor

 w grafie G to jego 2-

regularny, rozpięty  podgraf H, 
tzn. H jest sumą cykli i V(H)=V(G).

• 2-faktoryzacją

 grafu 2k-

regularnego G nazywamy podział 
E(G) na k rozłącznych 2-faktorów.

• 2-faktoryzacja ZAWSZE istnieje !!!

 

 

2-faktoryzacja -- ilustracja

 

 

Tw. Petersena o 2-

faktoryzacji

Tw

. Każdy 2k-regularny graf ma 2-

faktoryzację.

Lemat.

 Jeśli wszystkie stopnie 

wierzchołków w G są parzyste, to 
krawędzie w G można zorientować 
(skierować, ,,ostrzałkować”) tak, by do 
każdego wierzchołka wchodziło tyle samo 
strzałek co wychodziło.

 

 

Dowód Tw. Petersena 

Dowód Tw.: 

Rozważmy pomocniczy 

graf 2-dzielny D z A=V(G) do 

B=V(G), gdzie krawędź biegnie z a 

do b wgdy gdy ab jest krawędzią w G 

skierowaną od a do b.

• Graf D jest k-regularny, więc ma 
1-faktoryzację.

• Każdy 1-faktor w D odpowiada 2-

faktorowi w G.

 

 

Ilustracja dowodu Tw. 

Petersena

1

2

3

4

5

1

2

3

4

5

1

2

3

4

5

 

 

Dowód Lematu

Lemat.

 Jeśli wszystkie stopnie wierzchołków w G są 

parzyste, to krawędzie w G można zorientować 

(skierować, ,,ostrzałkować”) tak, by do każdego 

wierzchołka wchodziło tyle samo strzałek co 

wychodziło.

Dowód: 

Indukcja względem e(G) (e=0 

prawda).

Dla e>0, G musi zawierać cykl C. 

Zastosujmy 

założenie indukcyjne do G’=(V,E-C)

 i 

dodajmy cykl C skierowany cyklicznie. 