¿Los colores de los vértices son, en cierto sentido, colores de los bordes?

Sabemos que los colorantes de borde de un gráfico son colorantes de vértices de un gráfico especial, a saber, de la gráfica de línea de . $G$ $L(G)$ $G$

¿Hay un operador de gráfico $\Phi$ tal que los colores de vértice de un gráfico $G$ son colores de borde del gráfico $\Phi(G)$ ? Estoy interesado en un operador de gráfico de este tipo que se puede construir en tiempo polinómico, es decir, el gráfico $\Phi(G)$ se puede obtener de $G$ en tiempo polinómico.

Observación : Se puede hacer una pregunta similar para conjuntos estables y coincidencias. Una coincidencia en $G$ es un conjunto estable en $L(G)$ . ¿Hay un operador gráfico $\Psi$ tal que los conjuntos estables en $G$ coincidan en $\Psi(G)$ ? Desde ESTABLE SET es -Complete y JUEGO pertenece a , un tal operador gráfico (si existe) no puede ser construido en tiempo polinómico, suponiendo . $\mathsf{ NP}$ $\mathsf{P}$ $\Psi$ $\mathsf{NP}\not=\mathsf{P}$

EDITAR: Inspirado por la respuesta de @ usul y los comentarios de @ Okamoto y @ King, encontré una forma más débil para mi problema: los colores de vértice de un gráfico $G$ son colores de borde de una hipergrafía $\Phi(G)$ definidos de la siguiente manera. El vértice conjunto de $\Phi(G)$ es el mismo conjunto de vértices de $G$ . Para cada vértice $v$ de $G$ , la vecindad cerrada $N_G[v]= N_G(v) \cup\{v\}$ es un borde de la hipergrafía . Entonces es el gráfico lineal de la hipergrafía y, por lo tanto, los colores de vértice de son colores de borde de . $\Phi(G)$ $G$ $\Phi(G)$ $G$ $\Phi(G)$

Nuevamente, agradezco todas las respuestas y comentarios que muestran que, con o sin suponer , el operador que estoy buscando no puede existir. ¡Sería bueno si pudiera aceptar todas las respuestas! $\mathsf{NP}\not=\mathsf{P}$

graph-theory graph-algorithms usuario13136
fuente

Gracias a todos por sus amables comentarios (¡y paciencia!) Y respuestas útiles. Necesito tiempo para leer, pensar y posiblemente volver con ojos frescos.

user13136

Encontré el siguiente problema bastante interesante planteado por Nishizeki y Zhou en 1998 que de alguna manera está relacionado con su pregunta y su segundo comentario a @TsuyoshiIto: ¿Puede el problema de coloración de vértices reducirse "simplemente" al problema de coloración de bordes? (...) Dado que ambos problemas son NP completos, cualquiera de los dos puede reducirse al otro de manera plausible a través de 3-SAT, debido a la teoría de la NP completa. Por lo tanto, el problema abierto pregunta, ... (ver aquí )

vb le

@vble: gracias! Admito que quería "demasiado". Tal operador resolvería el problema de Nishizeki y Zhou.

usuario13136

Respuestas:

Por analogía con el gráfico lineal , creo que está preguntando lo siguiente:

Para cada gráfico no dirigido , ¿existe un gráfico no dirigido manera que cada vértice corresponda a un borde y los bordes correspondientes a y comparten al menos un punto final si y solo si $G = (V,E)$ $G' = (V',E')$ $v \in V$ $(v_1,v_2) \in E'$ $u \in V$ $v \in V$ ? $(u,v) \in E$

La respuesta puede verse como no . Considere el árbol de cuatro vértices con raíz tiene tres hijos . En , debemos tener cuatro aristas: . Además, debe darse el caso de que $G$ $v$ $x,y,z$ $G'$ $(v_1,v_2),(x_1,x_2),(y_1,y_2),(z_1,z_2)$ o es un punto final de cada uno de los otros tres bordes (es decir, , etc.). Pero esto significa que al menos dos de los otros tres bordes deben compartir un punto final común, lo que viola nuestros requisitos ya que no hay dos de adyacentes en el gráfico original. $v_1$ $v_2$ $\left| \{v_1,v_2\} \cap \{x_1,x_2\} \right| \geq 1$ $x,y,z$

Creo que el mismo gráfico también le dará un contraejemplo para la pregunta correspondiente.

usul
fuente

¡Buen punto! En realidad tenía los mismos pensamientos. ¿Pero tal vez hay otra forma de definir

? ¿O cómo podemos demostrar formalmente que tal operador

no existe?

