Deje $G$ tienen orden de $n$ y el tamaño de la $m$.
Puesto que G es planar sabemos $m \le 3n - 6.$ Ya que G es de 5-regular, sabemos $2m = 5n$.
El uso de estos dos hechos, tenemos que $5n \le 6n - 12$, lo que significa que $n \ge 12$. Además, dado que el gráfico es de 5-regular sabemos que n debe ser par.
Hasta ahora he tratado de bosquejar 5-regular grafos planares en 12, 16, y 24 vértices, pero ninguno de ellos había $\chi(G)$ = 3. Estoy teniendo problemas para dibujar el 5 regular grafos planares como es, y no digamos de encontrar uno que también es de 3 cromática. El problema parece ser que los gráficos contienen demasiados triángulos, que se traduce en más de 3 colores que son necesarios.
Cualquier ayuda para obtener esta gráfica sería muy apreciada.
Respuestas
¿Demasiados anuncios?
La gráfica de la chata cuboctahedron es un ejemplo con 24 vértices:
(dibujo adaptado de aquí; ver también Mathworld para otros simpáticos dibujos).
He encontrado esta tomando cuatro copias de este fragmento
\ \
\ \ \ )
\ \ \ /
.---A---B---C----
/ / \ / \ /
/ / C---A-----
/ / / \ /
/ / / B--------
/ / / \
/ `-----
y la organización de ellos como los vértices de un tetraedro, y resulta que el 3-colorear encaja! En el dibujo anterior, cada copia de este básica fragmento está teñido de verde, y las caras que corresponden a las caras del tetraedro original se tiñen de color rojo.
Comenzar con un triángulo. En cada vértice agregar tres bordes salientes ($9$ en total). En cada otro extremo de estos $9$ bordes agregar cuatro bordes salientes ($36$ en todos), y así ad infinitum. De esta manera en cada uno de los vértices del triángulo original de un árbol es construido, que puede ser coloreado con dos colores. Debido a la básica triángulo todavía tenemos tres colores para colorear el grafo completo.
