Lista6-MO405

Prévia do material em texto

Lista de Exercícios 6 - MO405
Resolução:
X(K7) = 7
X(K3,5) = 2
X(C9) = 3
X(Peterson) = 3
Por Brooks:
X(Pet) <= delta(Pet) <= 3
Pet Contem C5 => X(Pet) >= 3
X(Pet) = |V(G)|/alfa(G) >= 10/4 >= 2,5 >= 3
==> X(Petersen) = 3
Resolução:
K-cubo
K-cubo é bibartido => X(k-cubo) = 2, k>=2 (OK)
Alternativamente, alfa = 4, => X(k-cubo) >= |V(G)| / alfa(k-cubo) = 8 /4 = 2
Multipartido completo: G = Kp1,p2,...,ps 
w(G) = s => X(G) >= s
Podemos colorir cada partição com uma única cor, pois os elementos da mesma partição não são adjacentes entre si. Ou seja, cada partição é um conjunto independente adjacente entre si. Logo, X(G) <= s
Como X(G) >=s e X(G) <= s, X(g) = s
Resolução:
stable set == conjunto independente
Resolução:
Pela lista de email:
a) X(G) = 4, X(H) = 4
b) Para G temos 2 argumentos
X(G) >= 11/3>= 4
É possível usar a expressão X(G) 1 + max{(M)}, M G
Se tirarmos algum dos vértices externos => (M) = 2;
Se tirarmos algum dos vértices do meio => (M) = 3;
Se tirarmos o vértice central => (M) = 2.
Dessa forma X(G) 4
Resolução:
Resolução:
Pela lista de e-mail: (Bem mais fácil de entender do que a resposta)
Base: n=1 delta(G) = 0, X(G) = 1
HI: Seja H com 1< k < n vértices => X(H) <= delta(G) + 1
Passo: Tomemos o grafo G, simples, com k+1 vértices e seja v um vértice de G.
Ao remover v de, obtemos o grafo G' com k vértices. Por H. I. G' tem uma k-coloração.
Podemos inserir v novamente. Como d(v) <= delta(G), os vizinhos de v usam no máximo delta(G) cores. Portanto podemos atributir a cor delta(G) +1 para v.
Portanto, G possui uma delta(G) +1-coloração. X(G) <= delta(G) +1
Resolução:
Complete graphs Kn and odd cycles C2n+1 are critical graphs.
Pendente
Resolução:
Pendente.
Resolução:
The cartesian product GxH contains copies of G and H as subgraphs, so X(GxH) max{X(G), X(H)}.
Let k = max{X(G), X(H)}. To prove the upper bound, we produce a proper k-coloring of GxH using optimal coloring of G and H. Let g be a proper X(G)-coloring of G, and h be a proper X(H)-coloring of H. Define a coloring f of GxH by letting f(u,v) be the congruence class of g(u) + h(u) modulo k. Thus f assigns colors to V(GxH) from set of size k.
We claim that f properly colors GxH. If (u,v) and (u’, v’) are adjacent in GxH, then g(u) + h(u) and g(u’) + h(u’) agree in one summand and differ by between 1 and k in the other. Since the difference of the two sums is between 1 and k, they lie in different congruence classes modulo k.
The cartesian product allows us to compute chromatic numbers by computing independence numbers, because a graph G is m-colorable if and only if the cartesian product CxKm has an independent set of size n(G).
Pular.
Tentativa: Como é conexo, das 13 arestas, 5 sao gastas para unirem os 6 vertices.
Depois disso, constroi se as arestas de tal forma a se obter a menor clique possivel, que vai ser w = 4. Lembre-se que nao pode haver lacos e arestas multiplas. Assim, X(G) >= w >= 4 que é maior que 3, como enunciado.
Resolução:
Resolução:
Tem que fazer báskara na formula final para chegar no X, que vai ser uma das raizes
Resolução:
Pendente.
Pendente.