Graph colouring

A graph colouring assigns labels called colours to graph elements subject to specified constraints. A proper vertex colouring gives adjacent vertices different colours.

This decision problem asks whether a finite undirected graph has a graph colouring with three colours. It is NP-complete: a colouring certifies membership in NP, while 3-SAT reduces using Boolean-pair colouring gadgets and three-colour clause gadgets.

Take auxiliary graph triangles $a,b,c$ and $d,t,e$, join $a$ to $d$, and add edges $bx,cy,ez$. When $t$ has colour $T$ and the inputs $x,y,z$ have colours in $\{T,F\}$, this graph admits an extension to a graph colouring with three colours exactly when at least one input is $T$. All-false inputs force $a=d=F$, contradicting their edge. Conversely, use $(a,b,c,d,e)=(T,F,B,F,B)$ if $x=T$, $(T,B,F,F,B)$ if $x=F,y=T$, and $(F,T,B,B,F)$ if $x=y=F,z=T$. The extension property is necessary for both directions of a polynomial-time many-one reduction.

Two graph triangles sharing a vertex $B$ force their two opposite edges to use the same two colours in a graph colouring with three colours. A palette graph triangle $T,F,B$ and another graph triangle $u,\bar{u},B$ therefore force the literal pair to have opposite Boolean colours. This gadget is used in a reduction from 3-SAT to the three-colourability problem.

If every vertex subset of size at least $m$ contains an independent set of size $r$, repeatedly colour and remove an $r$-element independent set while at least $m$ vertices remain. Giving each remaining vertex its own colour uses at most $|V|/r+m$ colours.

The Lovász number of a finite simple graph is the semidefinite program valuewhere $J$ is the all-ones matrix. Its value on the complement graph gives a lower bound for the chromatic number.

For a finite simple graph with at least one vertex, the complement theta number has the equivalent semidefinite program formulationsandThe Schur complement and $U=tZ-J$ prove the equivalence; any feasible $t$ is at least one, so division by $t$ is valid. For a graph with an edge, $U/(t-1)$ is the Gram matrix of a strict vector coloring. Consequently $\bar{\vartheta }(G)$ is the strict vector chromatic number, and an ordinary $k$-graph colouring gives $\bar{\vartheta }(G)\le k$ by assigning the colors the vertices of a regular simplex.

A vector $k$-coloring, for $k>1$, assigns a unit vector $v_i$ to each vertex of a graph, such that $⟨v_i,v_j⟩\le -1/(k-1)$ on every edge. A graph colouring with $k$ colors gives a vector $k$-coloring by placing the colors at the vertices of a regular simplex. The Gram matrix of these vectors allows semidefinite programming to search for such a representation.

A strict vector $k$-coloring requires equality $⟨v_i,v_j⟩=-1/(k-1)$ on every edge. The least admissible $k$ is the complement theta number for a graph with an edge. Allowing merely an inequality defines the potentially smaller vector chromatic number.

For unit vectors $u,v$ and a random normal $a$ with independent standard normal distribution coordinates,The Gaussian distribution is invariant under orthogonal transformations. Projecting onto the plane spanned by $u,v$ therefore gives a uniformly distributed direction. If the angle between $u,v$ is $\theta$, the sign-disagreement directions form two sectors of total angle $2\theta$ out of $2\pi$. The endpoint cases $u=v$ and $u=-v$ give probabilities zero and one directly.

A $k$-semicoloring of a finite graph assigns one of $k$ colors to every vertex and is a proper graph colouring on an induced subgraph containing at least half the vertices. This is weaker than a proper coloring of the whole graph, and is useful as an intermediate step in a randomized algorithm.

Suppose a graph with $n$ vertices and $m>0$ edges has a vector coloring with adjacent inner products at most $-1/2$. Take $r$ independent copies of random hyperplane rounding and use the $r$ signs as a color. Each edge remains monochromatic with probability at most $3^{-r}$, so the expected number $B$ of monochromatic edges is at most $m{3}^{-r}$ by linearity of expectation.

Choose $r=\max \{0,\lceil {\log }_3(4m/n)\rceil \}$. Then Markov inequality gives $\mathbb{P}(B>n/2)\le 1/2$. On success, delete one endpoint of every monochromatic edge. This random alteration method leaves at least $n/2$ vertices properly colored withThe removed vertices can retain their original colors, as the semicoloring only requires the retained induced subgraph to be proper. A failed draw can be detected and repeated, with at most two trials on average. The case $m=0$ needs just one color. This is the elementary independent-hyperplane construction in Karger, Motwani and Sudan's paper on approximate graph coloring.

An edge colouring assigns a colour to every edge of a graph. In a red-blue edge colouring of a complete graph, a triangle is monochromatic when its three edges have the same colour.

The chromatic number $\chi (G)$ is the least number of colours in a proper vertex colouring of $G$.

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.

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.

The edge chromatic number is the least number of colours required to colour edges so that incident edges receive different colours.

Every finite simple graph of maximum degree $\Delta$ has edge chromatic number $\Delta$ or $\Delta +1$.

In a partial proper edge colouring with one uncoloured edge incident with a vertex $x$, a Vizing fan is a sequence of neighbours of $x$ whose incident edge colours are missing at earlier fan vertices. With one more colour than the maximum degree, fan rotations and a two-colour Kempe chain free one common colour at the endpoints of the uncoloured edge.

For two colours in a proper graph colouring, a Kempe chain is a connected component of the subgraph using only those colours. Interchanging the two colours throughout one component preserves properness.

For each positive integer $t$, the chromatic polynomial $P_G(t)$ counts the proper vertex colourings of a finite graph $G$ using a fixed palette of $t$ colours.

For a non-loop edge $e$,The first term counts colourings after deleting $e$; the second subtracts those giving its endpoints the same colour, which correspond to colourings of the contraction. Together with $P_G(t)=t^{|V(G)|}$ for an edgeless graph, induction proves that $P_G$ is a polynomial.

Attaching a new leaf to a graph multiplies its chromatic polynomial by $t-1$, because after colouring the old graph the leaf may receive any colour except its neighbour's.