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) $
© Minden jog fenntartva!
Az oldalon található tartalmak részének vagy egészének másolása, elektronikus úton történő tárolása vagy továbbítása, harmadik fél számára nyújtott oktatási célra való hasznosítása kizárólag az üzemeltető írásos engedélyével történhet. Ennek hiányában a felsorolt tevékenységek űzése büntetést von maga után!
