Emparelhamentos e Coloração de Arestas - Prof. Marcia Cerioli

Prévia do material em texto

UFRJ - Teoria de Grafos - 2017/2
4. Emparelhamentos e Colorac¸a˜o de Arestas
1. Considere um tabuleiro de xadrez 8×8 em que os cantos que sa˜o casas brancas
foram retirados. Decida se e´ poss´ıvel cobrir este tabuleiro modificado com
retaˆngulos 2 × 1. Se sim, mostre como.
2. Mostre como determinar o tamanho de um conjunto independente ma´ximo
em um grafo bipartido e, se poss´ıvel, deˆ uma fo´rmula para determinar seu
tamanho.
3. Seja G um grafo bipartido e k-regular, com k > 0, enta˜o G tem um empa-
relhamento perfeito.
4. Sejam M e N dois emparelhamentos de um grafo G tais que ||M | − |N || ≥ 2.
Mostre que existem emparelhamentos M ′ e N ′ tais que M ∪ N = M ′ ∪ N ′ e
||M ′| − |N ′|| < ||M | − |N ||.
5. Mostre que o grafo de Petersen e´ 4-aresta-croma´tico.
6. Determine χ′(Kn), se n e´ par.
7. Determine χ′(Kn), se n e´ ı´mpar.
8. Prove que todo grafo 3-regular e hamiltoniano tem ı´ndice croma´tico igual a 3.
Mostre que a rec´ıproca na˜o e´ verdadeira, isto e´, exiba um grafo 3-regular e
com ı´ndice croma´tico igual a 3 que na˜o e´ hamiltoniano.
9. Prove que se G e´ um grafo k-regular de ordem par, enta˜o o grafo obtido de
G pela subdivisa˜o de uma aresta (por um novo ve´rtice) e´ tal que χ′(G) =
∆(G) + 1.
10. Prove que se G e´ um grafo regular de ordem ı´mpar, enta˜o χ′(G) = ∆(G) + 1.