G^{'}

$G'$

Φ

$\Phi$

user13136

@ user13136, hmm, tal vez haya una forma creativa de evitarlo, pero necesitaría reformular su pregunta (creo que mi contraejemplo es una prueba formal de la pregunta tal como está redactada en el cuadro citado). Intuitivamente, creo que el problema es que al ir en la dirección del gráfico de líneas, tomamos un borde (que solo se puede conectar a dos vértices) y lo convertimos en un vértice (que se puede conectar a cualquier número de bordes): fácil . Lo contrario es opuesto y más difícil.

usul

Simplemente agregando a la respuesta de usul, la respuesta corta es no, porque los emparejamientos tienen propiedades estructurales que no necesariamente están presentes en conjuntos estables. Por ejemplo, cada gráfico de línea también es casi lineal y sin garras; Esto realmente limita la profundidad de los colores de los bordes en comparación con los colores de los vértices.

Andrew D. King

La pregunta contiene cierta ambigüedad en lo que quiere decir con “los colores de vértice de un gráfico G son colores de borde de un gráfico H ”, pero es NP-difícil construir un gráfico cuyo número cromático de borde sea igual al número cromático (vértice) de un gráfico dado Formalmente, el siguiente problema de relación es NP-duro.

Representando número cromática como borde número cromática
Instancia : Un gráfico G .
Solución : Un gráfico de H tal que el número cromática borde χ '( H ) de H es igual al número χ cromática ( G ) de G .

Esto se debe a que el teorema de Vizing proporciona un algoritmo eficiente (trivial) que se aproxima al número cromático de borde dentro de un error aditivo de 1, mientras que el número cromático es difícil incluso de aproximar en varios sentidos. Por ejemplo, Khanna, Linial y Safra [KLS00] mostraron que el siguiente problema es NP completo (y luego Guruswami y Khanna [GK04] dieron una prueba mucho más simple):

3-coloreable versus no-4-coloreable
Instancia : Un gráfico G .
Sí, lo prometo : G es de 3 colores.
Sin promesa : G no tiene 4 colores.

Este resultado es suficiente para probar la dureza NP que reclamé al principio. Se deja una prueba como ejercicio, pero aquí hay una pista:

Ejercicio . Demuestre que el problema antes mencionado "Representar el número cromático como número cromático de borde" es NP-duro bajo la reducibilidad funcional de tiempo polinomial al reducir "colorable 3 versus no colorable 4". Es decir, construya dos funciones de tiempo polinomial f (que asigna un gráfico a un gráfico) yg (que asigna un gráfico a un bit) de modo que

Si G es un gráfico de 3 colores y H es un gráfico tal que χ ( f ( G )) = χ '( H ), entonces g ( H ) = 1.

Si G es un gráfico no colorable en 4 y H es un gráfico tal que χ ( f ( G )) = χ '( H ), entonces g ( H ) = 0.

Referencias

[GK04] Venkatesan Guruswami y Sanjeev Khanna. Sobre la dureza de 4 colores, un gráfico de 3 colores. SIAM Journal on Discrete Mathematics , 18 (1): 30–40, 2004. DOI: 10.1137 / S0895480100376794 .

[KLS00] Sanjeev Khanna, Nathan Linial y Shmuel Safra. Sobre la dureza de aproximar el número cromático. Combinatorica , 20 (3): 393–415, marzo de 2000. DOI: 10.1007 / s004930070013 .

Tsuyoshi Ito
fuente

¡Gracias por tu respuesta! Soy un poco impreciso al formular “los colores de vértice de un gráfico

son colores de borde de un gráfico

”. Lo que quiero decir es un operador

como el operador de gráfico de líneas

, pero desde colores de vértices hasta colores de bordes. Esto es de alguna manera más que

G

$G$

H

$H$

Φ

$\Phi$

L

$L$

χ (G) = χ^{'} (H)

$\chi(G) = \chi'(H)$

usuario13136

Como VERTEX COLORING y EDGE COLORING son ambos

-completos, podemos construir, por definición,

partir de

en tiempo polinomial tal que

iff

Pero tal construcción no necesita cumplir con la propiedad de un operador

Estoy buscando. Solo reduce los colores de los vértices a colores de los bordes.

N P

$\mathsf{NP}$

H

$H$

G

$G$

χ (G) \leq k

$\chi(G) \le k$

χ^{'} (H) \leq k^{'}

$\chi'(H) \le k'$

Φ

$\Phi$

usuario13136

@ user13136: Si un requisito más débil es imposible de satisfacer, el requisito más fuerte es obviamente también imposible. Esto es logico. Debe comprender que su ejemplo de gráfico plano no es un contraejemplo para esto. Decidir la capacidad de coloración en 3 de un gráfico plano dado no es un requisito más débil que decidir la capacidad de coloración en 4 de un gráfico plano dado; son solo requisitos diferentes. Por otro lado, ya mostré que lo que quieres es imposible a menos que P = NP, punto. Pero si tiene problemas para comprender esto, no creo que haya nada que pueda hacer para ayudarlo a comprender.

Tsuyoshi Ito

Si entiendo la pregunta correctamente, tal mapa

no existe. No necesitamos referirnos a la integridad de NP. Solo considere

y suponga que tal

existe. Como

es de 2 colores,

debe ser de 2 bordes. Esto significa que el grado máximo de

es como máximo dos. Como

tiene cuatro aristas, podemos ver todos los candidatos para

Φ

$\Phi$

G = K_{1, 3}

$G=K_{1,3}$

Φ (G)

$\Phi(G)$

G

$G$

Φ (G)

$\Phi(G)$

Φ (G)

$\Phi(G)$

Φ (G)

$\Phi(G)$

Φ (G)

$\Phi(G)$

Φ (G)

$\Phi(G)$

G

$G$

@ user13136: Se me ocurrió que podría haber estado confundido porque escribí solo una idea de prueba y omití la prueba real. Revisé la respuesta para que quede claro que omití la prueba real y agregué algunos consejos para la prueba. Si esto aún no funciona para ti, entonces me rendiré.

Tsuyoshi Ito

(Esta es una adición a la respuesta de usul y al comentario de YoshioOkamoto, en lugar de una respuesta). Se puede ver que su operación $\Phi$ existe solo para esos gráficos $G$ para lo cual hay un gráfico $G'$ con $G = L(G')$ es decir $G$ es un gráfico lineal (verificable en polytime). En este caso, $\Phi$ es el "operador de gráfico de línea inversa" $L^{-1}$ es decir $\Phi(G)=G'$ y coloraciones de vértices de $G$ son coloraciones de borde de $\Phi(G)$ .

En teoria
fuente