Ata de Aula: 25/11/2002
Redator: Sílvia Cristina de Matos Soares
8.4 More Extremal Problems
Problema da Fofoca (Gossip Problem): existem n fofoqueiros, e cada um possui uma parte da informação. Todos desejam saber a informação completa, e para isso são feitas várias chamadas telefonicas. Quantas chamadas são necessárias?
Para n >= 4, bastam 2n - 4 chamadas. Primeiramente é selecionado um conjunto S de 4 pessoas. Todos ligam para um dos 4. Os 4 compartilham a informação através de chamadas sucessivas 2 a 2 (por exemplo, AB; CD; AC; BD). E, posteriormente, os outros recebem chamadas do conjunto S, utilizando um total de:
(n - 4) + 4 + (n - 4) = 2n - 4 chamadas.
Para n >= 4, o número mínimo de arestas em um esquema de fofoca com n vértices é 2n - 4.
Para n = 3 (fofoqueiros: A, B e C), 3 chamadas bastam:
A liga para B, B liga para C e, B ou C liga para A.
Coloração com Listas (List Coloring): cada vértice do grafo possui uma lista de cores disponíveis. A cor do vértice deve pertencer à lista e a coloração deve ser própria.
k-escolhível (k-choosable): um grafo G é k-escolhível se, para qualquer atribuição de listas de tamanho k aos vértices, é possível obter uma coloração própria.
Escolhibilidade (Choosability ( chi l (G) )): é o mínimo k tal que G é k-choosable.
O grafo K3,3 é exemplo de grafo k-colorável mas não k-escolhível, para k = 2. A atribuição de listas abaixo torna impossível colorir propriamente o grafo.
Coloração de Aresta com Listas (List Edge Coloring): cada aresta do grafo possui uma lista de cores disponíveis. A cor da aresta deve pertencer à lista e a coloração deve ser própria.
Edge Choosability ( chi' l (G) )): é o mínimo k tal que para toda associação de listas de tamanho k é possível obter uma coloração própria de arestas.
Conjectura (List Coloring Conjecture): chi' l (G) = chi' (G) para todo G.
Coloração Total (Total Coloring) de G: associa uma cor a cada vértice e a cada aresta de maneira que objetos coloridos possuam cores diferentes quando forem adjacentes ou incidentes.
Conjectura da Coloração Total (Total Coloring Conjecture): todo grafo simples G possui uma coloração total com, no máximo, Delta (G) + 2 cores.