0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – K S Betageri Oct 12 '16 at 15:08
  • $\begingroup$ 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? $\endgroup$ – Alex Ravsky Oct 12 '16 at 16:28
  • $\begingroup$ 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. $\endgroup$ – K S Betageri Oct 12 '16 at 17:01
  • $\begingroup$ if $G$ is $3$-colorable then $L(G_c)$ is complete graph $\endgroup$ – K S Betageri Oct 12 '16 at 17:03
0
$\begingroup$

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\}$.

$\endgroup$
  • $\begingroup$ Oh my god, I notice some error in question. $\endgroup$ – K S Betageri Oct 15 '16 at 13:53
  • $\begingroup$ These are the correct question.\\ $\endgroup$ – K S Betageri Oct 15 '16 at 13:54
  • $\begingroup$ 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. $\endgroup$ – K S Betageri Oct 15 '16 at 13:59
  • $\begingroup$ in second problem disconnected colored graph need not be colored with $\chi 9$ of colores $\endgroup$ – K S Betageri Oct 15 '16 at 14:02
  • $\begingroup$ @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. $\endgroup$ – Alex Ravsky Oct 15 '16 at 15:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.