Explorador de coloreo de grafos

El grafo de Petersen tiene 10 vértices, 15 aristas y ningún triángulo. Por tanto, el panel indica χ ≥ 2. Halle el número cromático real. Este es el estado Grafo de Petersen.

1. Cualquier grafo proporciona dos cotas de forma inmediata: necesita al menos tantos colores como su clique más grande, y nunca más de uno por encima de su grado máximo.

   $$\omega (G)\le \chi (G)\le \Delta (G)+1:\text{Petersen has }\omega =2,\Delta =3⟹2\le \chi \le 4$$

2. La cintura del grafo de Petersen es 5, de modo que no hay ningún triángulo en él y la cota del clique se reduce al valor trivial 2. Ese es el número que muestra el panel.

   $$\text{girth}=5⟹\text{no triangle}⟹\omega =2,\text{yet the graph is not bipartite}$$

3. Solo es posible usar dos colores cuando el grafo es bipartito, y que sea bipartito significa que no tiene ningún ciclo impar. El pentágono exterior es un 5-ciclo, por lo que los dos colores quedan descartados.

   $$\text{bipartite}⟺\text{no odd cycle};\text{the outer 5-cycle is odd}⟹\chi \ge 3$$

4. Se puede colorear con tres colores; basta mostrar una disposición para demostrar por completo la cota superior. Colorea los vértices del pentágono exterior, en orden, con 1, 2, 1, 2, 3; después, colorea los cinco vértices interiores, siguiendo el mismo orden, con 2, 1, 3, 3, 2. Cada uno queda unido al vértice exterior de su propio radio. Recorre las quince aristas: los extremos de ninguna tienen el mismo color.

   $$\text{a 3-colouring exists}⟹\chi =3,\text{strictly above the clique bound }\omega =2$$

5. El teorema de Brooks indica lo mismo desde arriba: un grafo conexo que no sea ni completo ni un ciclo impar necesita a lo sumo Δ colores, y aquí Δ es 3.

   $$|V|=10,|E|=15,\Delta =3:\text{Brooks’ theorem gives }\chi \le 3\text{for a connected non-complete graph}$$

Ahora K₄: cuatro vértices, con sus seis aristas presentes. Calcule χ y compare las cotas con el resultado obtenido en Petersen. Este es el estado K4 completo.

1. Cuente las aristas en lugar de fiarse del dibujo: cada par de cuatro vértices está conectado, y hay seis pares.

   $$K_4:|V|=4,|E|=\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6,\text{every pair adjacent}$$

2. Cada vértice es adyacente a todos los demás, por lo que dos vértices no pueden compartir el mismo color. Eso constituye una cota inferior de 4 y no requiere más argumento que la propia definición.

   $$\text{all four vertices are mutually adjacent}⟹\omega =4⟹\chi \ge 4$$

3. Cuatro colores son evidentemente suficientes, de modo que la cota se cumple. El mismo razonamiento proporciona χ(Kₙ) = n para todo n, lo que convierte a los grafos completos en el caso sencillo.

   $$\text{four colours suffice trivially}⟹\chi (K_n)=n$$

4. Ponga los dos grafos frente a frente. La misma pregunta, las dos mismas cotas, y el desfase entre ellas es la materia en su totalidad.

   $$\text{here }\omega =\chi =4:\text{the bound is tight, and Petersen showed it need not be}$$

5. Observe dónde queda aquí el teorema de Brooks. Su cota de Δ = 3 sería errónea para K₄, motivo por el cual los grafos completos quedan excluidos explícitamente.

   $$\Delta +1=4\text{as well — Brooks’ theorem excludes complete graphs for exactly this reason}$$