7
$\begingroup$

If $G,H$ are simple, undirected graphs, we say that they are in a hom(omorphism)-relation if there is a graph homomorphism from $G$ to $H$ or from $H$ to $G$.

For any graph $G$ let $L(G)$ denote its line graph.

If $G,H$ each have at least one edge, and they are in a hom-relation, does the same hold for $L(G), L(H)$?

$\endgroup$
  • $\begingroup$ Let $G=K_3$, the complete graph with three vertices and $H=K_2$. Then $G$ and $H$ is in homomorphism relation. But, $L(G)=G$ and $L(H)=K_1$. If these two latter graphs be in homomorphism relation, then we must have a loop in $L(H)$, which is impossible. I think, if there is at least one edge in $L(G)$ and $L(H)$, your answer is true, $\endgroup$ – Shahrooz Janbaz Oct 1 '15 at 11:44
  • $\begingroup$ @ShahroozJanbaz $L(G)$ and $L(H)$ are in homomorphism relation since there is a homomorphism from $K_1$ to $K_3$. $\endgroup$ – Tony Huynh Oct 2 '15 at 9:21
5
$\begingroup$

Well, this question turned out more interesting than I thought at first.

If there is a homomorphism $f:G \to H$ then at first sight, it seems that the natural induced mapping on edges would be a homomorphism from $L(G) \to L(H)$, but this turns out to be false.

In fact, the whole thing turns out to be false, in that two graphs can be homomorphically equivalent (i.e. homomorphisms in both directions), but have unrelated linegraphs.

I think that the smallest examples are the following two, and running this Sage code is the easiest way to convince yourself that they are actually examples.

g1 = Graph("D]w")
g2 = Graph("FQjR_")
lg1 = g1.line_graph()
lg2 = g2.line_graph()
g1.has_homomorphism_to(g2)
g2.has_homomorphism_to(g1)
lg1.has_homomorphism_to(lg2)
lg2.has_homomorphism_to(lg1)

Actually, the two graphs both have chromatic number 3 and have triangles, so it is easy to see that they are homomorphically equivalent (simply use the colour classes to map each one into one of the triangles of the other).

But it is not trivial to see that the two linegraphs do not have homomorphisms between them. Or at least, I couldn't find a slick one-or-two line reason for it, and rather than start to write out a case analysis (suppose vertex 1 is mapped to vertex 2, then vertex 2 must be mapped to either 3 or 4, and in the first case...), the Sage code is easier to understand and more reliable.

$\endgroup$
  • 6
    $\begingroup$ Chris Godsil pointed out to me that an exercise in our Algebraic Graph Theory text is to show that the mapping between line graphs induced by a homomorphism between two graphs is a homomorphism between the line graphs precisely when it is locally injective. I should probably make more effort to keep up with the literature! $\endgroup$ – Gordon Royle Oct 5 '15 at 2:36
  • $\begingroup$ Gordon, one way to show that your lg1 does not have a homomorphism to your lg2 is the following: Claim: lg1 has a homomorphism to the line graph of a graph $G$ of max degree 3 if and only if $G$ contain g1 as an induced subgraph. Proof: If lg1 has an injective homomorphism to $L(G)$, then lg1 is an induced subgraph of $L(G)$ by a degree argument. This implies that g1 is an induced subgraph of $G$. Identifying any two nonadjacent vertices of lg1 creates an odd wheel. However, no odd wheel has a homomorphism to the line graph of a graph of max degree 3 (true for $W_3 = K_4$, use induction). $\endgroup$ – David Roberson Oct 15 '15 at 4:27
  • $\begingroup$ By the way, I believe that the exercise in your book you mentioned was first proven by Nesetril in this paper. $\endgroup$ – David Roberson Oct 15 '15 at 4:30
5
$\begingroup$

Things are even worse than you imagine.

Tony's answer shows that the homomorphism order of line graphs can be partitioned into intervals whose endpoints are the complete graphs. I made use of this fact in my thesis. Then the line graphs in the interval $[K_d, K_{d+1})$ are the line graphs of graphs with maximum degree $d$ (ignoring exceptions caused by $K_3$). For $d = 1$, this interval contains only $K_1$, for $d = 2$ it contains only $K_2$ and the odd cycles of length at least 5 (up to homomorphic equivalence). After that however things get more complicated. In fact, it is shown here that every other such interval is universal, meaning that ANY countable partial order can be embedded order-preservingly into it. Finally, the graphs in that paper whose line graphs are used to prove universality of the interval $[K_d, K_{d+1})$ are all homomorphically equivalent to $K_d$.

All together this means that not only are there two homomorphically equivalent graphs whose line graphs have no homomorphisms between them in any direction, as Gordon's answer shows. But for any $d \ge 3$, there are an infinite number of graphs all homomorphically equivalent to $K_d$, but whose line graphs form a partial order that any countable partial order can be embedded in.

$\endgroup$
3
$\begingroup$

Here is a reduction to the case that the maximum degree of $G$ is equal to the maximum degree of $H$. In fact, for this reduction, we do not even need the assumption that $H$ are $G$ are in a homomorphism relation.

Claim. Let $G$ and $H$ be simple graphs with $\Delta(G) < \Delta(H)$. Then there is a homomorphism $f$ from $L(G)$ to $L(H)$.

Proof. Observe that $L(H)$ contains a clique of size $\Delta(H)$. Next note that the chromatic number of $L(G)$ is the chromatic index of $G$, which by Vizing's Theorem is either $\Delta(G)$ or $\Delta(G)+1$. Thus, there is a homomorphism from $L(G)$ to $K_{\Delta(G)+1}$. Since $\Delta(G)+1 \leq \Delta(H)$, there is a homomorphism from $K_{\Delta(G)+1}$ to $L(H)$. Composing these homomorphisms gives the result.

The proof actually shows that every counterexample must satisfy $\Delta(G)=\Delta(H)=\chi'(H)-1=\chi'(G)-1$.

$\endgroup$
  • 3
    $\begingroup$ I wrote this same thing out, but then realised that it is possible that $f(u) = f(w)$ which seemed to be a flaw in the argument? $\endgroup$ – Gordon Royle Oct 2 '15 at 10:15
  • $\begingroup$ A note for the unwary (like me): the above comments refer to the argument using the obvious map induced on edges, which is wrong for the reason given by Gordon Royle. $\endgroup$ – David Oct 2 '15 at 17:03
0
$\begingroup$

How about this (the argument doesn't exactly work but I have checked the counterexample using computer):

Let $G$ be the graph of a cube with one edge subdivided and let $H$ be the graph of the regular dodecahedron with one edge subdivided. It is easy to see that there is a homomorphism from $G$ to $H$. I claim that $L(G)$ and L(H) are not in homomorphism relation.

It is not hard to see that $L(G)$ and $L(H)$ have chromatic number 4 and that the graphs obtained by deleting the edges $e_G$ and $e_H$ have chromatic number 3. The edges $e_G$ and $e_H$ are the only edges not in triangles and so any potential homomorphism maps $e_G$ to to $e_H$ and no other edge gets mapped to $e_H$. Now $e_G$ is in a cycle of length 5 but the shortest cycle containing $e_H$ has length 6, this proves no homomorphism can exist from $L(G)$ to $L(H)$.

This part does not work: To see that there is no homomorphism from $L(H)$ to $L(G)$ observe that the graph of triangles in $L(G)$ is bipartite (two triangles are adjacent if they share at least one vertex), but the corresponding triangle graph of $L(H)$ is not.

$\endgroup$

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.