2colorable

2colorable is a term used in graph theory to describe graphs that can be colored with two colors so that adjacent vertices have different colors. A graph with this property is called 2-colorable or bipartite. Equivalently, the vertex set can be divided into two independent sets, so no edge has both endpoints in the same set.

A key characterization is that a graph is 2-colorable if and only if it contains no odd cycles. This means that every connected component of a 2-colorable graph must be bipartite; a graph is 2-colorable exactly when all of its connected components are bipartite. If any component contains an odd cycle, two colors are insufficient to avoid adjacent vertices sharing a color.

A standard method to determine 2-colorability is a BFS or DFS that attempts to assign colors while traversing the graph. Start with an uncolored vertex and assign it one color, then alternating colors along all edges. If a conflict arises (an edge connects two vertices of the same color), the graph is not 2-colorable. This algorithm runs in linear time with respect to the number of vertices and edges, O(V+E), and can also produce a valid 2-coloring when possible.

Examples illustrate the concept: a path graph and any even cycle are 2-colorable, while a triangle (a 3-cycle) is not. In terms of coloring, 2-colorable graphs have chromatic number 2 (though edgeless graphs are also 1-colorable).

Applications of 2-colorability include scheduling with two time slots, parity constraint systems, and recognizing bipartite structures in networks and matching problems.