Lista9-MO405

Prévia do material em texto

Lista de Exercicio 9
Resolução:
Segundo teorema demonstrado em aula, um grafo G bipartido simples Classe 1, ou seja X’(G) = (G).
Em um grafo bipartido completo (G) = max {m, n}.
Falso. K4 é o contra exemplo:
X(K4) = 4 e X’(L(K4)) = 5
Para L(K4) aplicamos uma coloração usando guloso e chegamos em X’(L(K4)) <= 5. Alem disso, sabemos que (K4) = 4 para qualquer vértice e que como m(L(K4)) = 12 > piso(12/2) = 6, precisamos de (L(K4))+1 para pintá-lo. Logo, X’(L(K4)) >= 4+1 = 5, o que implica em X’(L(K4)) = 5.
Outro contra-exemplo (conferir):
Resolução:
Pendente
Resolução:
Qual a relação do vértice universal com Kn? Acho que dá pra falar que um grafo com vértice universal é um “quase-Kn-com-n-par”e que, como tal, dá para pinta-lo com no maximo o mesmo numero de cores (n-1). Dai o grau do v’ertice universal seria o n do Kn. Mas se isso for verdade, nao da pra generalizar dizendo que qualquer grafo com n par pode ser pintado com o mesmo n’umero de ores que um Kn com n par ?
Pendente
Pendente
Resolução
delta (G) <= w(L(G)) -- isso nao foi usado. ainda bem, pq nao sei se eh valido
Sabemos que X’(G) = X(L(G))
X(L(G)) <= delta(L(G)) + 1 (Brooks)
X’(G) <= delta(L(G)) + 1
delta(L(G)) = max(d(x)-1+d(y)-1))
delta(L(G)) = max(d(x)+d(y)-2))
Supondo d(x)=d(y)=delta(L(G))
delta(L(G)) <= 2*delta(G) - 2
Substituindo em X’(G) <= delta(L(G)) + 1, temos X’(G) <= 2*delta(G) - 1
Resolução:
O exercício é o oposto. Dado que é Hamiltoniano, devemos provar que é 3-coloração-aresta. Não da para aproveitar a légica dessa demo =/
Pendente
Pendente
Pendente
Pendente
Pendente
Pendente
Pendente