Coloração de borda - Edge coloring

Uma coloração de 3 arestas do gráfico de Desargues

Na teoria dos grafos , a coloração das arestas de um gráfico é uma atribuição de "cores" às arestas do gráfico de modo que duas arestas incidentes não tenham a mesma cor. Por exemplo, a figura à direita mostra a coloração das bordas de um gráfico pelas cores vermelho, azul e verde. A coloração das bordas é um dos vários tipos diferentes de coloração do gráfico . O problema da coloração de arestas pergunta se é possível colorir as arestas de um dado gráfico usando no máximo $k$ cores diferentes, para um determinado valor de $k$ , ou com o menor número possível de cores. O número mínimo necessário de cores para as bordas de um determinado gráfico é chamado de índice cromático do gráfico. Por exemplo, as bordas do gráfico na ilustração podem ser coloridas por três cores, mas não podem ser coloridas por duas cores, portanto, o gráfico mostrado tem índice cromático três.

Pelo teorema de Vizing , o número de cores necessárias para colorir a borda de um gráfico simples é seu grau máximo $Δ$ ou $Δ + 1$ . Para alguns gráficos, como gráficos bipartidos e gráficos planares de alto grau , o número de cores é sempre $Δ$ , e para multigrafos , o número de cores pode ser tão grande quanto $3Δ / 2$ . Existem algoritmos de tempo polinomial que constroem cores ótimas de gráficos bipartidos e cores de gráficos simples não bipartidos que usam no máximo $Δ + 1$ cores; no entanto, o problema geral de encontrar uma coloração de aresta ideal é NP-difícil e os algoritmos mais rápidos conhecidos para isso levam um tempo exponencial. Muitas variações do problema de coloração de arestas, no qual as atribuições de cores às arestas devem satisfazer outras condições além da não adjacência, foram estudadas. Colorações de borda têm aplicações em problemas de programação e atribuição de frequência para redes de fibra óptica .

Exemplos

Um gráfico de ciclo pode ter suas bordas coloridas com duas cores se a duração do ciclo for uniforme: simplesmente alterne as duas cores ao redor do ciclo. No entanto, se o comprimento for ímpar, são necessárias três cores.

Construção geométrica de uma coloração de 7 arestas do grafo completo

K 8

. Cada uma das sete classes de cores tem uma aresta do centro a um vértice do polígono e três arestas perpendiculares a ele.

Um gráfico completo $K n$ com $n$ vértices pode ser colorido nas bordas com $n - 1$ cores quando $n$ é um número par; este é um caso especial do teorema de Baranyai . Soifer (2008) fornece a seguinte construção geométrica de uma coloração neste caso: coloque $n$ pontos nos vértices e no centro de um polígono de lados regulares $(n - 1)$ . Para cada classe de cor, inclua uma aresta do centro a um dos vértices do polígono e todas as arestas perpendiculares que conectam os pares de vértices do polígono. No entanto, quando $n$ é ímpar, são necessárias $n$ cores: cada cor só pode ser usada para $(n - 1) / 2$ arestas, uma fração de $1 / n$ do total.

Vários autores estudaram as cores das bordas dos gráficos ímpares , $n-$ gráficos regulares em que os vértices representam equipes de $n - 1$ jogadores selecionados a partir de um pool de $2 n - 1$ jogadores, e em que as bordas representam possíveis emparelhamentos dessas equipes (com um jogador saiu como "estranho fora" para arbitrar o jogo). O caso em que $n = 3$ dá o conhecido gráfico de Petersen . Como Biggs (1972) explica o problema (para $n = 6$ ), os jogadores desejam encontrar um cronograma para esses pares de forma que cada equipe jogue cada uma de suas seis partidas em dias diferentes da semana, com folga aos domingos para todas as equipes; isto é, formalizando o problema matematicamente, eles desejam encontrar uma coloração de 6 arestas do gráfico ímpar 6-regular $O 6$ . Quando $n$ é 3, 4 ou 8, uma coloração de borda de $O n$ requer $n + 1$ cores, mas quando é 5, 6 ou 7, apenas $n$ cores são necessárias.

Definições

Tal como acontece com sua contraparte de vértice , uma coloração de aresta de um gráfico, quando mencionada sem qualquer qualificação, é sempre assumida como uma coloração adequada das arestas, significando que duas arestas adjacentes não têm a mesma cor. Aqui, duas arestas distintas são consideradas adjacentes quando compartilham um vértice comum. Uma aresta coloração de um gráfico $G$ também pode ser considerado como equivalente a um vértice coloração do gráfico de linha $G (G)$ , o gráfico que tem um vértice de cada ponta de $L$ e uma borda para cada par de bordas adjacentes em $L$ .

A margem adequada coloração com $k$ cores diferentes é chamado de (adequada) $k$ -Edge-coloração. Um gráfico ao qual pode ser atribuída uma coloração $k$ -edge é dito ser colorível com $k$ -edge. O menor número de cores necessárias para uma coloração (adequada) das arestas de um gráfico $G$ é o índice cromático , ou número cromático das arestas, $χ ' (G)$ . O índice cromático às vezes também é escrito usando a notação $χ 1 (G)$ ; nesta notação, o subscrito indica que as arestas são objetos unidimensionais. Um gráfico é $k$ -edge-cromático se seu índice cromático for exatamente $k$ . O índice cromática não deve ser confundido com o cromática número $χ (G)$ ou $χ 0 (G)$ , o número mínimo de cores necessárias em um vértice adequada coloração de $G$ .

A menos que indicado de outra forma, todos os gráficos são considerados simples, em contraste com multígrafos nos quais duas ou mais arestas podem estar conectando o mesmo par de pontos finais e nos quais pode haver auto-loops. Para muitos problemas de coloração de arestas, gráficos simples se comportam de maneira diferente de multigrafos, e cuidados adicionais são necessários para estender teoremas sobre coloração de arestas de gráficos simples para o caso de multigrafos.

Relação com correspondência

Este grafo planar 3-regular tem 16 vértices e 24 arestas, mas apenas 7 arestas em qualquer combinação máxima. Portanto, requer quatro cores em qualquer coloração de borda.

Uma correspondência em um grafo $G$ é um conjunto de arestas, nenhuma das quais adjacentes; uma correspondência perfeita é uma correspondência que inclui arestas tocando todos os vértices do gráfico, e uma correspondência máxima é uma correspondência que inclui tantas arestas quanto possível. Em uma coloração de arestas, o conjunto de arestas com qualquer cor deve ser não adjacente entre si, para que formem uma correspondência. Ou seja, uma coloração de aresta adequada é a mesma coisa que uma partição do gráfico em correspondências disjuntas.

Se o tamanho de uma correspondência máxima em um determinado gráfico for pequeno, muitas correspondências serão necessárias para cobrir todas as bordas do gráfico. Expresso de forma mais formal, esse raciocínio implica que se um gráfico tem $m$ arestas no total, e se no máximo $β$ arestas podem pertencer a um casamento máximo, então cada coloração de aresta do gráfico deve usar pelo menos $m / β$ cores diferentes. Por exemplo, o gráfico planar de 16 vértices mostrado na ilustração tem $m = 24$ arestas. Neste gráfico, não pode haver correspondência perfeita; pois, se o vértice central for correspondido, os vértices não correspondidos restantes podem ser agrupados em três componentes conectados diferentes com quatro, cinco e cinco vértices, e os componentes com um número ímpar de vértices não podem ser combinados perfeitamente. No entanto, o gráfico possui correspondências máximas com sete arestas, então $β = 7$ . Portanto, o número de cores necessárias para colorir o gráfico é de pelo menos 24/7 e, como o número de cores deve ser um inteiro, é pelo menos quatro.

