3colorable

3colorable refers to a property of a graph in graph theory: a graph is 3colorable if its vertices can be assigned one of three colors so that no adjacent vertices share the same color. Equivalently, the graph’s chromatic number χ(G) is at most 3, meaning three colors suffice for a proper coloring.

Examples illustrate the concept. A triangle K3 is 3colorable and in fact requires exactly three colors. A cycle with five vertices, C5, is also 3colorable. A path or any tree is 2-colorable, hence also 3colorable. A complete graph on four vertices, K4, is not 3colorable since it requires four colors.

Computationally, deciding whether an arbitrary graph is 3colorable is NP-complete. This means there is no known polynomial-time algorithm that solves all instances unless P = NP. For special graph families, the problem can be easier: for example, bipartite graphs and trees are 2-colorable and hence trivially 3colorable. Despite these exceptions, many natural graph classes retain 3colorability as a difficult decision problem. Practical approaches include backtracking, constraint programming, and heuristic local-search methods, often combined with problem-specific structure or reductions from related combinatorial problems.

Related concepts include graph coloring in general and the study of χ(G) for varying k, known as k-colorability. The 3-colorability problem has implications in areas such as scheduling, register allocation in compilers, and map coloring, where a small fixed number of colors is desirable.