# Line graph of a colored graph

Definition. (Line Graph of a Colored Graph) Let $G_c$ be a simple colored graph with $\chi {(G)}$ colors and $V(G_c )=\{v_1,v_2,…,v_n\}$ be the vertex set, $E(G_c )=e_1,e_2,…,e_m$ be edge set of $G_c.$ The line graph $L(G_c)$ of a colored graph $G_c$ is a simple graph with the vertices $e_1,e_2,…,e_m$ in which $e_i$ and $e_j$ are adjacent whenever, the edges $e_i$ and $e_j$ share at least one common colored vertex or common colored vertices in $G_c$. The $L(G_c)$ is called the line graph or edge graph of colored graph $G_c$.

Then how to prove following statements:
1. If $G_c$ is disconnected with $\chi{(G)}$, then $L(G_c)$ is connected.
2. If $G_c$ is disconnected colored graph, then $L(G_c)$ is disconnected if and only if every pair of edges in $G_c$ do not share a common colored vertex.

• Here the colored graph means proper coloring of a graph. means minimum colors needed to color the graph such that no two vertices receives same color. – K S Betageri Oct 12 '16 at 15:08
• All vertices of $G$ are colored? right? And I don’t understand, when the edges $e_i$ and $e_j$ are adjacent in $L(G_c)$. Are they adjacent iff some vertex $v$ of $G_c$ incident to $e_i$ is colored in the same color as some vertex $u$ of $G_c$ incident to $e_j$m right? – Alex Ravsky Oct 12 '16 at 16:28
• Yes, I will give little more information. The line graph $L(G_c)$ of a colored graph $G_c$ is the simple graph whose colored vertices are the edges of $G_c$ with two colored vertices in $L(G_c)$ are adjacent, whenever the corresponding edges in $G_c$ share at least one common colored vertex. – K S Betageri Oct 12 '16 at 17:01
• if $G$ is $3$-colorable then $L(G_c)$ is complete graph – K S Betageri Oct 12 '16 at 17:03

OK, I’ll suppose that your answers to my questions are positive. Nevertheless, I still don’t know what you mean by “disconnected”.

First I remark that if two edges $e_i$ and $e_j$ of the graph $G_c$ belong to one connected component $G_c’’$ of the graph $G_c$ then them can be joined with a path, which induces a path between $e_i$ and $e_j$ in the graph $L(G_c)$, so the vertices $e_i$ and $e_j$ of the graph $L(G_c)$ belong to one connected component $L(G_c’’)$ of the graph $L(G_c)$ too. In particular, in the graph $G_c$ is connected then the graph $L(G_c)$ is connected too. Now I’ll proceed to your questions.

1) I suppose that “$G_c$ is disconnected with $\chi(G)$” means that we have a proper coloring of (vertices of) the graph $G_c$ into (exactly) $\chi(G_c)$ colors. Let $G_c’$ be a connected component of $G_c$ with the biggest chromatic number. The minimality of number of colors in the proper coloring implies that each connected component $G_c’’$ of the graph $G_c$ is colored in colors which are used to color $G_c’$. Then each edge of $G_c’’$ is adjacent (in $L(G_c)$) to some edge in $G_c’$. Thus the union $L(G_c)\cup L(G_c’)$ is connected. Since this holds for each connected component of the graph $G_c$, the graph $L(G_c)$ is connected.

2) The construction of edges of the graph $L(G_c)$ implies that each vertex of the graph $L(G_c)$ is isolated (has degree zero) iff there are no two distinct edges of the graph $G_c$ which share a common colored vertices. Moreover, in the last case the graph $G_c$ has no adjacent edges, each vertex of the graph $G_c$ has degree at most $1$.

PS. The graph $L(G_c)$ is a union of cliques $K^k=\{e\in G_c: e$ has a vertex colored in color $k\}$.

• Oh my god, I notice some error in question. – K S Betageri Oct 15 '16 at 13:53
• These are the correct question.\\ – K S Betageri Oct 15 '16 at 13:54
• 1. If $G_ c$is disconnected colored graph, then $L(G_c)$ is connected colored graph. 2.If $G_ c$is disconnected colored graph with $\chi (G)$, then $L(G_c)$ is disconnected colored graph if and only if every pair of edges in distinct components of $G_c$ do not share a common colored vertices. – K S Betageri Oct 15 '16 at 13:59
• in second problem disconnected colored graph need not be colored with $\chi 9$ of colores – K S Betageri Oct 15 '16 at 14:02
• @KSBetageri As I understood, my answer to the first question is still valid, it even is more general. But your modified second question has a negative answer. If the graph $G_c$ has at least two connected components $G_c’$ and $G_c’’$ and every pair of edges in distinct components of $G_c$ do not share a common colored vertices then the graph $L(G_c)$ also has at least two connected components $L(G_c’)$ and $L(G_c’’)$, since no vertex (in $L(G_c)$) from these subgraphs can be joined by an edge with a vertex from different component. – Alex Ravsky Oct 15 '16 at 15:17