Coloração de arestas

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
3-coloração-de-arestas do grafo de Desargues.

Em teoria dos grafos, uma coloração de arestas de um grafo é a atribuição de “cores” para as arestas de um grafo de forma que não haja duas arestas adjacentes tendo a mesma cor. Por exemplo, a figura à direita mostra uma coloração de arestas de um grafo com as cores vermelha, azul e verde. Coloração de arestas é um dos vários tipos de coloração de grafos.

O Problema da coloração de arestas pergunta se é possível colorir um dado grafo usando no máximo n cores. O número mínimo exigido de cores para um grafo é chamado de índice cromático. Por exemplo, o grafo à direita pode ser colorido com três cores, mas não pode ser colorido por duas cores, e, portanto, tem o índice cromático três.

Definição[editar | editar código-fonte]

Tal como acontece com a sua contrapartida em vértices, uma coloração de arestas de um grafo, quando mencionada sem qualquer qualificação, é sempre assumida ser uma coloração própria das arestas, significando que não há duas arestas adjacentes atribuídas com a mesma cor. Aqui, "adjacentes" significa não compartilhar um mesmo vértice. Uma coloração própria com k cores é chamada uma k-aresta-coloração (própria) e é equivalente ao problema de particionamento do conjunto de arestas em k acoplamentos. A um grafo que pode ser atribuída uma (própria) k-arestas-coloração é k-aresta-colorível. Uma 3-arestas-coloração de um grafo cúbico é algumas vezes chamada uma coloração Tait.

O menor número de cores necessárias em uma (própria) coloração de arestas de um grafo G é o índice cromático, ou número cromático de arestas, χ′(G), também, por vezes, simbolizado \chi_1(G). Um grafo é k-arestas-cromático se o seu índice cromático é exatamente k. O índice cromático não deve ser confundido com o número cromático χ(G).

Propriedades[editar | editar código-fonte]

Em seguida, façamos Δ(G) denotar o grau máximo; e μ(G), a multiplicidade. Algumas propriedades de χ′(G):

  1. χ′(G) = 1 se e somente se G é um acoplamento.
  2. χ′(G) ≥ Δ(G).
  3. χ′(G) ≤ Δ(G) + 1. (Teorema de Vizing, nomeado em honra a Vadim G. Vizing que o descobriu em 1964, divide todos os grafos em 2 classes: Classe 1 grafos tem χ′(G) = Δ(G); Classe 2 grafos tem χ′(G) = Δ(G)+1).
  4. χ′(G) ≤ Δ(G) + μ(G), onde G é permitido ser um multigrafo.
  5. χ′(G) ≤ (3/2)Δ(G) para qualquer multigrafo [1] .
  6. χ′(G) = Δ(G) se G é um grafo bipartido. (teorema bipartido de König)
  7. χ′(G) = Δ(G) se G é simples, planar e Δ(G) ≥ 7. (Vizing,1965[2] combinado com Sanders e Zhao,2001[3] )
  8. χ′(G) = Δ(G) para quase todos os grafos (Erdős e Wilson, 1977[4] ).

Classificando grafos e encontrando seu índice cromático[editar | editar código-fonte]

Como podemos ver acima, χ′(G) é igual a Δ(G) ou Δ(G) + 1. Quando χ′(G) = Δ(G), G é dito ser Classe 1; caso contrário, Classe 2. (Holyer, 1981[5] ) provou que é NP-completo determinar se um grafo simples é Classe 1 ou Classe 2. No entanto, esforços têm sido feitos para dar uma caracterização parcial.

Por exemplo, Vizing (1965)[2] mostrou que um grafo simples planar é da Classe 1, se o seu grau máximo é de pelo menos 8. Em contraste, ele observou que para os graus máximos 2, 3, 4, e 5, existem grafos planares simples da Classe 2. Por exemplo, comece com um sólido platônico e substitua uma única aresta por um caminho de duas arestas adjacentes. Desta forma, os sólidos platônicos resultam em simples grafos planares de classe 2 de grau máximo de 3, 4 e 5. (Cada ciclo de comprimento ímpar é um grafo de classe 2 de grau máximo 2).

Vizing conjecturou o seguinte resultado para os dois casos, que ele não resolveu:

Conjectura Vizing do grafo planar[6] .

Todos os grafos simples e planares com grau máximo 6 ou 7 são de Classe 1.

Sanders & Zhao (2001) [3] provaram parcialmente a conjectura do grafo planar de Vizing. Eles mostraram que todos os grafos simples e planares com grau máximo de 7 são da classe 1. Assim, o único caso que permanece sem solução de grafos simples e planares é o grau máximo de 6.

Esta conjectura tem implicações para a conjectura da coloração total

Referências

  1. SHANNON, Claude E.. (1949). "A theorem on coloring the lines of a network". J. Math. Physics 28: 148–151 pp..
  2. a b VIZING, V. G.. (1965). "Critical graphs with given chromatic class" (em russo). Metody Diskret. Analiz. 5: 9–17 pp..
  3. a b SANDERS, Daniel P.; ZHAO, Yue. (2001). "Planar graphs of maximum degree seven are class I". Journal of Combinatorial Theory, Series B 83 (2): 201-212 pp.. DOI:10.1006/jctb.2001.2047.
  4. ERDÕS, Paul; WILSON, Robin J.. (1977). "Note on the chromatic index of almost all graphs". Journal of Combinatorial Theory, Series B 23: 255–257 pp.. DOI:10.1016/0095-8956(77)90039-9..
  5. HOLYER, Ian. (1981). "The NP-completeness of edge-coloring". SIAM Journal on Computing 10: 718–720 pp.. DOI:10.1137/0210055.
  6. Vizing, V. G.. (1964). "On an estimate of the chromatic class of a p-graph". Diskret. Analiz. 3 p. 25–30..