Chromatic number (χ(G))

For a nonempty finite simple graph $G$, the chromatic number $\chi (G)$ is the least positive integer $k$ for which $G$ has a proper vertex graph coloring with at most $k$ colours. To establish an exact chromatic number, give a colouring using that many colours and explain why fewer cannot suffice. A colouring alone gives only an upper bound.^[ref]

These small graphs show why the chromatic number measures more than the presence of triangles in a graph:

For a cycle graph of even length, alternating two colours closes consistently; for an odd cycle, it does not, and a third colour on the final vertex suffices. More generally, the two-colourability criterion for bipartite graphs says that $\chi (G)\le 2$ exactly when $G$ is a bipartite graph, and the odd-cycle characterization of bipartite graphs identifies the obstruction as an odd cycle. A nonempty graph with no edges has chromatic number one; a bipartite graph with at least one edge has chromatic number exactly two.

In the pairwise-conflict scheduling model of graph coloring, $\chi (G)$ is the least number of interchangeable slots needed. This turns a drawing into an optimization question: how many groups of compatible activities are unavoidable? Greedy coloring constructs a valid grouping quickly, but its number of colours can exceed the chromatic number.

This is the least number of colors needed to color all points of Euclidean space so that points at Euclidean distance one receive different colors. Any finite unit-distance graph embedded in the space gives a lower bound. If $p$ is prime, the characteristic vectors of all $(2p-1)$-subsets of $[4p-1]$, divided by $\sqrt{2p}$, give such a graph: its edges are exactly pairs intersecting in $p-1$ points. The prime-power modular intersection bound bounds an independent set by $\left(\genfrac{}{}{0ex}{}{4p-1}{p-1}\right)$, and hence gives $\chi ({\mathbb{R}}^{4p-1})\ge \left(\genfrac{}{}{0ex}{}{4p-1}{2p-1}\right)/\left(\genfrac{}{}{0ex}{}{4p-1}{p-1}\right)$.

A vertex $v$ is colour-critical if deleting it lowers the chromatic number by one. If $\chi (F)=r+1$ and $\chi (F-v)=r$, an embedding of $F-v$ into a complete $r$-partite graph inside one neighbourhood extends to an embedding of $F$. This supplies maximum-degree obstructions in extremal graph theory.

The Mycielski construction replaces a graph $G$ with a graph $\mu (G)$ having one shadow vertex for each original vertex and one further vertex adjacent to every shadow. It satisfiesand preserves triangle-freeness. Iterating it from the five-cycle gives triangle-free graphs of arbitrarily large chromatic number.

Here $G$ is a finite simple graph with at least one vertex; it need not have an edge. The Mycielskian separates two ways of needing many colours: a large clique forces distinct colours immediately, but a triangle-free graph can impose incompatible choices through its whole pattern of graph adjacency. The Mycielski construction increases that global constraint while preserving the absence of triangles in a graph.

Write the vertex set of $G$ as $\{v_1,\dots ,v_n\}$, with $n\ge 1$. Keep these vertices, add distinct Mycielski shadow vertices $u_1,\dots ,u_n$, and add a Mycielski apex $w$. The vertex set and complete list of edges areThere are no other edges: the Mycielski shadow vertices form an independent set, $w$ has no original vertex as a neighbour, and $u_i$ is not adjacent to $v_i$. Each Mycielski shadow vertex copies its original vertex's graph neighbourhood within the original vertex set, not its position in the drawing. This is the construction in the inspected research paper.^[ref]

For $n$ original vertices and $m$ original edges, direct counting gives $2n+1$ vertices and $3m+n$ edges. The original vertices induce a copy of $G$, so no original graph adjacency is lost. A drawing crossing is not an extra vertex.

Start with the complete graph $K_2$, whose only edge is $v_1{v}_2$, abbreviating $\{v_1,v_2\}$. Its Mycielskian has exactly the edges $v_1{v}_2,u_1{v}_2,u_2{v}_1,w{u}_1,w{u}_2$. Reading them as $v_1,v_2,u_1,w,u_2,v_1$ gives the cycle graph $C_5$. A proper vertex colouring gives $v_1,u_1$ colour 1, $v_2,u_2$ colour 2, and $w$ colour 3. Two colours cannot close an odd cycle, so its chromatic number is exactly three.

