A ciclo del tamaño de al menos $\frac{n}k$ en una gráfica con al menos $3k$ vértices

Question

Mi pregunta es la siguiente: En un $G=(V,E)$ donde $\alpha(G)\leq k$ (el máximo del tamaño de un subconjunto independiente de $G$) y $|V|=n\geq3k$, muestran que hay un ciclo de tamaño $\geq \frac{n}k$.

Ahora, $\chi(G)\geq \frac{n}{\alpha(G)}\geq \frac{n}k\geq3$. Vamos a examinar una óptima vértice-pintura de $G$, hay, al menos, $3$ cromática establece: $C_1, C_2, \dots, C_m$ (donde $m$ es la cromática número de $G$). Puede ser demostrado que existe un vértice con al menos $2$ a los vecinos, así que vamos a empezar el ciclo en ese vértice y conectarlo al tanto de sus vecinos. Ahora vamos a conectar los dos vecinos por cubrir a todos los restantes cromática conjuntos. En la prueba que yo tenía, me hizo la falsa suposición de que cada vértice debe estar conectado a uno de los miembros de una cromática establecida al que no pertenecen. Pero esto no es cierto, todo lo que puedo suponer es que entre dos cromática diferente conjuntos debe ser un borde (de lo contrario podríamos tomar su unión como una cromática conjunto). Necesito encontrar una manera de sortear esta dificultad y crear un ciclo que se basa en el $m$ cromática establece (por $m\geq \frac{n}k$, lo que demuestra lo que necesita ser probada). Si de otra manera por completo es sugerido, voy a estar muy agradecido a todos el mismo. Gracias.

Answer 1

Uno tiene que utilizar los siguientes dos teoremas fundamentales, que, por ejemplo, puede ser encontrado en Reinhard Diestel, la Teoría de grafos (Cuarta Edición), Springer Posgrado Textos en Matemáticas. Para un gráfico de $G = (V,E)$ dejamos $\delta(G)$ denotar el grado mínimo de $G$:

$$ \delta(G) = \min_{v\in V} d(v). $$

Si $H \subseteq G$ es un subgrafo y $v\in V$ es un vértice, luego escribimos $d_H(v)$ para el grado de $v$ en relación al $H$.

Teorema 1 (Diestel la proposición 5.2.2). Cada gráfico de $G = (V,E)$ contiene un subgrafo $H \subseteq G$$\delta(H) \geq \chi(G) - 1$.

Prueba. Primero construimos una enumeración de los vértices de $G$, de la siguiente manera:

• Deje $v_n$ ser un vértice de grado mínimo en $G$;
• Deje $v_{n-1}$ ser un vértice de grado mínimo en $G \setminus \{v_n\}$;
• $\ldots$
• Deje $v_i$ ser un vértice de grado mínimo en $G \setminus \{v_{i+1}, v_{i+2}, \ldots, v_{n-1}, v_n\}$.

Nota: el grado en que tener en cuenta en cada paso es el grado en relación a los restantes subgrafo $G \setminus \{v_{i+1},v_{i+2},\ldots,v_{n-1},v_n\}$, no el grado en el gráfico original $G$.

Ahora construimos un codicioso coloración de $G$ en la dirección inversa, de$v_1$$v_n$. Si los vértices $v_1,\ldots,v_{i-1}$ ya han sido de color, entonces hemos de color $v_i$ con el entero más pequeño $k\geq 1$ que no se producen entre sus vecinos de la izquierda. Ahora vamos a $C$ el número de colores utilizados en este colorante y dejamos $j \in \{1,\ldots,n\}$ ser un índice tal que $v_j$ recibe de color $C$. Ahora $v_j$ debe tener al menos $C - 1$ vecinos a la izquierda (color $1$ a través de $C - 1$). Ya que hemos elegido $v_j$, como mínimo, el grado de vértice en $G \setminus \{v_{j+1},v_{j+2},\ldots,v_{n-1},v_n\}$, se deduce que $$\delta\big(G \setminus \{v_{j+1},v_{j+2},\ldots,v_{n-1},v_n\}\big) \geq C - 1 \geq \chi(G) - 1.\tag*{$\Cuadro de$} $$

¿Por qué es útil? Debido a que las gráficas de gran tamaño mínimo grado contienen grandes ciclos:

Teorema 2 (Diestel la proposición 1.3.1). Cada gráfico de $G = (V,E)$ satisfacción $\delta(G) \geq 2$ tiene un ciclo de longitud de, al menos,$\delta(G) + 1$.

Prueba. Deje $x_0\cdots x_k$ ser un camino simple de longitud máxima. A continuación, todos los vecinos de $x_k$ mentira en este camino, de lo contrario el camino podría ser extendido. (Ver imagen a continuación). Como hemos $d(x_k) \geq \delta(G) \geq 2$ por supuesto, sabemos que $x_k$ tiene otro vecino (aparte de $x_{k-1}$). Ahora vamos a $i\in\{0,\ldots,k-2\}$ ser el índice mínimo de un vecino de $x_k$, entonces tenemos un ciclo de $x_ix_{i+1}\cdots x_{k-1}x_k$ que contiene todos los vecinos de $x_k$ $x_k$ sí. Por lo tanto, este ciclo tiene una longitud de, al menos,$\delta(G) + 1$. $$\tag*{$\Cuadro de$}$$

Poner estos resultados en conjunto, nos encontramos con

Corolario 3. Cada gráfico de $G = (V,E)$ satisfacción $\chi(G) \geq 3$ tiene un ciclo de longitud de, al menos,$\chi(G)$.

Estoy seguro de que usted puede tomar desde aquí. :-)

---

Como una nota del lado, el siguiente ejemplo muestra que el $\frac{n}{k}$ es óptimo, en el sentido de que no son los gráficos de satisfacer $\alpha(G) \leq k$ $n \geq 3k$ que no tienen un ciclo de más de $\lceil \frac{n}{k} \rceil$. Por ejemplo, corregir algunos entero $r\geq 3$ y considere la gráfica de $G$ obtenida por la toma de $k$ discontinuo completa de los gráficos de $K_r$ y la adición de un único vértice que está conectado a todos los otros vértices. Por lo tanto, ahora tenemos a $k$ camarillas de tamaño $r + 1$ que todos tienen exactamente un vértice en común. Esto es ilustrado por el ejemplo de abajo ( $k = 3$ $r = 9$).

Ahora, los resultados son:

• Tenemos $\alpha(G) = k$, ya que ningún conjunto independiente puede tener dos o más vértices de la misma camarilla;
• Claramente tenemos $n = kr + 1 \geq 3k$;
• El mayor ciclo tiene una longitud de $r + 1$: sólo hay un vértice que nos lleva de un grupo a otro, por lo que no podemos dejar lo que la camarilla de empezar en, y luego volver a ella.