El boceto de un 5 regular plano gráfico, G $\chi(G)$ = 3.

Question

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.

Answer 1

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.

Answer 2

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.