El número cromático de una gráfica es a lo sumo su circunferencia

Question

La cromática número de un gráfico es en la mayoría de su circunferencia: la duración del ciclo más largo en el gráfico. (Haciendo una excepción para los bosques, donde la cromática número se encuentra en la mayoría de los $2$ y la circunferencia no está definido.)

Esto puede ser mostrado como un corolario de la siguiente teorema:

Si $G$ ha $k$ distintos extraño ciclo de longitudes y $k'$ distintos incluso duraciones del ciclo, a continuación, $\chi(G) \le k+k'+2$. (P. Mihók, I. Schiermeyer, Ciclo de longitudes y cromática número de gráficos, la Matemática Discreta. 286 (2004) 147-149.)

Si asumimos que el ciclo más largo en $G$ tiene una longitud de $\ell$, entonces no se $\ell-2$ posibles duraciones del ciclo: $\{3, 4, \dots, \ell-1,\ell\}$. Por lo tanto, $k+k'\le \ell-2$, por lo que por el teorema anterior $\chi(G) \le \ell$.

Mi pregunta es: ¿esta declaración tiene más fácil la prueba? Después de todo, la desigualdad entre los cromática número y la circunferencia es mucho más débil.

No es difícil de comprobar en el caso de $\ell=3$ (como se ve en esta última pregunta).

También, hay un breve argumento de que cualquier gráfico de $G$ con $\chi(G)=k$ contiene una ruta de acceso (no es un ciclo) en $k$ vértices: deje que los colores se $\{1,2,\dots,k\}$, elija una coloración de tal manera que cualquier vértice de color $i$ es adyacente a los vértices $1,2,\dots,i-1$ (por ejemplo, el colorante que minimiza la suma de los colores sobre todos los vértices de trabajo). Luego de un vértice de color $k$, podemos ir a un vértice de color $k-1$, de ahí a un vértice de color $k-2$, y así sucesivamente hasta llegar a un vértice de color $1$.

Answer 1

Después de algo más de pensar, he encontrado una solución simple. Llegamos muy rápido a partir de dos resultados que son bien conocidos en la teoría de grafos, aunque para la integridad voy a incluir sus pruebas.

Lema 1. Un gráfico de $G$ con grado mínimo $k$ contiene un ciclo de longitud de, al menos, $k+1$.

Prueba. Tomar el camino más largo $v_0, v_1, v_2, \dots, v_\ell$ en $G$. El vértice $v_0$ tiene al menos $k$ vecinos, y todos ellos deben ser los otros vértices en el camino, porque de lo contrario nos podríamos extender la ruta y hacerla aún más. La última de $v_0$'s de los vecinos en la ruta de acceso debe ser por lo menos tan lejos como $v_k$ (ya que no hay $k$ de ellos), por lo que tenemos un ciclo de longitud de, al menos, $k+1$ siguiendo el camino de $v_0$ a $v_0$'s último vecino, a continuación, tomar el borde de vuelta a $v_0$.

---

Por el contrario, si el ciclo más largo en un gráfico de $G$ tiene una longitud de $k$, entonces se tiene un vértice de grado $k-1$ o menos. Lo que es más, en cada subgrafo $H$ de $G$, el ciclo más largo tiene una longitud de $k$ o menos (si se trata de un ciclo en $H$, es un ciclo en el $G$, también). Por lo $H$ debe tener un vértice de grado $k-1$ o menos.

El gráfico de esta propiedad - cada subgrafo tiene un vértice de grado $k-1$ o menos, se llama" $(k-1)$degenerada.

Lema 2. Un $(k-1)$degenerada gráfico de $G$ ha cromática número en la mayoría de las $k$.

Prueba. Nos introducirá en el número de vértices en $G$. Cuando $G$ ha $k$ vértices o menos, podemos $k$color $G$ , dando a todos los vértices de diferentes colores.

De lo contrario, deje $v$ ser un vértice de grado $k-1$ o menos. $G-v$ también $(k-1)$-degenerado (cada subgrafo de $G-v$ es un subgrafo de $G$) y dispone de un menor número de vértices, de modo que la inducción por $G-v$ es $k$-engañosa. Podemos $k$color $G$ a partir de la $k$colorear de $G-v$, luego de dar a $v$ un color distinto de los colores de sus vecinos (que elimina a la mayoría de las $k-1$ opciones).

---

Poniendo juntos los dos lemas: un gráfico con la circunferencia de la $k$ es $(k-1)$-degenerado, por lo que ha cromática número en la mayoría de las $k$. La cromática número se encuentra en la mayoría de la circunferencia.