Para um gráfico regular de grau $k$ que não tem uma correspondência perfeita, esse limite inferior pode ser usado para mostrar que pelo menos $k + 1$ cores são necessárias. Em particular, isso é verdade para um gráfico regular com um número ímpar de vértices (como os gráficos completos ímpares); para tais gráficos, pelo lema do aperto de mão , o próprio $k$ deve ser par. No entanto, a desigualdade $χ ' \geq m / β$ não explica totalmente o índice cromático de todos os gráficos regulares, porque há gráficos regulares que têm correspondências perfeitas, mas não podem ser coloridos com k -edge. Por exemplo, o gráfico de Petersen é regular, com $m = 15$ e com $β = 5$ arestas em suas combinações perfeitas, mas não possui uma coloração de 3 arestas.

Relação com o grau

Teorema de Vizing

O número cromática borda de um gráfico $G$ é muito intimamente relacionado com o grau máximo $Δ (L)$ , o maior número de arestas incidente para qualquer único vértice do $L$ . Claramente, $χ ' (G) \geq Δ (G)$ , pois se $Δ$ arestas diferentes se encontram no mesmo vértice $v$ , então todas essas arestas precisam ter cores diferentes entre si, e isso só pode ser possível se houver pelo menos $Δ$ cores disponíveis para serem atribuídas. O teorema de Vizing (nomeado em homenagem a Vadim G. Vizing que o publicou em 1964) afirma que esse limite é quase estreito: para qualquer gráfico, o número cromático da aresta é $Δ (G)$ ou $Δ (G) + 1$ . Quando $χ ' (G) = Δ (G)$ , diz-se que G é da classe 1; caso contrário, é considerado da classe 2.

Todo grafo bipartido é da classe 1, e quase todos os grafos aleatórios são da classe 1. No entanto, é NP-completo determinar se um grafo arbitrário é da classe 1.

Vizing (1965) provou que os grafos planares de grau máximo de pelo menos oito são de classe um e conjecturou que o mesmo é verdade para grafos planares de grau máximo de sete ou seis. Por outro lado, existem gráficos planares de grau máximo variando de dois a cinco que são de classe dois. A conjectura já foi comprovada para gráficos de grau máximo sete. Os gráficos cúbicos planos sem ponte são todos da classe 1; esta é uma forma equivalente do teorema das quatro cores .

Gráficos regulares

Uma 1-fatoração de um k - gráfico regular , uma partição das arestas do gráfico em combinações perfeitas , é a mesma coisa que uma k -coloração das arestas do gráfico. Ou seja, um gráfico regular tem uma fatoração 1 se e somente se for da classe 1. Como um caso especial disso, uma coloração de 3 arestas de um gráfico cúbico (3-regular) é às vezes chamada de coloração Tait .

Nem todo gráfico regular tem uma fatoração de 1; por exemplo, o gráfico de Petersen não. De maneira mais geral, os trechos são definidos como os gráficos que, como o gráfico de Petersen, são sem ponte, 3-regulares e de classe 2.

De acordo com o teorema de Kőnig (1916) , todo grafo regular bipartido possui uma fatoração-1. O teorema foi afirmado anteriormente em termos de configurações projetivas e foi comprovado por Ernst Steinitz .

Multigraphs

Um multigrafo de Shannon com grau seis e multiplicidade de arestas três, exigindo nove cores em qualquer coloração de aresta

Para multigrafos , nos quais várias arestas paralelas podem conectar os mesmos dois vértices, os resultados que são semelhantes, mas mais fracos que o teorema de Vizing, são conhecidos relacionando o número cromático da aresta $χ ' (G)$ , o grau máximo $Δ (G)$ e a multiplicidade $μ (G)$ , o número máximo de arestas em qualquer feixe de arestas paralelas. Como um exemplo simples que mostra que o teorema de Vizing não generaliza para multigrafos, considere um multigrafo de Shannon , um multigrafo com três vértices e três feixes de $μ (G)$ arestas paralelas conectando cada um dos três pares de vértices. Neste exemplo, $Δ (G) = 2μ (G)$ (cada vértice incide em apenas dois dos três feixes de $μ (G)$ arestas paralelas), mas o número cromático da aresta é $3μ (G)$ (há $3μ (G))$ arestas no total, e cada duas arestas são adjacentes, portanto, todas as arestas devem receber cores diferentes entre si). Em resultado que inspirou Vizing, Shannon (1949) mostraram que este é o pior caso: $χ '(G) \leq (3/2) Δ (L)$ para qualquer multigrafo $L$ . Além disso, para qualquer multigrafo $G$ , $χ ' (G) \leq Δ (G) + μ (G)$ , uma desigualdade que se reduz ao teorema de Vizing no caso de gráficos simples (para os quais $μ (G) = 1$ ).

Algoritmos

Como o problema de testar se um gráfico é de classe 1 é NP-completo , não há algoritmo de tempo polinomial conhecido para colorir cada gráfico com um número ótimo de cores. No entanto, vários algoritmos foram desenvolvidos que relaxam um ou mais desses critérios: eles funcionam apenas em um subconjunto de gráficos, ou nem sempre usam um número ótimo de cores, ou nem sempre funcionam em tempo polinomial.

Colorir classes especiais de gráficos de maneira ideal

No caso de gráficos bipartidos ou multigrafos com grau máximo $Δ$ , o número ótimo de cores é exatamente $Δ$ . Cole, Ost & Schirra (2001) mostraram que uma coloração ótima das arestas desses gráficos pode ser encontrada no limite de tempo quase linear $O (m log Δ)$ , onde $m$ é o número de arestas no gráfico; algoritmos mais simples, mas um pouco mais lentos, são descritos por Cole & Hopcroft (1982) e Alon (2003) . O algoritmo de Alon (2003) começa tornando o grafo de entrada regular, sem aumentar seu grau ou aumentar significativamente seu tamanho, mesclando pares de vértices que pertencem ao mesmo lado da bipartição e, em seguida, adicionando um pequeno número de vértices e arestas adicionais . Então, se o grau for ímpar, Alon encontra uma única combinação perfeita em um tempo quase linear, atribui a ela uma cor e a remove do gráfico, fazendo com que o grau se torne par. Finalmente, Alon aplica uma observação de Gabow (1976) , que selecionar subconjuntos alternados de arestas em um passeio de Euler do gráfico o divide em dois subgráficos regulares, para dividir o problema de coloração de arestas em dois subproblemas menores, e seu algoritmo resolve os dois subproblemas recursivamente . O tempo total para seu algoritmo é $O (m log m)$ .

