= Solution
If there are no <triangle in a graph>[triangles], any <edge colouring> works. Otherwise $\Delta\geq2$. Put $q=\lceil3\sqrt\Delta\rceil$ and colour each <edge> independently and uniformly from $q$ colours. For each <triangle in a graph>[triangle] $T$, let $A_T$ be the <event> that its three <edges> have one colour. Then
$$
\mathbb P(A_T)=q\left(\frac1q\right)^3=\frac1{q^2}.
$$
<Events> for <triangle in a graph>[triangles] sharing no <edge> depend on disjoint edge-colour variables, so each <event> is jointly <independent> of the collection of all such nonneighbours. Each <edge> of a <triangle in a graph>[triangle] lies in at most $\Delta-2$ other <triangle in a graph>[triangles]: a common <neighbour> of its endpoints must be one of at most $\Delta-1$ <neighbours> besides the other endpoint, and one of these is the third <vertex> of $T$ itself. Thus the dependency degree is at most $d=3(\Delta-2)$.
Because $q^2\geq9\Delta$,
$$
e\,\frac1{q^2}(d+1)\leq\frac{e(3\Delta-5)}{9\Delta}<\frac e3<1.
$$
The symmetric local lemma gives positive <probability> of avoiding every monochromatic <triangle in a graph>[triangle]. Hence
$$
\boxed{\lceil3\sqrt\Delta\rceil\text{ colours suffice}.}
$$
For an edgeless <graph> the empty <colouring> handles even the zero-colour case $\Delta=0$.
Back to article page
