Complejidad de la coloración de bordes en gráficos planos

15

La coloración de 3 bordes de los gráficos cúbicos es -completa. El teorema de cuatro colores es equivalente a "Cada gráfico cúbico plano sin puente es coloreable por 3 bordes".nortePAG

¿Cuál es la complejidad de la coloración de 3 bordes de los gráficos planos cúbicos?

Además, se conjetura que color -edge es duro para gráficos planos con un grado máximo {4,5}.N P Δ ∈ΔnortePAGΔ∈

¿Se ha avanzado en la resolución de esta conjetura?

Marek Chrobak y Takao Nishizeki. Algoritmos de coloreado de bordes mejorados para gráficos planos. Journal of Algorithms, 11: 102-116, 1990

cc.complexity-theory graph-theory np-hardness graph-colouring Mohammad Al-Turkistany
fuente
¿La línea 2 en la tabla 1 en dx.doi.org/10.1007/s00453-007-9044-3 significa que "la coloración de 3 bordes de los gráficos planos cúbicos" es polinomialmente solucionable?
Oleksandr Bondarenko
La entrada de la tabla se refiere al papel para colorear Robertson, Sanders, Seymour y Thomas Four que trata con gráficos planos cúbicos sin puente .
Mohammad Al-Turkistany
+1 gran pregunta, tengo una similar, pero más práctica ...
draks ...
Hola, ¿sabes si hay algún progreso para los colores de 3 bordes en gráficos cúbicos en un toro doble ?
Draks ...

Respuestas:

15

Cada gráfico cúbico plano sin puente puede tener 3 bordes de color en tiempo cuadrático, ya que esta tarea es equivalente a cuatro colores de un gráfico plano, que se puede hacer en tiempo cuadrático. (Ver Robertson, Sanders, Seymour y Thomas: http://people.math.gatech.edu/~thomas/OLDFTP/fcdir/fcstoc.ps )

EDITAR: Como señala Mathieu, los gráficos cúbicos con puentes nunca son colorables por 3 bordes.

Emil
fuente
55
Los gráficos cúbicos con un puente nunca se pueden colorear con 3 aristas. Esto se desprende del "Parity Lemma", por ejemplo, vea el comentario debajo de Lemma 2.1 en combinatorics.org/Volume_17/PDF/v17i1r32.pdf
Colin McQuillan
1
Para ser precisos, la equivalencia entre coloración -Edge y 4 -coloration significa sólo para cúbicos sin puente planas gráficos. 34 4
Mathieu Chapelle
@ Emil, no veo cómo implicaría que los gráficos PLANARES cúbicos con puentes nunca sean colorables por 3 bordes.
Mohammad Al-Turkistany
@ MohammadAl-Turkistany Dados dos colores ayb en una coloración de borde d de un gráfico d-regular (d> = 2), el subgrafo inducido por los bordes coloreados aob es una unión disjunta de ciclos pares. De esto se desprende el Lema de paridad: si X es un subconjunto no vacío adecuado de V (G) y F es el corte inducido por X, entonces, para todos los colores ayb, la paridad del número de bordes de X coloreados a es igual a la paridad del número de aristas de X coloreadas b. Ergo, cualquier gráfico d-regular (d> = 2) con un puente no puede ser colorable en el borde d, independientemente de si es plano o no.
Leandro Zatesko
5

La coloración de 3 bordes de gráficos sin triángulo con un grado máximo 3 también está completa para NP, ver 10.1016 / S0096-3003 (96) 00021-5.

Diamantis Koreas
fuente