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) $