Si $G,H$ son grafos simples y no dirigidos, decimos que están en un hom(omorfismo)-relación si existe un homomorfismo de grafos desde $G$ a $H$ o de $H$ a $G$ .
Para cualquier grafo $G$ deje $L(G)$ denotan su gráfico de líneas .
Si $G,H$ tienen cada una al menos una arista, y están en una homorrelación, ¿ocurre lo mismo con $L(G), L(H)$ ?
Las cosas están peor de lo que imaginas.
La respuesta de Tony muestra que el orden de homomorfismo de los grafos lineales puede dividirse en intervalos cuyos extremos son los grafos completos. He utilizado este hecho en mi tesis . Entonces las gráficas de línea en el intervalo $[K_d, K_{d+1})$ son los gráficos lineales de grafos con grado máximo $d$ (ignorando las excepciones causadas por $K_3$ ). En $d = 1$ este intervalo sólo contiene $K_1$ para $d = 2$ sólo contiene $K_2$ y los ciclos impar de longitud al menos 5 (hasta equivalencia homomórfica). Sin embargo, a partir de ahí las cosas se complican. De hecho, se demuestra aquí que cualquier otro intervalo de este tipo es universal, lo que significa que CUALQUIER orden parcial contable puede incrustarse en él preservando el orden. Por último, los gráficos de ese artículo cuyos gráficos lineales se utilizan para demostrar la universalidad del intervalo $[K_d, K_{d+1})$ son todos homomórficamente equivalentes a $K_d$ .
En conjunto, esto significa que no sólo hay dos grafos homomórficamente equivalentes cuyos grafos lineales no tienen homomorfismos entre ellos en ninguna dirección, como muestra la respuesta de Gordon. Sino que para cualquier $d \ge 3$ existe un número infinito de grafos homomórficamente equivalentes a $K_d$ pero cuyos grafos lineales forman un orden parcial en el que se puede incrustar cualquier orden parcial contable.
He aquí una reducción al caso de que el grado máximo de $G$ es igual al grado máximo de $H$ . De hecho, para esta reducción, ni siquiera necesitamos el supuesto de que $H$ son $G$ están en una relación de homomorfismo.
Reclamación. Sea $G$ y $H$ sean grafos simples con $\Delta(G) < \Delta(H)$ . Entonces existe un homomorfismo $f$ de $L(G)$ a $L(H)$ .
Prueba. Observe que $L(H)$ contiene una camarilla de tamaño $\Delta(H)$ . A continuación, observe que el número cromático de $L(G)$ es el índice cromático de $G$ que por Teorema de Vizing es $\Delta(G)$ o $\Delta(G)+1$ . Por lo tanto, existe un homomorfismo de $L(G)$ a $K_{\Delta(G)+1}$ . Desde $\Delta(G)+1 \leq \Delta(H)$ existe un homomorfismo de $K_{\Delta(G)+1}$ a $L(H)$ . Componiendo estos homomorfismos se obtiene el resultado.
En realidad, la prueba demuestra que todo contraejemplo debe satisfacer $\Delta(G)=\Delta(H)=\chi'(H)-1=\chi'(G)-1$ .
Qué te parece esto (el argumento no funciona exactamente pero he comprobado el contraejemplo usando el ordenador):
Sea $G$ sea el grafo de un cubo con una arista subdividida y sea $H$ sea el grafo del dodecaedro regular con una arista subdividida. Es fácil ver que existe un homomorfismo de $G$ a $H$ . Afirmo que $L(G)$ y L(H) no están en relación de homomorfismo.
No es difícil ver que $L(G)$ y $L(H)$ tienen número cromático 4 y que los grafos obtenidos suprimiendo las aristas $e_G$ y $e_H$ tienen el número cromático 3. Las aristas $e_G$ y $e_H$ son las únicas aristas que no están en triángulos y por tanto cualquier homomorfismo potencial mapea $e_G$ a $e_H$ y ninguna otra arista se asigna a $e_H$ . Ahora $e_G$ está en un ciclo de longitud 5 pero el ciclo más corto que contiene $e_H$ tiene longitud 6, esto prueba que no puede existir ningún homomorfismo de $L(G)$ a $L(H)$ .
Esta parte no funciona: Para ver que no hay homomorfismo de $L(H)$ a $L(G)$ observe que el gráfico de triángulos en $L(G)$ es bipartito (dos triángulos son adyacentes si comparten al menos un vértice), pero el correspondiente gráfico de triángulos de $L(H)$ no lo es.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
