MO405 - Exercícios - Propostos em 2002-10-07

1. Qual o número cromático de Cn, Qn, Kn e Km,n?

2. (5.1.1 do livro)

Soluções - Discutidas em classe em 2002-10-09

1.

Grafo	Número Cromático	Condição
Cn	2	n par
	3	n ímpar
Qn	1	n=0
	2	n diferente de 0
Kn	n-1
Km,n	1	m=0 ou n=0
	2	m e n diferentes de 0

2. Grafo original

Grafo Redesenhado:

Colorido:

Clique number = 3

Independence number = 2

Chromatic Number = 4

Sim, o limite (Chromatic Number of G) >= n(G)/(independence number of G) prova a otimalidade da coloração, pois

n(G)/(independence number of G)=7/2=3,5

Sim, o grafo é cor-crítico. Testando remoção das arestas marcadas do grafo (figura abaixo), que cobre todos os casos:

Temos os seguintes grafos 3-coloridos: