Return to Answer

Just to prove that this is a general-purpose colouring solution, use parameters below (produce a four-colouring):

Just to prove that this also applies to a general-purpose colouring solution, use parameters below (produce a four-colouring):

NOTE: Why did I comment out ParallelMap? Because apparently CylindricalDecomposition[..., "Components"] fails for many, if not all less trivial inputs on Mathematica versions up to 13.0.1 when parallel kernels are in use. This appears to be a long-running, reported issue. You can effectively run this code with ParallelMap once on a fresh session, but not more than that.

NOTE: Why did I comment out ParallelMap? Because apparently CylindricalDecomposition[..., "Components"] fails for many, if not all less trivial inputs on older Mathematica versions when parallel kernels are in use. This issue has been fixed in 13.1. You can effectively run this code with ParallelMap once on a fresh session, but not more than that.

NOTE: Why did I comment out ParallelMap? Because apparently CylindricalDecomposition[..., "Components"] fails for many, if not all less trivial inputs when parallel kernels are in use. This appears to be a long-running, reported issue. You can effectively run this code with ParallelMap once on a fresh session, but not more than that.

NOTE: Why did I comment out ParallelMap? Because apparently CylindricalDecomposition[..., "Components"] fails for many, if not all less trivial inputs on Mathematica versions up to 13.0.1 when parallel kernels are in use. This appears to be a long-running, reported issue. You can effectively run this code with ParallelMap once on a fresh session, but not more than that.