Timeline for Graph transformation related to graph isomorphism
Current License: CC BY-SA 3.0
9 events
when toggle format | what | by | license | comment | |
---|---|---|---|---|---|
Jul 16, 2014 at 6:12 | vote | accept | joro | ||
Jul 13, 2014 at 12:43 | history | edited | joro | CC BY-SA 3.0 |
added 72 characters in body
|
Jul 13, 2014 at 1:54 | answer | added | Tony Huynh | timeline score: 1 | |
Jul 12, 2014 at 18:48 | comment | added | Marzio De Biasi | no problem! I tried to read the last part of the question but I got totally lost. What is the relation of the claims in your question and theorem 6 of the paper? I think you should 1) briefly define what are $\overline{3K_2}$, and $K_{2,2,2}$; 2) write the theorem of the paper; 3) briefly explain why the claims of your question and the theorem lead to GI in P | |
Jul 12, 2014 at 12:48 | comment | added | joro | @MarzioDeBiasi edited with proposed proof of the conjecture, do you object it? | |
Jul 12, 2014 at 12:47 | history | edited | joro | CC BY-SA 3.0 |
Added possible proof of conjecture
|
Jul 12, 2014 at 12:02 | comment | added | Marzio De Biasi | Also claim 1 seems correct: to avoid a triangle two nodes of $P_4$ must be on the clique from $V_1$ and the other two on the clique from $V_2$. So there is no way to pick the $K_1$. You can tight it: $G'$ is also $(P_3 \cup K_1)$ free. | |
Jul 12, 2014 at 11:32 | comment | added | Marzio De Biasi | $Q_1$ should be a direct consequence of the following 2 lemmas: given two bipartite graphs $G=(V_1\cup V_2,E), G' =(V'_1\cup V'_2,E')$ then (1) they are isomorphic if and only if their complements are isomorphic. (2) the operation of "complementing the edges" of a bipartite graph (i.e. replacing all the edges $E$ with all the edges $(u,v) \notin E, u \in V_1, v \in V_2$) preserves isomorphism. I'll check it better and convert it to an answer. | |
Jul 12, 2014 at 10:45 | history | asked | joro | CC BY-SA 3.0 |