Para gráficos planares com grau máximo $Δ \geq 7$ , o número ótimo de cores é novamente exatamente $Δ$ . Com a suposição mais forte de que $Δ \geq 9$ , é possível encontrar uma coloração de aresta ótima no tempo linear ( Cole & Kowalik 2008 ).

Para grafos d-regulares que são pseudo-aleatórios no sentido de que sua matriz de adjacência tem o segundo maior autovalor (em valor absoluto) no máximo $d 1 - ε$ , d é o número ótimo de cores ( Ferber & Jain 2018 ).

Algoritmos que usam mais do que o número ideal de cores

Misra & Gries (1992) e Gabow et al. (1985) descrevem algoritmos de tempo polinomial para colorir qualquer gráfico com $Δ + 1$ cores, atendendo ao limite dado pelo teorema de Vizing; veja o algoritmo de coloração de bordas de Misra & Gries .

Para multigrafos, Karloff & Shmoys (1987) apresentam o seguinte algoritmo, que atribuem a Eli Upfal . Faça o multigrafo de entrada $G$ Euleriano adicionando um novo vértice conectado por uma aresta a cada vértice de grau ímpar, encontre um passeio de Euler e escolha uma orientação para o passeio. Forme um grafo bipartido $H$ no qual existem duas cópias de cada vértice de $G$ , uma em cada lado da bipartição, com uma aresta de um vértice $u$ no lado esquerdo da bipartição para um vértice $v$ no lado direito da bipartição sempre que o passeio orientada tem uma aresta de $u$ para $v$ em $L$ . Aplicar um algoritmo de coloração borda gráfico bipartido para $H$ . Cada classe de cor em $H$ corresponde a um conjunto de arestas em $G$ que formam um subgrafo com grau máximo dois; isto é, uma união disjuntos de caminhos e ciclos, de modo que para cada classe de cor em $H$ é possível formar três classes de cor em $L$ . O tempo para o algoritmo é limitado pelo tempo para colorir as bordas de um grafo bipartido, $O (m log Δ)$ usando o algoritmo de Cole, Ost & Schirra (2001) . O número de cores que esse algoritmo usa é no máximo próximo, mas não exatamente igual ao limite de Shannon . Ele também pode ser transformado em um algoritmo paralelo de maneira direta. No mesmo artigo, Karloff e Shmoys também apresentam um algoritmo de tempo linear para colorir multígrafos de grau máximo três com quatro cores (combinando os limites de Shannon e Vizing) que opera em princípios semelhantes: seu algoritmo adiciona um novo vértice para tornar o grafo euleriano, encontra um passeio de Euler e, em seguida, escolhe conjuntos alternados de arestas no passeio para dividir o gráfico em dois subgráficos de grau dois no máximo. Os caminhos e até mesmo os ciclos de cada subgrafo podem ser coloridos com duas cores por subgrafo. Após esta etapa, cada ciclo ímpar restante contém pelo menos uma aresta que pode ser colorida com uma das duas cores pertencentes ao subgrafo oposto. A remoção dessa aresta do ciclo ímpar deixa um caminho, que pode ser colorido usando as duas cores para seu subgrafo. ${\ displaystyle 3 \ left \ lceil {\ frac {\ Delta} {2}} \ right \ rceil}$ ${\ displaystyle \ left \ lfloor {\ frac {3 \ Delta} {2}} \ right \ rfloor}$

Um algoritmo de coloração ganancioso que considera as arestas de um gráfico ou multigrafo uma por uma, atribuindo a cada aresta a primeira cor disponível , às vezes pode usar até $2Δ - 1$ cores, que podem ser quase o dobro do número de cores necessário. No entanto, tem a vantagem de poder ser usado na configuração do algoritmo online em que o gráfico de entrada não é conhecido com antecedência; neste cenário, sua razão competitiva é dois, e isso é ótimo: nenhum outro algoritmo online pode atingir um desempenho melhor. No entanto, se as arestas chegam em uma ordem aleatória, e o gráfico de entrada tem um grau que é pelo menos logarítmico, taxas competitivas menores podem ser alcançadas.

Vários autores fizeram conjecturas que implicam que o índice cromático fracionário de qualquer multigrafo (um número que pode ser calculado em tempo polinomial usando programação linear ) está dentro de um dos índices cromáticos. Se essas conjecturas forem verdadeiras, seria possível calcular um número que nunca está mais do que um fora do índice cromático no caso multigrafo, combinando o que é conhecido por meio do teorema de Vizing para gráficos simples. Embora não provadas em geral, essas conjecturas são conhecidas por se manterem quando o índice cromático é pelo menos , como pode acontecer para multígrafos com multiplicidade suficientemente grande. ${\ displaystyle \ Delta + {\ sqrt {\ Delta / 2}}}$

Algoritmos exatos

É simples testar se um gráfico pode ser colorido pelas bordas com uma ou duas cores, então o primeiro caso não trivial de coloração das bordas é testar se um gráfico tem uma coloração com 3 bordas. Como Kowalik (2009) mostrou, é possível testar se um gráfico tem uma coloração de 3 arestas no tempo $O (1,344 n)$ , usando apenas o espaço polinomial. Embora esse limite de tempo seja exponencial, é significativamente mais rápido do que uma pesquisa de força bruta em todas as atribuições possíveis de cores às bordas. Cada gráfico 3-regular bicconectado com $n$ vértices tem $O (2 n / 2)$ coloração de 3 arestas; todos os quais podem ser listados no tempo $O (2 n / 2)$ (um pouco mais lento do que o tempo para encontrar uma única coloração); como Greg Kuperberg observou, o gráfico de um prisma sobre um polígono de $n / 2$ lados tem $Ω (2 n / 2)$ colorações (limite inferior em vez de limite superior), mostrando que esse limite é estreito.

Aplicando algoritmos exatos para coloração de vértices ao gráfico de linha do gráfico de entrada, é possível colorir de forma otimizada qualquer gráfico com $m$ arestas, independentemente do número de cores necessárias, em tempo $2 m m O (1)$ e espaço exponencial , ou no tempo $O (2,2461 m)$ e apenas no espaço polinomial ( Björklund, Husfeldt & Koivisto 2009 ).

Como a coloração das bordas é NP-completa mesmo para três cores, é improvável que seja um parâmetro fixo tratável quando parametrizado pelo número de cores. No entanto, é tratável para outros parâmetros. Em particular, Zhou, Nakano & Nishizeki (1996) mostraram que para gráficos de largura de árvore $w$ , uma coloração de aresta ótima pode ser calculada no tempo $O (nw (6 w) w (w + 1) / 2)$ , um limite que depende superexponencialmente em $w,$ mas apenas linearmente no número $n$ de vértices no gráfico.

Nemhauser & Park (1991) formulam o problema de coloração de arestas como um programa de inteiros e descrevem sua experiência usando um solucionador de programação de inteiros para gráficos de cores de arestas. No entanto, eles não realizaram nenhuma análise de complexidade de seu algoritmo.

Propriedades Adicionais

O gráfico de Petersen generalizado com três cores,

G (9,2)

. Uma de suas três classes de cores é mostrada pelas bordas claras e as outras duas podem ser encontradas girando as bordas claras em 40 ° em cada direção ou particionando o ciclo hamiltoniano escuro em bordas alternadas.

