Timeline for Graph homomorphisms and line graph
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 12, 2021 at 2:47 | comment | added | Gordon Royle | The non-working link contains a DOI that can be searched for independently and leads to sciencedirect.com/science/article/pii/0012365X71900148. The paper is called “Homomorphisms of derivative graphs”. (Derivative graph = line graph) | |
| Dec 10, 2021 at 4:31 | comment | added | Cyriac Antony | @DavidRoberson. Could you please give the details of the Nesetril's paper mentioned in your comment above? (the link is not working, at least in our region). The name of the paper and the name of the co-authors (if any) suffices. Thank you. | |
| Oct 15, 2015 at 4:30 | comment | added | David Roberson | By the way, I believe that the exercise in your book you mentioned was first proven by Nesetril in this paper. | |
| Oct 15, 2015 at 4:27 | comment | added | David Roberson | 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). | |
| Oct 5, 2015 at 2:36 | comment | added | Gordon Royle | 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! | |
| Oct 4, 2015 at 16:43 | vote | accept | Dominic van der Zypen | ||
| Oct 3, 2015 at 12:21 | history | answered | Gordon Royle | CC BY-SA 3.0 |