Mostrar que los bordes de cualquier gráfico G pueden ser orientados de tal manera que no exista ningún camino dirigido de longitud $\chi(G)$.

Question

$\chi(G)$ representa el número mínimo de colores necesarios para la coloración adecuada de $G$. Lo único que he notado es que si tenemos $k=\chi(G)$ colores, entonces tenemos $k$ clases de colores, y que un camino conectando un vértice de cada clase de color tiene longitud $k-1$.

Answer 1

Sea $V_i$ el subconjunto de nodos coloreados $i$. Notar que $V_i$ es un conjunto independiente. Para cada $i, dirigir todas las aristas entre$V_i$y$V_j$hacia$V_j$. Entonces cada camino dirigido tendrá como máximo$\chi(G)-1$ aristas.