Um gráfico pode ser colorido exclusivamente com $k$ se houver apenas uma maneira de particionar as arestas em $k$ classes de cores, ignorando o $k!$ possíveis permutações das cores. Para $k \neq 3$ , os únicos gráficos com $k$ -edge para colorir são caminhos, ciclos e estrelas , mas para $k = 3$ outros gráficos também podem ser para $k$ -edge com exclusividade . Cada gráfico com três arestas para colorir com exclusividade tem exatamente três ciclos hamiltonianos (formados pela exclusão de uma das três classes de cores), mas existem gráficos 3-regulares que têm três ciclos hamiltonianos e não são exclusivamente 3-coloráveis, como os gráficos de Petersen generalizados $G (6 n + 3, 2)$ para $n \geq 2$ . O único gráfico conhecido não planar unicamente com três cores é o gráfico de Petersen generalizado $G (9,2)$ , e foi conjecturado que nenhum outro existe.

O grafo bipartido completo K _3,3 com cada uma de suas classes de cores desenhadas como segmentos de linha paralelos em linhas distintas.

Folkman & Fulkerson (1969) investigaram as sequências não crescentes de números $m 1, m 2, m 3, ...$ com a propriedade de que existe uma coloração adequada das arestas de um dado grafo $G$ com $m 1$ arestas da primeira cor, $m 2$ arestas da segunda cor, etc. Eles observaram que, se uma sequência $P$ é viável nesse sentido, e é maior em ordem lexicográfica do que uma sequência $Q$ com a mesma soma, então $Q$ também é viável. Pois, se $P > Q$ em ordem lexicográfica, então $P$ pode ser transformado em $Q$ por uma sequência de etapas, cada uma das quais reduz um dos números $m i$ em uma unidade e aumenta outro número posterior $m j$ com $i < j$ em uma unidade . Em termos de coloração das bordas, partindo de uma coloração que realiza $P$ , cada uma dessas mesmas etapas pode ser realizada trocando as cores $i$ e $j$ em uma cadeia Kempe , um caminho máximo de bordas que se alternam entre as duas cores. Em particular, qualquer gráfico tem uma coloração de borda equitativa , uma coloração de borda com um número ótimo de cores em que cada duas classes de cores diferem em tamanho em no máximo uma unidade.

O teorema De Bruijn – Erdős pode ser usado para transferir muitas propriedades de coloração de arestas de grafos finitos para grafos infinitos . Por exemplo, os teoremas de Shannon e Vizing relacionando o grau de um gráfico a seu índice cromático generalizam diretamente para gráficos infinitos.

Richter (2011) considera o problema de encontrar um desenho de gráfico de um dado grafo cúbico com as propriedades de que todas as arestas no desenho têm uma das três inclinações diferentes e que não há duas arestas na mesma linha que a outra. Se tal desenho existir, então claramente as inclinações das arestas podem ser usadas como cores em uma coloração de 3 arestas do gráfico. Por exemplo, o desenho do gráfico de utilidade $K 3,3$ como as arestas e diagonais longas de um hexágono regular representa uma coloração de 3 arestas do gráfico desta forma. Como mostra Richter, um grafo bipartido simples 3-regular, com uma determinada coloração Tait, tem um desenho desse tipo que representa a coloração dada se e somente se o gráfico for conectado por 3 arestas . Para um grafo não bipartido, a condição é um pouco mais complicada: uma dada coloração pode ser representada por um desenho se a capa dupla bipartida do gráfico for conectada por 3 arestas, e se a exclusão de qualquer par monocromático de arestas levar a um subgrafo que ainda não é bipartido. Todas essas condições podem ser testadas facilmente em tempo polinomial; no entanto, o problema de testar se um gráfico 4-regular colorido de 4 arestas tem um desenho com arestas de quatro inclinações, representando as cores por inclinações, está completo para a teoria existencial dos reais , uma classe de complexidade pelo menos tão difícil quanto sendo NP-completo.

Além de estar relacionado ao grau máximo e ao número máximo de correspondência de um gráfico, o índice cromático está intimamente relacionado à arboricidade linear $la (G)$ de um gráfico $G$ , o número mínimo de florestas lineares (uniões disjuntas de caminhos) nas quais as bordas do gráfico podem ser particionadas. Uma correspondência é um tipo especial de floresta linear, e na outra direção, qualquer floresta linear pode ser colorida com 2 arestas, então para cada $G$ segue que $la (G) \leq χ ' (G) \leq 2 la (G)$ . A conjectura de Akiyama (nomeada em homenagem a Jin Akiyama ) afirma que , da qual se seguiria mais fortemente que $2 la ($ $G$ $) - 2 \leq χ ' ($ $G$ $) \leq 2 la ($ $G$ $)$ . Para gráficos de grau máximo três, $la ($ $G$ $)$ é sempre exatamente dois, então, neste caso, o limite $χ ' ($ $G$ $) \leq 2 la ($ $G$ $)$ corresponde ao limite dado pelo teorema de Vizing. ${\ displaystyle \ mathop {\ mathrm {la}} (G) \ leq \ left \ lceil {\ frac {\ Delta +1} {2}} \ right \ rceil}$

Outros tipos

Uma partição do grafo bipartido completo K _4,4 em três florestas, mostrando que ele possui três arboricidade.

O número Thue de um gráfico é o número de cores necessárias em uma coloração de borda que atende ao requisito mais forte de que, em cada caminho de comprimento par, a primeira e a segunda metades do caminho formam diferentes sequências de cores.

A arboricidade de um gráfico é o número mínimo de cores necessárias para que as arestas de cada cor não tenham ciclos (em vez de, no problema de coloração de arestas padrão, não ter pares adjacentes de arestas). Ou seja, é o número mínimo de florestas nas quais as arestas do gráfico podem ser particionadas. Ao contrário do índice cromático, a arboricidade de um gráfico pode ser calculada em tempo polinomial.

A coloração de arestas de lista é um problema em que é dado um gráfico em que cada aresta está associada a uma lista de cores, e deve-se encontrar uma coloração de arestas apropriada em que a cor de cada aresta é tirada da lista daquela aresta. O índice cromático da lista de um grafo $G$ é o menor número $k$ com a propriedade de que, não importa como se escolha listas de cores para as arestas, desde que cada aresta tenha pelo menos $k$ cores em sua lista, então uma coloração é garantida para seja possível. Assim, o índice cromático da lista é sempre pelo menos tão grande quanto o índice cromático. A conjectura de Dinitz sobre o preenchimento de quadrados latinos parciais pode ser reformulada como a afirmação de que o número cromático da aresta da lista do grafo bipartido completo $K n, n$ é igual ao número cromático da aresta, $n$ . Galvin (1995) resolveu a conjectura provando, de forma mais geral, que em todo gráfico bipartido o índice cromático e o índice cromático da lista são iguais. A igualdade entre o índice cromático e o índice cromático de lista foi conjecturada para se manter, ainda mais geralmente, para multigrafos arbitrários sem auto-loops; esta conjectura permanece aberta.

