3colorability

3colorability, in graph theory, refers to the problem of determining whether the vertices of a given undirected graph can be colored with at most three colors such that no adjacent vertices share a color. A successful coloring in this sense is called a 3-coloring.

This problem is a special case of graph coloring, where the goal is to minimize the number of colors needed to color a graph so that adjacent vertices have different colors. A graph is 3-colorable precisely when its chromatic number χ(G) is at most 3. For many common graph classes, the question becomes easier or even trivial: cycles of even length are 2-colorable, odd cycles require three colors, trees are 2-colorable, and bipartite graphs are 2-colorable.

Computationally, 3colorability is NP-complete for general graphs, meaning there is no known polynomial-time algorithm to decide it for all graphs unless P = NP. The problem remains NP-complete for several restricted classes, including planar graphs. Because 3-colorability sits between 2-colorability (bipartiteness) and general coloring, it is often used in complexity and reduction studies. There are polynomial-time algorithms for certain graph families; for example, in chordal and other perfect graphs, the chromatic number equals the clique number, enabling efficient decision of 3-colorability in those cases.

In practice, approaches to 3colorability include backtracking and constraint programming, SAT formulations, and fixed-parameter algorithms parameterized by treewidth. While planarity does not simplify the problem to a tractable one, understanding 3colorability helps illuminate the broader landscape of graph coloring and its computational boundaries.