Bipartitni graf

Bipartitni graf, vrsta grafa u teoriji grafova. Za nj vrijedi $G=(V,E)$ i za čiji se skup vrhova $V$ može podijeliti u dva disjunktna skupa $A$ i $B$ sa svojstvom da svaki brid u $E$ povezuje jedan vrh iz $A$ i jedan vrh iz $B$. Kod bipartitnog grafa kromatski broj je 2. Ciklički graf se može obojati u dvije boje na samo dva načina.