threecolorable

A graph is threecolorable if its vertices can be colored using at most three colors such that no two adjacent vertices share the same color. This is a specific case of the general graph coloring problem, which asks for the minimum number of colors needed to color a graph. The problem of determining if a graph is threecolorable is NP-complete. This means that for large graphs, there is no known efficient algorithm to determine threecolorability.

Every graph that is planar and has no triangles (i.e., is triangle-free) can be colored with at most three colors, a result related to the Four Color Theorem which states all planar graphs are 4-colorable. However, not all planar graphs are threecolorable. For example, the complete graph K4, which consists of four vertices all connected to each other, requires four colors and is therefore not threecolorable. Non-planar graphs can also be threecolorable, such as bipartite graphs, which can always be colored with two colors and thus are also threecolorable.

The concept of threecolorability is important in various fields, including computer science for scheduling and resource allocation, and in mathematics for understanding graph structures. Algorithms exist to attempt to three-color a graph, but their efficiency can vary significantly depending on the graph's properties.