En efecto, es NP-completo decidir si un grafo planar es $3$ -colorables (véase el artículo "Some simplified NP-complete graph problems"). Así que es poco probable que veamos una buena caracterización de los problemas planares $3$ -Gráficos coloreables. Sin embargo, hay algunos resultados conocidos que dan clases de grafos planares $3$ -Gráficos coloreables.
Se sabe que los grafos exteriores (grafos planos en los que todos los vértices se encuentran en la cara exterior) son $3$ -colorables.
Series Gráficos paralelos (gráficos que no contienen un $K_4$ -minor) son conocidos por ser $3$ -colorables. Esta es la conjetura de Hadwinger (la $4$ -teorema del color con esteroides) aplicado a $K_{4}$ -menores de edad.
El teorema de Grotzech dice que los grafos planares libres de triángulos son $3$ -Colaborable. En general, si un gráfico no contiene ciclos de longitud $0 \bmod 3$ entonces el gráfico es $3$ -colorables. Hay un montón de otras generalizaciones de este resultado para obtener conjuntos ligeramente más amplios de gráficos (planos).
El teorema de Brook dice que todas las subcúbicas (de grado máximo $3$ ) los gráficos son $3$ -colorables.
Gráficos con degeneración $2$ (todos los subgráficos tienen un vértice de grado $2$ ) son $3$ -colorables.
Por supuesto, si un gráfico no tiene ciclos Impares, entonces es $2$ -colorables, por lo que los grafos planos bipartitos son $2$ -colorables.
1 votos
Ver esta pregunta math.stackexchange.com/questions/459773/ ... draks está interesado en los grafos planos trivalentes (3-conectados) cuyas caras son sólo cuadrados y hexágonos ... los primeros sólo requieren $3$ ¡colores!