Esta pregunta surgió en una licenciatura de matemáticas club de la reunión de ayer.
Como sabemos, un grafo es planar si puede ser integrado en el plano sin bordes de cruce. Un famoso necesaria y suficiente combinatoria condición para un grafo es plano es el teorema de Kuratowski: un gráfico de $G$ es planar si no contiene una subdivisión del grafo completo $K_5$ o del bipartito gráfico de $K_{3,3}$.
Ahora considere la posibilidad de un polígono $P$ en el plano (una secuencia finita de vértices, sucesivamente, se unió por no cruzar la línea de segmentos). Yo no requieren que $P$ ser convexo. Una triangulación de $P$ se compone de la original polígono $P$, junto con otras no-cruce de los segmentos de línea uniendo los vértices de $P$, de tal manera que el interior de $P$ se divide en triángulos. (Para que no se les permite añadir interna de los vértices. No estoy seguro de si esta es exactamente la definición habitual de "triangulación".) Usted puede ver esta triangulación como un gráfico, el uso de los vértices del polígono original, y todos los originales y añadidos de los segmentos de línea como los bordes.
Aquí es un crudo de dibujo. Los puntos verdes son los vértices, las líneas negras son el polígono original, las líneas rojas son el agregado de los segmentos de la triangulación.
Permítanme decir una (resumen) finito gráfico de $G$ es un polígono de triangulación si existe un polígono $P$ y una triangulación de $P$ que, como un gráfico, es isomorfo a $G$.
Dado un número finito de gráfico de $G$, hay una necesaria y suficiente combinatoria condición para $G$ a ser un polígono de triangulación? (Tal vez de forma análoga a Kuratowski?)
Se nos ocurrió con algunas condiciones necesarias:
$G$ debe ser plana, obviamente. Así que por Kuratowski no puede contener una subdivisión de $K_5$ o $K_{3,3}$.
$G$ debe ser conectado, también obvio.
$G$ debe ser de 3 engañosa. (Así que no todos los planos del gráfico es un polígono de triangulación; en particular, $K_4$ no es un polígono de triangulación.) Este parece ser bien conocido.
(Aquí es un boceto de una prueba de 3 colorabilidad. Inducción sobre el número de $n$ de los vértices de $G$. El caso base $n=3$ es trivial. Para el paso inductivo, vamos a $G$ ser un polígono de triangulación con $n$ vértices. Fijar una incrustación de $G$ que es un polígono de triangulación. Considere el grafo dual $G'$$G$, excluyendo la cara exterior. $G'$ debe ser acíclicos, porque un ciclo en $G'$ haría un bucle dentro de $P$ que encierra un vértice de $P$, contradiciendo la simple conexión de $P$. Por lo $G'$ contiene una hoja; esto corresponde a una cara triangular de $G$ con dos bordes exteriores $e_1, e_2$. Deje $v$ ser el vértice entre los bordes; no se puede incidente en cualquier otro bordes, por lo $v$ tiene grado 2. Por la hipótesis inductiva podemos correctamente color de 3 $G -v$. Pero desde $v$ tiene grado 2 se puede colorear $v$ también, por lo $G$ es de 3 engañosa.)
Pero no nos descubre una condición necesaria y suficiente.
(Nota: Este no es mi campo, así que es muy probable que yo estoy mal uso de la terminología o la ignorancia de los hechos conocidos. Por favor, siéntase libre de ilumíname!)
