Dúvida coloração

Dúvida coloração

por André Gomes -
Número de respostas: 2

No material das aulas, a página 46 parágrafo 5 diz o seguinte:

"O conceito de coloração de vértices é uma generalização do conceito de bipartição (veja seção 13): toda bipartição de um grafo é uma coloração dos seus vértices, e toda bicoloração é uma bipartição."

Minha dúvida é a seguinte: não seria mais correto dizer que "(...) toda bipartição de um grafo é uma bicoloração dos seus vértices(...)" ?

Por que desta maneira me dá a impressão que qualquer k-coloração é uma bipartição, o que não é verdade se levarmos em conta a definição da página 13 que diz que " Uma bipartição (= bipartition) de um conjunto V é um par {U;W} de conjuntos"

Caso eu esteja enganado, alguém poderia me explicar o motivo?

Em resposta à André Gomes

Re: Dúvida coloração

por Lucas Piva Rocha Corrêa -
"toda bipartição de um grafo é uma coloração dos seus vértices"

Uma bicoloração, em particular, é uma coloração de um grafo, e como uma bipartição induz uma bicoloração trivialmente, toda bicoloração de um grafo é uma coloração de seus vértices.

A impressão que você tem de que qualquer k-coloração é uma bipartição me parece ser porque você está assumindo que se vale a ida da afirmação, vale a volta, o que não é verdade. Veja:

Todo grafo que possui emparelhamento perfeito possui um número par de vértices (verdade). Isso, de forma alguma, implica que todo grafo com número par de vértices possui um emparelhamento perfeito.

Ida: Toda bipartição de um grafo é uma coloração dos seus vértices. (verdade).
Volta: Toda coloração de vértices de um grafo é uma bipartição. (mentira)

Espero ter entendido certo sua dúvida e conseguido explicar direito.