noncolorable

Noncolorable is a term used primarily in graph theory to describe a structure that cannot be colored with a given number of colors under standard coloring rules. A graph is k-colorable if its vertices can be assigned at most k colors so that no adjacent vertices share a color. If no such coloring exists, the graph is non-k-colorable. The chromatic number χ(G) of a graph G is the smallest k for which G is k-colorable; equivalently, G is non-k-colorable when χ(G) > k.

Examples help illustrate the concept. For a cycle C_n, χ(C_n) equals 2 if n is even, and 3 if n is odd. Therefore C_3 and C_5 are not 2-colorable. The complete graph K_m has χ(K_m) = m, so K_4 is non-3-colorable. These simple cases show how noncolorability arises from the structure of the graph.

Extensions of the idea include list coloring, where each vertex has a list of allowable colors. A graph can be k-colorable in the general sense but non-colorable from a given list assignment, illustrating that added constraints can create noncolorability.

Computationally, determining whether a general graph is k-colorable is NP-complete for k ≥ 3, while deciding 2-colorability is polynomial-time (equivalent to testing bipartiteness).

In geometric and plane coloring contexts, noncolorable concepts appear in problems about coloring the plane to avoid certain configurations, such as unit-distance graphs that force more colors. These topics connect noncolorability to broader questions in combinatorial geometry and Ramsey-type problems.