Dada una gráfica lineal $L(G)$ ¿es posible determinar si $G$ ¿es bipartita?

Question

Supongamos que me dan un gráfico de líneas $L(G)$ pero no lo sé $G$ . ¿Es posible determinar a partir de esta información si $G$ ¿es bipartita?

Answer 1

En un principio pensé que la respuesta era afirmativa y por eso publiqué la pregunta, pero descubrí que es negativa.

Dejemos que $G$ sea tal que $E(G)=\{ \{1,2\},\{2,3\},\{1,3\}\}$ y $V(G)=\{1,2,3\}$ . Entonces la gráfica de la línea es de la forma $V(L(G))=\{a,b,c\}$ y $E(L(G))=\{\{a,b\},\{b,c\},\{a,c\}\}$ .

Dejemos que $H$ sea tal que $E(H)=\{\{1,2\},\{1,3\},\{1,4\}\}$ y $V(H)=\{1,2,3,4\}$ . Entonces la gráfica de la línea es de la forma $V(L(H))=\{a,b,c\}$ y $E(L(H))=\{\{a,b\},\{b,c\},\{a,c\}\}$ .

$G$ no es bipartita, sino que $H$ es bipartita, pero tienen el mismo gráfico de líneas.