El gráfico bicúbico no hamiltoniano más pequeño de 2 conexiones con índice cromático 3

Question

Encontré este ejemplo bastante trivial para un gráfico bicubic no hamiltoniano 2 conectado con índice cromático 3:

$\hskip0.5in$

¿Es este el más pequeño? Si no puedes construir uno más pequeño?

Answer 1

Su ejemplo es el más pequeño.

Me lo tomo "bicúbica" significa bipartito y 3-regular. En un bipartito gráfico, el borde cromática número (o cromática índice) es igual al grado máximo, por lo que cada bicúbica gráfica tiene cromática índice 3.

Hay archivos de datos de diferentes familias de gráficos disponibles. Cúbicos de gráficos (al parecer significado conectado 3-regular gráficas simples) hasta 22 vértices están disponibles en Gordon Royle del sitio web, en un formato que puede ser importado en Mathematica.

Me encontré con un comando como

LG = Import[
    "http://school.maths.uwa.edu.au/~gordon/remote/cubics/cub20.g6"];

para cada tamaño de archivo de datos (04 hasta 20), y luego corrió

Select[LG, (ConnectedGraphQ[#] && ! HamiltonianGraphQ[#] && 
    Min[VertexDegree[#]] == 3 && Max[VertexDegree[#]] == 3 && 
    BipartiteGraphQ[#]) &]

para encontrar cualquier nonhamiltonian bipartito. (Las condiciones para la conectividad y el grado de los vértices debe ser redundante, ya que sólo conectado 3-regular los gráficos se incluyen en los datos.) No existe ninguno con menos de 20 vértices. Por otra parte, sólo un ejemplo que existe con 20 vértices. Mathematica presenta como esto (he comprobado que es isomorfo a la suya):