Graph coloring assigns colors to vertices while preventing adjacent vertices from receiving the same color. With two colors, this condition is equivalent to bipartiteness: the colors identify the graph’s two partitions. section 15.2.3
A practical two-coloring algorithm modifies breadth-first search. Color a starting vertex red, visit its neighbors, and assign each the opposite color. If an edge joins vertices with the same color, reject the graph as non-bipartite; otherwise, the color groups form its partitions. section 15.2.3
Testing a graph in planarity analysis
When checking whether a graph matches K3,3, first verify six vertices and nine edges, then use two-coloring to confirm bipartiteness and verify that both color classes contain three vertices. section 15.2.3
