Dukolora grafeo

eta|plena dukolora grafeo kun m = 5 kaj n = 3

En grafeoteorio, dukolora grafeo (aŭ duparta grafeo) estas grafeo kies verticojn oni povas dividi en du disajn arojn  kaj , en kiu ĉiu eĝo ligas verticon en  al vertico en . Verticaro  kaj  ofte nomiĝas la partoj de la grafeo. Ekvivalente, dukolora grafeo estas grafeo sen nepara ciklo..

La du partojn ,  oni povas pripensi kiel kolorado de la grafeo per du koloroj: ekzemple verticoj en  estu bluaj, kaj verticoj en  verdaj. Do la randoj de ĉiu eĝo havas malsamajn kolorojn., p. 7. Kontraste, ĉi tia kolorado ne eblas en ne-dukolora grafeo, ekzemple unu triangulo.

Oni ofte skribas  por signifi dukolora grafeo kun partoj  kun , kaj  signas la eĝaro. Se dukolora grafeo ne estas konekteca, ĝi eble havas plurajn dukoloradojn;. tiel,   povas signi unu el la dukoloradoj utila por la nuna problemo. Se , t.e. la du partoj enhavas same da elementoj,  nomiĝas ekvilibra dukolora grafeo. Se ĉiuj verticoj en ambaŭ partoj havas saman gradon,  nomiĝas duregula.

 Referencoj 

Kategorio:Grafeteorio