The Grötzsch graph is the Mycielskian of the five-vertex cycle graph. Take original edges $v_i{v}_{i+1}$, with indices interpreted modulo five; add $u_i{v}_{i-1},u_i{v}_{i+1}$ and $w{u}_i$ for every $i$. There are eleven vertices and twenty edges: five original, ten between originals and Mycielski shadow vertices, and five from the Mycielski apex.

Give $v_1,\dots ,v_5$ colours $(1,2,1,2,3)$, give each $u_i$ the colour of $v_i$, and give $w$ colour 4. This is a proper vertex colouring. The Mycielskian chromatic increase proves that three colours are impossible, so the chromatic number is exactly four. The Mycielskian triangle preservation proves that this is a triangle-free graph. In particular its clique number is only two, even though its chromatic number is four.

The Mycielski apex has an independent set as its graph neighbourhood, yet all three old colours are needed there in any three-colour proper vertex colouring of the subgraph obtained by deleting it. Thus a locally easy group of mutually nonadjacent neighbours can carry globally incompatible colour requirements. Absence of triangles in a graph alone cannot bound the chromatic number.

A Mycielski shadow vertex $u_i$ has graph neighbourhood $N_G(v_i)\cup \{w\}$ in $\mu (G)$. Its neighbours other than the Mycielski apex are original vertices. All Mycielski shadow vertices form an independent set.

The Mycielski apex is the added vertex adjacent to every Mycielski shadow vertex and to no original vertex. Its graph neighbourhood is precisely $\{u_1,\dots ,u_n\}$.

For a nonempty finite simple graph, the upper bound copies an optimal proper vertex colouring to its Mycielski shadow vertices and gives the Mycielski apex a fresh colour. For the lower bound, suppose $\mu (G)$ uses $k=\chi (G)$ colours, with $w$ coloured $k$. Shadows avoid $k$. Replace colour $k$ at each original $v_i$ by $u_i$'s colour. Changed originals form an independent set; unchanged neighbours differ because $u_i{v}_j$ is an edge. This proper vertex colouring of $G$ uses $k-1$ colours, contradicting its chromatic number.^[ref]

The nonempty condition means $V(G)\ne \varnothing$, not $E(G)\ne \varnothing$. An edgeless $n$-vertex graph with $n\ge 1$ has chromatic number one; its Mycielskian is a star graph on $w,u_1,\dots ,u_n$ together with $n$ isolated vertices, and needs two colours. If $G$ has no vertices, $\mu (G)$ is a single vertex, so the same formula also holds with the convention $\chi (G)=0$.

A finite simple graph $G$ is a triangle-free graph if and only if its Mycielskian is a triangle-free graph. No triangle in a graph can contain the Mycielski apex, whose neighbours are an independent set, or two Mycielski shadow vertices. A triangle in a graph containing one shadow $u_i$ and two originals $v_j,v_{\ell }$ requires all three original edges $v_i{v}_j,v_i{v}_{\ell },v_j{v}_{\ell }$, hence an original triangle in a graph. Conversely every original triangle in a graph remains. In fact each original triangle in a graph gives four in $\mu (G)$: itself and the three choices of replacing one of its vertices by its shadow. Thus triangle-freeness is preserved, but a positive triangle count is multiplied by four.

Define $M_2=K_2$ and $M_{k+1}=\mu (M_k)$ for $k\ge 2$. By the Mycielskian chromatic increase and Mycielskian triangle preservation, each $M_k$ is a finite triangle-free graph with chromatic number $k$. The first steps are $K_2,C_5$, the Grötzsch graph, and then a 23-vertex graph needing five colours. The vertex recurrence $n_{k+1}=2n_k+1$ gives $n_k=3\cdot 2^{k-2}-1$. These explicit examples show how arbitrarily strong graph coloring constraints can accumulate without any three-vertex clique.

For every $g,k\ge 3$, there is a finite graph with no cycle of length at most $g$ and with chromatic number at least $k$. A probabilistic proof samples a sparse binomial random graph, observes that it has few short cycles and no large independent set, and deletes one vertex from every short cycle.

A connected graph of maximum degree $\Delta$ has chromatic number at most $\Delta$ unless it is a complete graph or an odd cycle.