¿Existencia de caminos de arco iris en gráficos?

Question

Deje $G$ ser un gráfico, y deje $c: V(G) \to \{1,\dots,k\}$ ser un adecuado $k$-la coloración de las $G$. Decimos que un camino de $v_1 \dots v_k$ $G$ es un arco iris de ruta de este colorante si $c(v_i) = i$ por cada $i \in \{1,\dots,k\} $. Ahora supongamos que $k = \chi(G)$, la cromática número de $G$; estoy tratando de determinar si es o no un arco iris camino que existe para este colorante.

Realmente no sé por dónde empezar, aunque. Si $k = 2$, luego un arco iris camino existe, ciertamente; para el caso de $k = 3$, he intentado buscar en los ciclos de longitud impar y las ruedas con un número impar de radios y parece que los gráficos de este tipo siempre debe tener el arco iris rutas así, pero no estoy seguro de cómo generalizar a grafos con $\chi(G) = 3$ o más altos valores de $k$.

Cualquier ayuda es muy apreciada.

Answer 1

La respuesta es sí.

Podemos, sin pérdida de generalidad supongamos que $G$ está conectado; de lo contrario, nos tiramos cada componente con menor cromática número, y considerar todos los demás componentes de forma individual.

Para $k=3$: Vamos a $E_1$ ser el conjunto de todos los vértices con el color de la $1$. Deje $E_2$ ser el conjunto de todos los vértices adyacentes a un vértice en $E_1$ con el color de la $2$. Si no hay tal vértice, entonces todos los vértices en $E_1$ cambia de color para el color de la $2$, y tenemos un $(k-1)$colorear de $G$; la contradicción. Deje $E_3$ ser el conjunto de todos los vértices adyacentes a un vértice en $E_2$ con el color de la $3$. Si no hay tal vértice, entonces podríamos cambiar el color de $E_1$ a el color de la $2$ $E_2$ a la de color 3, y obtener un 2-engañosa gráfico; contradicción. Por lo tanto, $E_1,E_2,E_3$ son no vacíos, por lo que podemos encontrar un arco iris camino de $e_1,e_2,e_3$ donde $e_i\in E_i$.

Este argumento puede ser transportado en general $k$: Vamos a continuar. Deje $E_4$ el conjunto de vértices adyacentes a $E_3$ que tienen el color de la $4$. Si se vacía, entonces se podría cambiar el color de $E_1,E_2,E_3$ a los colores $2,3,4$, respectivamente, y obtener un $(k-1)$colorear de $G$; la contradicción. Podemos definir a la $E_5,\ldots,E_k$ de forma análoga. Cuando hayamos terminado, podemos elegir un arco iris camino de $e_1,\ldots,e_k$ donde $e_i\in E_i$ por cada $i$.