Coloración de vértices en grafos dirigidos

Question

Mi pregunta es la siguiente;

Demuestra que $\chi (G) \leq k$ si y sólo si las aristas de G pueden orientarse de tal manera que ningún camino dirigido contenga más de k vértices.

(Sugerencia: Para demostrar la dirección hacia atrás, elimine un conjunto de aristas de tamaño mínimo que destruya todos los ciclos dirigidos. Sea H el subgrafo dirigido de G obtenido de este modo. Colorear un vértice x con $i \leq k$ si el camino dirigido más largo de H que comienza en x tiene I vértices. Demuestre que esto tiene una coloración propia de G.)

No tengo ni idea de por dónde empezar.

Saludos cordiales

Answer 1

Supongamos que el gráfico se puede colorear con colores $1,2\dots m$ con $m\leq k$ . Dirige el gráfico de forma que cada arista vaya del color más pequeño al color más grande. Es evidente que no hay ningún camino dirigido con más de $m$ vértices pueden existir, ya que los colores van aumentando a lo largo de cada camino. Así que la implicación hacia adelante es trivial.

La implicación hacia atrás es la difícil, la idea tiene un sabor similar a la demostración del teorema de Erdös-Szekeres. Supongamos que el grafo puede ser dirigido de tal manera que ningún camino contenga más de $k$ vértices, vamos a colorearlo usando colores $1,2,\dots, k$ . Sea $H$ sea un gráfico obtenido a partir de $G$ eliminando un conjunto de aristas de tamaño mínimo.

Ahora coloreamos los vértices $v$ con la longitud del camino más largo en $H$ que termina con $v$ (que, por supuesto, es como máximo $k$ ). Es evidente que dos vértices del mismo color no pueden estar unidos por una arista en $H$ Supongamos que una arista de $H$ de $u$ a $v$ existe, sea $x_1,x_2,\dots,u$ sea el camino más largo en $H$ terminando en $u$ entonces $x_1,x_2,\dots ,u,v$ es un camino más largo en $H$ terminando en $v$ o contiene vértices repetidos y, por tanto, un ciclo dirigido.

Supongamos ahora que hay una arista en $G\setminus H$ pasando de $u$ a $v$ tal que $u$ y $v$ tienen el mismo color, debe existir un ciclo dirigido que utilice $uv$ y ningún otro vértice de $G\setminus H$ (porque el conjunto de aristas eliminadas es de tamaño mínimo). Sea $u,v,x_1,\dots ,x_nu$ sea el ciclo, Sea $y_1,y_2,\dots,y_n,v$ sea el camino más largo en $H$ terminando en $v$ entonces $y_1,y_2,\dots,y_n,v,x_1,\dots,u$ es un camino más largo en $H$ terminando en $v$ o contiene vértices repetidos y, por tanto, un ciclo dirigido.