Uma $k$-coloração e seus subgrafos
A proposição na seção anteiror mostra que todo grafo $k$-cromático possui um subgrafo de grau mínimo pelo menos $k-1$. De fato, ele possui um subgrafo $k$-cromático tal:
Lema
Todo grafo $G$ k-cromático possui um subgrafo k-cromatico de grau mínimo pela menos $k-1$.
Demonstração:
Dado um grafo $G$ com $\chi(G) = k$,tomemos $H \subset G$ minimal tal que $\chi(H)=k$. Se $H$ possui vértice $v$ tal que $d_H(v) \leq k-2$, podemos estender uma $(k-1)$-coloração de $H-v$ para uma de $H$, contradizendo a escolha de $H$.
$\square$
Referências
- Reinhard Diestel. “Graph Theory” .5th Electronic Edition 2016, pp. 123. Acesso em 12/06/2023.