Barion Pixel Páros gráf | mateking
 

Páros gráf

Egy $G$ gráfot páros gráfnak nevezünk, ha csúcsainak a $V(G)$ halmaza felbontható az $A$ és $B$ diszjunkt részhalmazokra, úgy hogy $A$-n és $B$-n belül nem vezetnek élek.

A páros gráfok kromatikus száma 2, élkromatikus számukra pedig König Dénesnek van egy remek tétele:

Ha $G$ páros gráf, akkor $ \chi_e(G) = \Delta(G) $

Egy gráfot páros gráfnak nevezünk, ha csúcsainak halmaza felbontható két diszjunkt részhalmazra, úgy hogy a két halmazon belül nem vezetnek élek, csak köztük.