¿Es cierto que todo grafo plano que no es tricolor tiene una rueda par como subgrafo? Lo pregunto porque quiero demostrar que todo grafo plano exterior es tricolor.
Respuestas
¿Demasiados anuncios?
No.
La refutación moral: Si esto fuera cierto, sería un si y solo un si, ya que está claro que ningún gráfico con una rueda par es tricolor. Pero un grafo tiene una rueda par como subgrafo si y sólo si el enlace de algún vértice no es bipartito. La comprobación de la bipartición puede hacerse en tiempo polinómico, por lo que comprobar si un grafo contiene una rueda par puede hacerse en tiempo polinómico. Pero comprobar si los gráficos planos son 3 -colorable es NP completo , por lo que esto demostraría que P=NP.
Verificación de que este contraejemplo funciona: Dejemos que W sea el gráfico en el que eliminamos la arista garabateada. Tiene dos 3 -colores, hasta la permutación de colores:
(En ambas coloraciones, las esquinas unidas por la línea serpenteante tienen el mismo color.
Es fácil comprobar que no hay una rueda uniforme -- W es 3 -colorables, por lo que no puede tener una rueda par, entonces comprueba que el nuevo borde no importa. O simplemente comprueba las vecindades de todos los vértices; por simetría, sólo hay 6 casos.
Como señala Benjamin Dickman en los comentarios, demostrar que un gráfico fuera de plano es 3 -colorable no es difícil una vez que se abandona este enfoque condenado.
user45021
Puntos
1
Esto está cerca: http://arxiv.org/pdf/1309.7120v1.pdf
El teorema 1.2 dice que todo grafo plano sin rueda es tricolorable. Esto no es estrictamente lo que buscas porque no especificas que la rueda tenga que ser un subgrafo inducido, pero puede llevarte a donde quieres.
