twocoloring

Twocoloring, or two-coloring, is a problem in graph theory that asks whether the vertices of a graph can be colored with two colors so that no adjacent vertices share a color. If such a coloring exists, the graph is called bipartite; the coloring partitions the vertex set into two independent sets.

A graph is 2-colorable if and only if it contains no odd cycle; equivalently, every connected component is bipartite. For a connected bipartite graph with at least one edge, there are exactly two proper 2-colorings (the two color classes can be swapped). In a graph with multiple components, colorings of each component can be combined independently. Edge cases include edgeless graphs, which are trivially 2-colorable; the chromatic number is 0 for an empty graph, 1 for a graph with isolated vertices, and 2 for any graph with at least one edge that is bipartite.

Algorithmically, twocolorability can be decided in linear time using breadth-first search (BFS) or depth-first search (DFS). Starting with an uncolored vertex, assign a color and propagate alternately along edges. If a neighbor already has the same color, the graph is not 2-colorable. This approach also provides a practical bipartiteness test and underpins many related graph algorithms.

Applications and related concepts: Two-coloring is foundational in the study of bipartite graphs, with implications for matching theory, scheduling, and resource allocation problems. It serves as a common introductory example of colorability and is often used as a subroutine in more complex graph algorithms.