Muitas outras variações comumente estudadas de coloração de vértices também foram estendidas para colorações de arestas. Por exemplo, a coloração de bordas completa é a variante de coloração de bordas da coloração completa , uma coloração de bordas apropriada em que cada par de cores deve ser representado por pelo menos um par de bordas adjacentes e em que o objetivo é maximizar o número total de cores . Coloração de borda forte é a variante de coloração de borda de coloração forte , uma coloração de borda em que cada duas bordas com pontos de extremidade adjacentes devem ter cores diferentes. A coloração de borda forte tem aplicações em esquemas de alocação de canal para redes sem fio .

Coloração de borda acíclica é a variante de coloração de borda da coloração acíclica , uma coloração de borda para a qual cada duas classes de cor formam um subgrafo acíclico (ou seja, uma floresta). O índice cromático acíclico de um gráfico , denotado por , é o menor número de cores necessárias para ter uma coloração de aresta acíclica adequada . Foi conjecturado que , onde está o grau máximo de . Atualmente, o limite mais conhecido é . O problema fica mais fácil quando tem grande circunferência . Mais especificamente, existe uma constante tal que, se a circunferência de for pelo menos , então . Um resultado semelhante é que para todos existe um tal que se tenha pelo menos circunferência , então . ${\ displaystyle G}$ ${\ displaystyle a '(G)}$ ${\ displaystyle G}$ ${\ displaystyle a '(G) \ leq \ Delta +2}$ ${\ displaystyle \ Delta}$ ${\ displaystyle G}$ ${\ displaystyle a '(G) \ leq \ lceil 3,74 (\ Delta -1) \ rceil}$ ${\ displaystyle G}$ ${\ displaystyle c}$ ${\ displaystyle G}$ ${\ displaystyle c \ Delta \ log \ Delta}$ ${\ displaystyle a '(G) \ leq \ Delta +2}$ ${\ displaystyle \ epsilon> 0}$ ${\ displaystyle g}$ ${\ displaystyle G}$ ${\ displaystyle g}$ ${\ displaystyle a '(G) \ leq (1+ \ epsilon) \ Delta}$

Eppstein (2013) estudou colorações de 3 arestas de gráficos cúbicos com a propriedade adicional de que dois ciclos bicromáticos não compartilham mais do que uma única aresta. Ele mostrou que a existência de tal coloração equivale à existência de um desenho do gráfico em uma grade tridimensional inteira, com arestas paralelas aos eixos coordenados e cada linha paralela ao eixo contendo no máximo dois vértices. No entanto, como o problema padrão de coloração de 3 arestas, encontrar uma coloração desse tipo é NP-completo.

A coloração total é uma forma de coloração que combina a coloração dos vértices e das arestas, exigindo que os vértices e as arestas sejam coloridos. Qualquer par incidente de um vértice e uma aresta, ou uma aresta e uma aresta, deve ter cores distintas, assim como quaisquer dois vértices adjacentes. Foi conjecturado (combinando o teorema de Vizing e o teorema de Brooks ) que qualquer gráfico tem uma coloração total em que o número de cores é no máximo o grau máximo mais dois, mas isso permanece não comprovado.

Se um gráfico 3-regular em uma superfície é colorido com 3 arestas, seu gráfico duplo forma uma triangulação da superfície que também é colorida nas arestas (embora não, em geral, corretamente colorida nas arestas) de tal forma que cada triângulo tem um borda de cada cor. Outras cores e orientações de triangulações, com outras restrições locais sobre como as cores são organizadas nos vértices ou faces da triangulação, podem ser usadas para codificar vários tipos de objetos geométricos. Por exemplo, subdivisões retangulares (partições de uma subdivisão retangular em retângulos menores, com três retângulos se encontrando em cada vértice) podem ser descritas combinatorialmente por uma "marcação regular", uma coloração dupla das bordas de uma triangulação dupla para a subdivisão, com a restrição de que as arestas incidentes em cada vértice formem quatro subseqüências contíguas, em cada uma das quais as cores são iguais. Essa rotulagem é dupla a uma coloração da própria subdivisão retangular em que as bordas verticais têm uma cor e as bordas horizontais têm outra cor. Restrições locais semelhantes na ordem em que as bordas coloridas podem aparecer em torno de um vértice também podem ser usadas para codificar embeddings de grade em linha reta de gráficos planares e poliedros tridimensionais com lados paralelos ao eixo. Para cada um desses três tipos de rótulos regulares, o conjunto de rótulos regulares de um gráfico fixo forma uma rede distributiva que pode ser usada para listar rapidamente todas as estruturas geométricas com base no mesmo gráfico (como todos os poliedros paralelos ao eixo com o mesmo esqueleto ) ou para encontrar estruturas que satisfaçam restrições adicionais.

Um autômato finito determinístico pode ser interpretado como um grafo direcionado no qual cada vértice tem o mesmo grau de saída $d$ , e no qual as arestas são $d-$ coloridas de tal forma que cada duas arestas com o mesmo vértice de origem têm cores distintas. O problema da coloração de estradas é o problema de coloração de arestas de um grafo direcionado com graus externos uniformes, de tal forma que o autômato resultante tenha uma palavra de sincronização . Trahtman (2009) resolveu o problema de coloração de estradas provando que tal coloração pode ser encontrada sempre que o gráfico fornecido for fortemente conectado e aperiódico .

O teorema de Ramsey diz respeito ao problema de $k -$ colorir as arestas de um grafo completo grande $K n$ para evitar a criação de subgrafos completos monocromáticos $K s$ de algum tamanho $s$ . De acordo com o teorema, existe um número $R k (s)$ tal que, sempre que $n \geq R (s)$ , tal coloração não é possível. Por exemplo, $R 2 (3) = 6$ , ou seja, se as arestas do gráfico $K 6$ forem bicolores, sempre haverá um triângulo monocromático.

Um caminho em um gráfico com cores de aresta é considerado um caminho de arco - íris se nenhuma cor se repetir nele. Diz-se que um gráfico tem a cor do arco-íris se houver um caminho de arco-íris entre quaisquer dois pares de vértices. Uma coloração de arestas de um gráfico G com cores 1.. . t é um intervalo t de coloração se todas as cores são usadas, e as cores das arestas incidentes em cada vértice de G são distintas e formam um intervalo de inteiros.

Formulários

A coloração das bordas dos gráficos completos pode ser usada para agendar um torneio round-robin no menor número possível de rodadas, de modo que cada par de competidores jogue entre si em uma das rodadas; nesta aplicação, os vértices do gráfico correspondem aos competidores no torneio, as bordas correspondem aos jogos e as cores das bordas correspondem às rodadas em que os jogos são disputados. Técnicas de coloração semelhantes também podem ser usadas para programar outros pares de esportes que não sejam todos-play-all; por exemplo, na National Football League , os pares de times que se enfrentarão em um determinado ano são determinados, com base nos registros dos times do ano anterior, e então um algoritmo de coloração de arestas é aplicado ao gráfico formado pelo conjunto de emparelhamentos para atribuir jogos aos fins de semana em que são disputados. Para esta aplicação, o teorema de Vizing implica que independentemente do conjunto de pares escolhido (desde que nenhuma equipe jogue uma contra a outra duas vezes na mesma temporada), é sempre possível encontrar uma programação que usa no máximo um fim de semana a mais do que há jogos por equipe.

A programação de loja aberta é um problema de programação de processos de produção , em que existe um conjunto de objetos a serem fabricados, cada objeto possui um conjunto de tarefas a serem realizadas nele (em qualquer ordem), e cada tarefa deve ser realizada em um determinado máquina, evitando que qualquer outra tarefa que exija que a mesma máquina seja executada ao mesmo tempo. Se todas as tarefas têm o mesmo comprimento, então este problema pode ser formalizado como um de coloração de arestas de um multigrafo bipartido, em que os vértices de um lado da bipartição representam os objetos a serem fabricados, os vértices do outro lado da bipartição representam Nas máquinas de manufatura, as bordas representam tarefas que devem ser executadas e as cores representam etapas de tempo em que cada tarefa pode ser executada. Uma vez que a coloração da borda bipartida pode ser realizada em tempo polinomial, o mesmo é verdadeiro para este caso restrito de programação de loja aberta.

Gandham, Dawande e Prakash (2005) estudam o problema de escalonamento de link para protocolos de comunicação de rede de acesso múltiplo por divisão de tempo em redes de sensores como uma variante da coloração de arestas. Neste problema, deve-se escolher intervalos de tempo para as bordas de uma rede de comunicação sem fio de forma que cada nó da rede possa se comunicar com cada nó vizinho sem interferência. Usar uma coloração de borda forte (e usar dois slots de tempo para cada cor de borda, um para cada direção) resolveria o problema, mas pode usar mais slots de tempo do que o necessário. Em vez disso, eles buscam uma coloração do grafo direcionado formado pela duplicação de cada aresta não direcionada da rede, com a propriedade de que cada aresta direcionada $uv$ tem uma cor diferente das arestas que saem de $v$ e dos vizinhos de $v$ . Eles propõem uma heurística para este problema baseada em um algoritmo distribuído para $(Δ + 1)$ - coloração das bordas junto com uma fase de pós-processamento que reprograma as bordas que podem interferir umas nas outras.

Na comunicação de fibra óptica , o problema de coloração do caminho é o problema de atribuição de cores (frequências de luz) a pares de nós que desejam se comunicar entre si, e caminhos através de uma rede de comunicações de fibra óptica para cada par, sujeito à restrição que nenhum dos dois caminhos que compartilham um segmento de fibra use a mesma frequência um do outro. Os caminhos que passam pelo mesmo switch de comunicação, mas não por qualquer segmento de fibra, podem usar a mesma frequência. Quando a rede de comunicações é organizada como uma rede em estrela , com um único switch central conectado por fibras separadas a cada um dos nós, o problema de coloração do caminho pode ser modelado exatamente como um problema de coloração das bordas de um gráfico ou multigrafo, no qual os nós de comunicação formam os vértices do grafo, pares de nós que desejam se comunicar das arestas do grafo e as frequências que podem ser usadas para cada par formam as cores do problema de coloração das arestas. Para redes de comunicação com uma topologia de árvore mais geral, as soluções de coloração de caminho local para as redes em estrela definidas por cada switch na rede podem ser conectadas para formar uma única solução global.

Problemas abertos

Jensen & Toft (1995) listam 23 problemas em aberto relativos à coloração de arestas. Eles incluem:

A conjectura de Goldberg (1973) de que o índice cromático e o índice fracionário estão dentro um do outro, o que permitiria que o índice cromático fosse aproximado dentro de uma cor em tempo polinomial.
Várias conjecturas de Jakobsen e outros sobre a estrutura de gráficos críticos para coloração de arestas, gráficos de classe 2, de modo que qualquer subgrafo tem grau máximo menor ou é de classe 1. Jakobsen conjecturou originalmente que todos os gráficos críticos têm um número ímpar de vértices, mas isso acabou sendo refutado. Várias outras conjecturas enfraquecendo esta, ou limitando o número de vértices de gráficos críticos e multigrafos críticos, permanecem abertas.
O problema de Vizing de classificar os graus máximos possíveis para gráficos planares de classe 2.
A conjectura do subgrafo overfull de AJW Hilton, afirmando que os grafos com grau pelo menos $n / 3$ sao da classe 1 ou contem um subgrafo com o mesmo grau $Δ$ que o grafico original, e com um numero $k$ ímpar de vértices, tal que o número de arestas no subgrafo é maior que $Δ (k - 1) / 2$ , e uma conjectura semelhante por Herbert Grötzsch e Paul Seymour sobre grafos planares no lugar de grafos de alto grau.
Uma conjectura de Amanda Chetwynd e Anthony Hilton (possivelmente voltando antes ao trabalho de Gabriel Andrew Dirac ) de que os gráficos regulares com um número par $n$ de vértices e com grau pelo menos $n / 2$ são da classe 1.
Uma conjectura de Claude Berge e DR Fulkerson de que os multigráficos 6-regulares formados pela duplicação de todas as arestas de um gráfico simples 3-regular sem ponte podem ser coloridos nas arestas com seis cores.
Uma conjectura de Fiorini e Wilson de que todo gráfico planar livre de triângulos , exceto a garra K _1,3 , não pode ser colorido exclusivamente com 3 arestas .
Uma conjectura de 2012 de que se $G$ é um multigrafo planar $d-$ regular, então $G pode$ ser colorido com $d$ -edge se e somente se $G$ for estranhamente conectado com $d$ -edge. Esta conjectura é uma generalização do teorema das quatro cores , que surge em $d$ = 3. Maria Chudnovsky , Katherine Edwards e Paul Seymour provaram que um multigrafo planar regular de 8 tem um número cromático de aresta de 8.

Notas

Referências

Akiyama, Jin; Exoo, Geoffrey; Harary, Frank (1980), "Covering and packing in graphs. III. Cyclic and acyclic invariants", Mathematica Slovaca , 30 (4): 405-417, MR 0595302.
Alon, Noga (2003), "A simple algorithm for edge-colouring bipartite multigraphs", Information Processing Letters , 85 (6): 301–302, doi : 10.1016 / S0020-0190 (02) 00446-5 , MR 1956451.
Alon, Noga ; Sudakov, Benny; Zaks, Ayal (2001), "Acyclic edge colorings of graphs", Journal of Graph Theory , 37 (3): 157-167, doi : 10.1002 / jgt.1010 , MR 1837021.
Andersen, Lars Døvling (1977), "On edge-colorings of graphs", Mathematica Scandinavica , 40 (2): 161-175, doi : 10.7146 / math.scand.a-11685 , MR 0465922. Conforme citado por Chen, Yu & Zang (2011) .
Appel, K .; Haken, W. (1976), "Every planar map is four colorable", Bulletin of the American Mathematical Society , 82 (5): 711–712, doi : 10.1090 / S0002-9904-1976-14122-5 , MR 0424602.
Bahmani, Bahman; Mehta, Aranyak; Motwani, Rajeev (2010), "Um algoritmo de coloração de arestas de grafos on-line de 1,43 competitivo no modelo de chegada de ordem aleatória", Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '10) , pp. 31-39.
Bar-Noy, Amotz; Motwani, Rajeev ; Naor, Joseph (1992), "O algoritmo ganancioso é ideal para coloração de arestas on-line", Information Processing Letters , 44 (5): 251–253, doi : 10.1016 / 0020-0190 (92) 90209-E.
Barrett, CL; Istrate, G .; Kumar, VSA; Marathe, MV; Thite, S .; Thulasidasan, S. (2006), "Coloração de borda forte para atribuição de canal em redes de rádio sem fio", Proc. Quarta Conferência Internacional Anual IEEE sobre Computação Pervasiva e Workshops de Comunicações (PerCom Workshops 2006) , p. 106, doi : 10.1109 / PERCOMW.2006.129 , ISBN 0-7695-2520-2, S2CID 5797236.
Biggs, Norman (1972), Guy, Richard K. (ed.), "An edge-colouring problem", Research Problems, American Mathematical Monthly , 79 (9): 1018–1020, doi : 10.2307 / 2318076 , JSTOR 2318076.
Biggs, Norman (1979), "Some odd graph theory", Second International Conference on Combinatorial Mathematics, Annals of the New York Academy of Sciences , 319 (1): 71-81, Bibcode : 1979NYASA.319 ... 71B , doi : 10.1111 / j.1749-6632.1979.tb32775.x , S2CID 84995087.
Björklund, Andreas; Husfeldt, Thore; Koivisto, Mikko (2009), "Set particionamento via inclusão-exclusão" (PDF) , SIAM Journal on Computing , 39 (2): 546–563, doi : 10.1137 / 070683933 , MR 2529771.
Bosák, Juraj (1972), "Chromatic index of finite and infinite graphs", Czechoslovak Mathematical Journal , 22 (97): 272–290, doi : 10.21136 / CMJ.1972.101098 , MR 0309777.
Bosák, Juraj; Nešetřil, Jaroslav (1976), "Complete and pseudocomplete colorings of a graph", Matematicky Časopis Slovenskej Akadémie Vied , 26 (3): 171–184, MR 0439672.
Cai, XS; Perarnau, G .; Reed, BA ; Watts, AB (2014), "Acyclic edge colorings of graphs with large girth", Random Structures & Algorithms , 50 (4): 511–533, arXiv : 1411.3047 , doi : 10.1002 / rsa.20695 , S2CID 7727097.
Burke, E .; De Werra, D .; Kingston, J. (2004), "5.6.5 Sports Timetabling" , em JL, Gross; Yellen, J. (eds.), Handbook of Graph Theory , CRC Press, p. 462, ISBN 978-1-58488-090-5.
Chen, Guantao; Yu, Xingxing; Zang, Wenan (2011), "Approximating the cromática index of multigraphs", Journal of Combinatorial Optimization , 21 (2): 219–246, doi : 10.1007 / s10878-009-9232-y , MR 2770056 , S2CID 169162.
Chudnovsky, Maria ; Edwards, Katherine; Seymour, Paul (2012), "Edge-colouring eight-regular planar graphs", arXiv : 1209.1176 [ cs.DM ].
Cole, Richard; Hopcroft, John (1982), "On edge coloring bipartite graphs", SIAM Journal on Computing , 11 (3): 540-546, doi : 10.1137 / 0211043 , hdl : 1813/6283 , MR 0664720.
Cole, Richard; Kowalik, Łukasz (2008), "New linear-time algoritms for edge-colouring planar graphs", Algorithmica , 50 (3): 351–368, doi : 10.1007 / s00453-007-9044-3 , MR 2366985 , S2CID 7692895.
Cole, Richard; Ost, Kirstin; Schirra, Stefan (2001), "Edge-colouring bipartite multigraphs in $O (E log D)$ time", Combinatorica , 21 (1): 5-12, doi : 10.1007 / s004930170002 , MR 1805711 , S2CID 522145.
Cranston, Daniel W. (2006), "Coloração de aresta forte de gráficos com grau máximo 4 usando 22 cores", Discrete Mathematics , 306 (21): 2772-2778, arXiv : math / 0601623 , Bibcode : 2006math .... ..1623C , doi : 10.1016 / j.disc.2006.03.053 , MR 2264374 , S2CID 1097275.
Eppstein, David (2013), "The Complexity of Bendless Three-Dimensional Orthogonal Graph Drawing", Journal of Graph Algorithms and Applications , 17 (1): 35–55, arXiv : 0709.4087 , doi : 10.7155 / jgaa.00283 , S2CID 2716392.
Eppstein, David (2010), "Regular labelings and geometric structure", Proc. 22ª Conferência Canadense sobre Geometria Computacional (CCCG 2010) (PDF) , University of Manitoba, arXiv : 1007.0221 , Bibcode : 2010arXiv1007.0221E.
Erdős, Paul ; Wilson, Robin J. (1977), "Nota sobre o índice cromático de quase todos os gráficos" (PDF) , Journal of Combinatorial Theory , Series B, 23 (2–3): 255-257, doi : 10.1016 / 0095-8956 (77) 90039-9.
Erlebach, Thomas; Jansen, Klaus (2001), "The complex of path colour and call scheduling", Theoretical Computer Science , 255 (1-2): 33-50, doi : 10.1016 / S0304-3975 (99) 00152-8 , MR 1819065.
Ferber, Asaf; Jain, Vishesh (2018), "1-factorizations of pseudo - random graphs", arXiv : 1803.10361 [ math.CO ].
Fiamčik, J. (1978), "The acyclic cromática class of a graph", Math. Slovaca , 28 : 139-145.
Fiorini, S .; Wilson, Robin James (1977), Edge-colorings of graphs , Research Notes in Mathematics, 16 , Londres: Pitman, ISBN 0-273-01129-4, MR 0543798.
Folkman, Jon ; Fulkerson, DR (1969), "Edge colorings in bipartite graphs", Combinatorial Mathematics and its Applications (Proc. Conf., Univ. Carolina do Norte, Chapel Hill, NC, 1967) , Chapel Hill, NC: Univ. North Carolina Press, pp. 561–577, MR 0262112.
Fouquet, J.-L .; Jolivet, J.-L. (1983), "Strong edge-colorings of graphs and applications to multi- $k$ -gons", Ars Combinatoria , 16 (A): 141-150, MR 0737086.
Frieze, Alan M .; Krivelevich, Michael; Sudakov, Benny (2005), "The strong chromatic index of random graphs" (PDF) , SIAM Journal on Discrete Mathematics , 19 (3): 719-727 (eletrônico), doi : 10.1137 / S0895480104445757 , MR 2191290.
Gabow, Harold N. (1976), "Using Euler partitions to edge color bipartite multigraphs", International Journal of Computer and Information Sciences , 5 (4): 345–355, doi : 10.1007 / BF00998632 , MR 0422081 , S2CID 36331285.
Gabow, Harold N .; Nishizeki, Takao ; Kariv, Oded; Leven, Daniel; Terada, Osamu (1985), Algorithms for edge-colouring graphs , Tech. Relatório TRECIS-8501, Tohoku University.
Gabow, Harold N .; Westermann, Herbert H. (1992), "Forests, frames, and games: algoritms for matroid soms and applications", Algorithmica , 7 (5-6): 465-497, doi : 10.1007 / BF01758774 , MR 1154585 , S2CID 40358357.
Galvin, F. (1995), "The list cromática index of a bipartite multigraph", Journal of Combinatorial Theory , Series B, 63 (1): 153–158, doi : 10.1006 / jctb.1995.1011.
Gandham, S .; Dawande, M .; Prakash, R. (2005), "Escalonamento de links em redes de sensores: coloração de arestas distribuídas revisitada", Proc. 24th INFOCOM , 4 , pp. 2492–2501, doi : 10.1109 / INFCOM.2005.1498534 , ISBN 0-7803-8968-9, S2CID 8085139.
Giotis, I .; Kirousis, L .; Psaromiligkos, KI; Thilikos, DM (2015), "On the algorítmico Lovász Local Lemma and acyclic edge colouring", Proceedings of the Twelfth Workshop on Analytic Algorithmics and Combinatorics (ANALCO) , p. 16, doi : 10.1137 / 1.9781611973761.2 , ISBN 978-1-61197-376-1.
Goldberg, MK (1973), "Multigraphs com um índice cromático que é quase máximo", Diskret. Analiz. (23): 3-7, 72, MR 0354429. Conforme citado por Chen, Yu & Zang (2011) .
Habib, M .; Péroche, B. (1982), "Some problems about linear arboricity", Discrete Mathematics , 41 (2): 219-220, doi : 10.1016 / 0012-365X (82) 90209-6 , MR 0676882.
Holyer, Ian (1981), "The NP-completeness of edge-colouring", SIAM Journal on Computing , 10 (4): 718-720, doi : 10.1137 / 0210055.
Horák, Peter; Niepel, Ľudovít (1982), "Uma curta prova de um teorema de arboricidade linear para gráficos cúbicos", Acta Mathematica Universitatis Comenianae, 40/41: 275-277, MR 0686983.
Jensen, Tommy R .; Toft, Bjarne (1995), Graph Coloring Problems , Nova York: Wiley-Interscience, ISBN 0-471-02865-7.
Karloff, Howard J .; Shmoys, David B. (1987), "Efficient parallel algoritms for edge colorir problemas", Journal of Algorithms , 8 (1): 39–52, doi : 10.1016 / 0196-6774 (87) 90026-5 , MR 0875324.
Kőnig, D. (1916), "Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre" , Mathematische Annalen , 77 (4): 453-465, doi : 10.1007 / BF01456961 , hdl : 10338.dmlcz / 127635 , archived97310 , S264CID 127310 , S264CID 97310 do original em 19/01/2015 , recuperado em 30/09/2013.
Kowalik, Łukasz (2009), "Improved edge-coloured with three colors", Theoretical Computer Science , 410 (38-40): 3733-3742, doi : 10.1016 / j.tcs.2009.05.005 , MR 2553326.
Mahdian, Mohammad (2002), "On the computational complex of strong edge colorir", Discrete Applied Mathematics , 118 (3): 239–248, doi : 10.1016 / S0166-218X (01) 00237-2 , MR 1892971.
Meredith, Guy HJ; Lloyd, E. Keith (1973), "The footballers of Croam", Journal of Combinatorial Theory , Series B, 15 (2): 161-166, doi : 10.1016 / 0095-8956 (73) 90016-6.
Misra, J .; Gries, David (1992), "A constructive prova of Vizing's Theorem", Information Processing Letters , 41 (3): 131-133, doi : 10.1016 / 0020-0190 (92) 90041-S.
Muthu, Rahul; Narayanan, N .; Subramanian, CR (2007), "Improved bounds on acyclic edge colouring", Discrete Mathematics , 307 (23): 3063–3069, doi : 10.1016 / j.disc.2007.03.006 , MR 2371078.
Nash-Williams, C. St. JA (1964), "Decomposição de gráficos finitos em florestas", Journal of the London Mathematical Society , Second Series, 39 : 12, doi : 10.1112 / jlms / s1-39.1.12 , MR 0161333
Nemhauser, George L .; Park, Sungsoo (1991), "A polyhedral approach to edge colouring", Operations Research Letters , 10 (6): 315-322, doi : 10.1016 / 0167-6377 (91) 90003-8 , MR 1128970.
Richter, David A. (2011), "How to draw a Tait-colorable graph", em Brandes, Ulrik ; Cornelsen, Sabine (eds.), Proc. 18th International Symposium on Graph Drawing (GD 2010) , Lecture Notes in Computer Science, 6502 , Springer-Verlag, pp. 353-364, doi : 10.1007 / 978-3-642-18469-7_32 , ISBN 978-3-642-18468-0.
Sanders, Daniel P .; Zhao, Yue (2001), "Planar graphs of maximum seven are class I", Journal of Combinatorial Theory , Series B, 83 (2): 201–212, doi : 10.1006 / jctb.2001.2047.
Seymour, PD (1979), "On multicolourings of cubic graphs, and conjectures of Fulkerson and Tutte", Proceedings of the London Mathematical Society , Third Series, 38 (3): 423-460, doi : 10.1112 / plms / s3-38.3 .423 , MR 0532981.
Schwenk, Allen J. (1989), "Enumeration of Hamiltonian cycle in sure generalized Petersen graphs", Journal of Combinatorial Theory , Series B, 47 (1): 53-59, doi : 10.1016 / 0095-8956 (89) 90064- 6 , MR 1007713.
Shannon, Claude E. (1949), "Um teorema sobre a coloração das linhas de uma rede", J. Math. Física , 28 (1–4): 148–151, doi : 10.1002 / sapm1949281148 , hdl : 10338.dmlcz / 101098 , MR 0030203.
Skiena, Steven S. (2008), "16.8 Edge Coloring", The Algorithm Design Manual (2ª ed.), Springer-Verlag, pp. 548–550, doi : 10.1007 / 978-1-84800-070-4_16 , ISBN 978-1-84800-069-8. Consulte também o site para esta seção do livro no Stony Brook Algorithm Repository.
Soifer, Alexander (2008), The Mathematical Coloring Book , Springer-Verlag, ISBN 978-0-387-74640-1.
Tait, PG (1880), "Remarks on the colorings of maps", Proc. R. Soc. Edimburgo , 10 : 729, doi : 10.1017 / S0370164600044643.
Trahtman, Avraham N. (2009), "The road coloring problem", Israel Journal of Mathematics , 172 (1): 51–60, arXiv : 0709.0099 , doi : 10.1007 / s11856-009-0062-5 , S2CID 515742.
Vizing, VG (1964), "Em uma estimativa da classe cromática de um p- gráfico", Diskret . Analiz. , 3 : 25-30, MR 0180505.
Vizing, VG (1965), "Críticos gráficos com dada classe cromática", Metody Diskret. Analiz. , 5 : 9-17. (Em russo.)
Williamson, DP ; Hall, LA; Hoogeveen, JA; Hurkens, CAJ; Lenstra, JK ; Sevast'janov, SV; Shmoys, DB (1997), "Short shop schedule", Operations Research , 45 (2): 288-294, doi : 10.1287 / opre.45.2.288 , JSTOR 171745 , MR 1644998.
Zhou, Xiao; Nakano, Shin-ichi; Nishizeki, Takao (1996), "Edge-colouring partial $k$ -trees", Journal of Algorithms , 21 (3): 598-617, doi : 10.1006 / jagm.1996.0061 , MR 1417666.

Languages

In other projects