Vertex colorings and chromatic polynomials

For a finite simple graph, a proper $k$-coloring is a function from vertices to $k$ named colors with different values at adjacent endpoints. Each color class is an independent set, containing no edge. The chromatic number $\chi(G)$ is the least usable palette size for a nonempty graph. A clique of size $r$ forces at least $r$ colors because every pair conflicts, but the largest clique does not always determine the answer: an odd cycle needs three colors despite having no triangle.

A greedy coloring examines vertices in a chosen order and gives each the first color absent from its already-colored neighbors. With maximum degree $\Delta$, at most $\Delta$ colors are forbidden at any step, proving an upper bound of $\Delta+1$. A particular order may use fewer colors, but an arbitrary greedy result is not necessarily optimal. To prove the exact chromatic number, pair a lower obstruction, such as a clique or an odd cycle, with an explicit coloring using that many colors.

Let $P_G(k)$ be the number of proper colorings using colors chosen from a named palette of size $k$; not every available color must appear. For an edgeless graph on $n$ vertices, choices are independent, giving $k^n$. For a tree on $n\ge1$ vertices, choose a root color in $k$ ways, then each other vertex has $k-1$ choices distinct from its parent. The tree has no extra edges imposing further restrictions, so the product is $k(k-1)^{n-1}$.

For an edge $e=uv$, count proper colorings of the graph with that edge deleted. They split into those with different colors at u and v, which are exactly the proper colorings of the original graph, and those with equal colors, which correspond to colorings after contracting u and v to one vertex. Rearranging gives deletion–contraction. Parallel edges created by contraction impose duplicate inequality constraints and can be merged for this counting purpose. Repeating the recurrence proves that the count is a polynomial in k.

A graph is bipartite if and only if it has no odd cycle. One direction is immediate: a walk around a cycle alternates the two classes and can return to its starting class only after an even number of steps. Conversely, within each component choose a root and assign classes by even and odd distance from it. An edge joining vertices of the same parity would combine their root paths with that edge to give an odd closed walk, which contains an odd cycle after removing repetitions.

Thus a connected graph with at least one edge is two-colorable exactly when it is bipartite. This characterization is stronger than checking that no triangle occurs: a five-cycle is triangle-free but not bipartite. In scheduling, pairwise conflict graphs also have limits. A constraint saying three tasks cannot all share one slot, while any pair may, is not represented by ordinary edges. Modeling such higher-order restrictions requires different data rather than interpreting a proper graph coloring as a complete schedule certificate.