Complexidade da coloração de arestas em gráficos planares

15

A coloração em 3 arestas dos gráficos cúbicos é completa. O Teorema de quatro cores é equivalente a "Todos os gráficos planares cúbicos sem ponte são de três bordas".NP

Qual é a complexidade da coloração em 3 arestas dos gráficos planares cúbicos?

Além disso, é conjecturado que a coloração -edge é -hard para gráficos planares com grau máximo {4,5}.N P Δ ∈ΔNPΔ∈

Houve algum progresso no sentido de resolver essa conjectura?

Marek Chrobak e Takao Nishizeki. Algoritmos aprimorados de coloração de bordas para gráficos planares. Journal of Algorithms, 11: 102-116, 1990

cc.complexity-theory graph-theory np-hardness graph-colouring Mohammad Al-Turkistany
fonte
A linha 2 da tabela 1 em dx.doi.org/10.1007/s00453-007-9044-3 não significa que "a coloração em três arestas dos gráficos planares cúbicos" é polinomialmente solucionável?
precisa
A entrada da tabela refere-se ao artigo Robertson, Sanders, Seymour e Thomas Four Coloring, que trata dos gráficos planares cúbicos sem ponte .
Mohammad Al-Turkistany
+1 ótima pergunta, eu tenho um simliar, mas mais prático ...
draks ...
Olá, você sabe se existe algum progresso para as cores de 3 bordas em gráficos cúbicos em um toro duplo ?
Draks ...

Respostas:

15

Todo gráfico cúbico planar sem ponte pode ser colorido com três arestas em tempo quadrático, pois essa tarefa é equivalente a quatro cores de um gráfico planar, o que pode ser feito em tempo quadrático. (Veja Robertson, Sanders, Seymour e Thomas: http://people.math.gatech.edu/~thomas/OLDFTP/fcdir/fcstoc.ps )

EDIT: Como Mathieu ressalta, os gráficos cúbicos com pontes nunca são coloridos em três bordas.

Emil
fonte
5
Os gráficos cúbicos com uma ponte nunca são coloridos em três bordas. Isto se segue do "Lema da Paridade", por exemplo, veja a observação abaixo do Lema 2.1 em combinatorics.org/Volume_17/PDF/v17i1r32.pdf
Colin McQuillan
11
Para ser mais preciso, a equivalência entre coloração de ponta e das 4 -coloration fica apenas para cúbicos bridgeless planares gráficos. 34
Mathieu Chapelle
@Emil, não vejo como isso implicaria que os gráficos cúbicos do PLANAR com pontes nunca são coloridos em três bordas.
Mohammad Al-Turkistany
@ MohammadAl-Turkistany Dadas duas cores aeb em uma coloração na aresta d de um gráfico regular d (d> = 2), o subgrafo induzido pelas arestas coloridas a ou b é uma união disjunta de ciclos pares. A partir disso, segue o lema da paridade: Se X é um subconjunto não vazio adequado de V (G) e F é o corte induzido por X, para todas as cores aeb, a paridade do número de arestas de X colorido a é igual à paridade do número de arestas da cor X b. Portanto, qualquer gráfico regular d (d> = 2) com uma ponte não pode ser colorido com bordas em d, independentemente de ser plano ou não.
Leandro Zatesko 01/12/19
5

A coloração em três arestas de gráficos sem triângulo com grau máximo 3 também é NP-completa, consulte 10.1016 / S0096-3003 (96) 00021-5.

Diamantis Koreas
fonte