Cromática número $χ(G) > k$ implica la existencia de la camino de longitud $k$

Question

Mostrar que si $G$ es un loopless gráfico, $k≥1$ es un número entero y $χ(G) > k$ $G$ tiene una ruta de acceso con $k$ bordes.

Por lo tanto, podemos asumir WLOG que $G$ está conectado. estamos buscando un camino de $P$ donde $|V(P)| = k+1 $ $|E(P)| = k.$ estoy atascado con esta pregunta. Sé que $χ(G) < d(G) + 1$ donde $d(G)$ es el máximo grado de los vértices de $G$. Si $χ(G)= k+1$ , entonces no debe ser de al menos $k+1$ vértices de grado $> k$. No estoy seguro de cómo tomar desde allí, o si incluso estoy en la dirección correcta. Puede alguien por favor ayuda??

Answer 1

Deje $\ell$ denotar la longitud del camino más largo en $G$ con cromática número $\chi > k$. El grado mínimo de $G$ satisface $\delta \ge \chi - 1 \ge k$ y el camino más largo satisface $\ell \ge \delta$. Por lo tanto,$\ell \ge k$.

Edit: he hecho un pequeño error en el anterior, pero la idea es la misma. Deje $G$ $\chi$- cromática gráfico donde $ \chi > k$. Then $G$ contains a $\chi$-critical subgraph $H\subseteq G$. For the $\chi$-critical graph $H$, we have $\delta_H \ge \chi - 1$ where $\delta_H$ is the smallest vertex degree of $H$.

Sabemos que un gráfico con mínimo grado $\delta$ tiene necesariamente un camino de longitud de, al menos, $\delta$ de lo que se deduce que el camino más largo de $H$ es de longitud al menos $$\delta_H \ge \chi - 1 \ge k$$ Por lo $H$ contiene una ruta de acceso de la longitud de, al menos, $k$ y, por tanto, $G$ también contiene el mismo camino.