Bipartitni graf

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