PROFILPELAJAR.COM

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

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

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

χ′(G) = 1 se e somente se G é um acoplamento.
χ′(G) ≥ Δ(G).
χ′(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).
χ′(G) ≤ Δ(G) + μ(G), onde G é permitido ser um multigrafo.
χ′(G) ≤ (3/2)Δ(G) para qualquer multigrafo ^[1].
χ′(G) = Δ(G) se G é um grafo bipartido. (teorema bipartido de König)
χ′(G) = Δ(G) se G é simples, planar e Δ(G) ≥ 7. (Vizing,1965^[2] combinado com Sanders e Zhao,2001^[3])
χ′(G) = Δ(G) para quase todos os grafos (Erdős e Wilson, 1977^[4]).

Classificando grafos e encontrando seu índice cromático

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

↑ SHANNON, Claude E. (1949). «A theorem on coloring the lines of a network». J. Math. Physics. 28. pp. 148–151
↑ ^a ^b VIZING, V. G. (1965). «Critical graphs with given chromatic class». Metody Diskret. Analiz. (em russo). 5. pp. 9–17
↑ ^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). pp. 201–212. doi:10.1006/jctb.2001.2047
↑ ERDÕS, Paul; WILSON, Robin J. (1977). «Note on the chromatic index of almost all graphs» (PDF). Journal of Combinatorial Theory, Series B. 23. pp. 255–257. doi:10.1016/0095-8956(77)90039-9 .
↑ HOLYER, Ian (1981). «The NP-completeness of edge-coloring». SIAM Journal on Computing. 10. pp. 718–720. doi:10.1137/0210055
↑ Vizing, V. G. (1964). «On an estimate of the chromatic class of a p-graph». Diskret. Analiz. 3. p. 25–30 .