Coloração de Vértices - Prof. Marcia Cerioli

Prévia do material em texto

UFRJ - Teoria de Grafos - 2017/2
5. Colorac¸a˜o de ve´rtices
1. Suponha que em um laborato´rio de qu´ımica devam ser armazenados 5 produtos
qu´ımicos a, b, c, d e e em va´rias a´reas de seu depo´sito. Alguns destes produtos
reagem violentamente quando em contato e, portanto, devem ser guardados em
a´reas diferentes do depo´sito. Na tabela abaixo, um asterisco indica que aquele
par de produtos qu´ımicos deve estar separado. Quantas a´reas sa˜o necessa´rias?
a b c d e
a - * * * -
b * - * * *
c * * - * -
d * * * - *
e - * - * -
2. Mostre que qualquer grafo tem pelo menos
(
χ(G)
2
)
arestas.
3. Qual e´ o nu´mero croma´tico de cada um dos grafos platoˆnicos?
4. Mostre que: χ(G) ≥ n
α(G)
, para todo grafo G de ordem n.
5. Mostre que: χ(G) + χ(G) ≤ n+ 1, onde n e´ a ordem de G.1
6. Mostre que: χ(G)χ(G) ≥ n, onde n e´ a ordem de G.
7. Prove que sempre existe uma ordem dos n ve´rtices de um grafo de ordem n
em que o algoritmo guloso para colorac¸a˜o de ve´rtices aplicado nesta ordem
encontra χ(G), isto e´, usa exatamente χ(G) cores.
8. Deˆ exemplo de um grafo Gp de ordem n = 2p com χ(Gp) = 2 e deˆ uma
ordem de seus ve´rtices em que o algoritmo guloso de colorac¸a˜o encontra uma
colorac¸a˜o com p cores.
9. Um grafo e´ k-cr´ıtico se e´ k-croma´tico G − e e´ (k − 1)-color´ıvel, para todo
e ∈ E(G). Mostre que o grafo de Mycielski Mk e´ k-cr´ıtico.
1As desigualdades deste exerc´ıcio e do pro´ximo sa˜o conhecidas como desigualdades de Nordhaus-
Gaddum