Le graphe à une seule couleur près

Contexte

Un graphe est dit "biparti" si on peut colorier tous ses sommets avec exactement deux couleurs, de telle sorte qu'aucune arête ne relie deux sommets de la même couleur.

Mission

Quel algorithme de parcours de graphe (deux mots ou son acronyme à 3 lettres) est le plus naturel pour tester si un graphe est biparti, en coloriant les sommets au fur et à mesure qu'on les découvre, niveau par niveau ?