= Solution
For the <three-colourability problem>, represent a candidate by a complete colour assignment $c:V\to\{r,g,b\}$, initially chosen at random. Give it the conflict <objective function>
$$
H(c)=\sum_{\{u,v\}\in E}\mathbf1_{c(u)=c(v)}.
$$
A neighbor changes the colour of one <vertex> to either other colour. For <hill climbing>, maximize $-H$, or equivalently repeatedly choose a recolouring that reduces $H$. One can inspect all $2|V|$ neighbors, or focus on conflicted <vertices> and evaluate their alternative colours using only incident <edges>. Stop successfully as soon as \b[$H=0$], which is exactly a <proper graph colouring> with three colours.
If no improving move exists at positive $H$, the method is stuck in a <local minimum>. Random restarts, limited sideways moves or other exploratory <local search> choices can reduce this failure mode, but do not turn a finite unsuccessful run into a proof of impossibility. On a graph with no <proper graph colouring> using three colours, every complete colouring has $H>0$, so this procedure cannot return a valid colouring. Conversely, a positive-conflict stopping point also occurs on some graphs admitting a <proper graph colouring> with three colours. \b[Failure of <hill climbing> alone does not certify non-colourability.] For a concrete trap, use a <bipartite graph> with three <vertices> on each side and every cross-<edge>, and give each side one vertex of each colour. There are three conflicts. Recolouring any single vertex leaves it with exactly one same-colour neighbor, so no single change improves $H$, even though colouring each whole side differently solves the instance.
Back to article page
