Un plano gráfico n vértices pueden tener en la mayoría de 3n-6 bordes, y así tendremos, al menos, $\frac{\binom n2}{3n-6} = \frac{n+1}{6} - \frac{1}{3(n-2)}$ colores.
En la otra dirección, al $n$ es impar, se puede particionar $K_n$ a $\frac{n-1}{2}$ ciclos Hamiltonianos, que son todos planos. Si estamos permitido a la curva en los bordes, podemos incrustar estos de la siguiente manera (por ejemplo,$K_9$). Un ciclo se parece a:
![curved hamiltonian cycle]()
y los otros tres ciclos se obtienen por $45^\circ, 90^\circ, 135^\circ$ la rotación de este. Aquí está una foto de la plena coloración, aunque no hay mucho pasando:
![curved decomposition]()
La construcción se generaliza a cualquier extraño $n$, la colocación de un solo vértice en el centro de un círculo, los demás en todo el perímetro, y zigzagueando entre ellos. Excepto para los dos bordes del centro y de un solo filo que de lo contrario sería un diámetro, casi todos los bordes pueden ser líneas rectas. Esto nos da una coloración con $\frac{n-1}{2}$ colores; al $n$ es incluso, se puede colorear $K_{n+1}$ $\frac n2$ colores, a continuación, eliminar el vértice central para obtener un colorante de $K_n$.
Así que la respuesta correcta está en el orden de $cn$ para algunas constantes $c$$\frac16$$\frac12$.
(Si no podemos curva de los bordes, yo no puedo con la mano pensar en una mejor cosa que hacer que la partición de $K_n$ a $n-1$ perfecto matchings por extraño $n$, lo que nos da $n-1$ en lugar de $\frac{n-1}{2}$ ciclos.)
