Timeline for Graph transformation related to graph isomorphism
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 16, 2014 at 6:12 | vote | accept | joro | ||
| Jul 13, 2014 at 16:26 | comment | added | joro | Thanks. Do you have opinion about the graph class described in the linked paper and this question: mathoverflow.net/questions/176016/… | |
| Jul 13, 2014 at 14:54 | comment | added | Tony Huynh | The reason this answers Q1 is the following. Suppose I give you a graph $G'$ and tell you that it comes from some $G$, but I don't tell you which $G$. A priori it might even be that $G'$ comes from two non-isomorphic graphs. But the answer shows that one can in fact recover $G$ from $G'$. | |
| Jul 13, 2014 at 9:28 | comment | added | joro | Why you need find good partition? YOU are computing the transformation so you know the partitions. My sage code finds the partitions even for 2-regular. Or am I missing something? | |
| Jul 13, 2014 at 9:07 | comment | added | joro | Thanks. So your answer, claim 1, the suggested proof imply for triangle free G, G' is $(P_4 \cup K1,\overline{3K_2})$-free. According to the linked paper GI for this class is in P, so this implies GI is in P or am I missing something? | |
| Jul 13, 2014 at 1:54 | history | answered | Tony Huynh | CC BY-SA 3.0 |