Timeline for Graph Isomorphism for Triangle Free graph
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 19, 2016 at 15:51 | vote | accept | Michael | ||
| Apr 19, 2016 at 15:47 | answer | added | Tobias Fritz | timeline score: 6 | |
| Apr 19, 2016 at 15:29 | comment | added | Tobias Fritz | @Jim: alright, will do. | |
| Apr 19, 2016 at 15:06 | comment | added | Michael | @TobiasFritz let me apreciate your help, post an answer. | |
| Apr 19, 2016 at 15:05 | comment | added | Tobias Fritz | @Jim: yes, that's what I mean. You check for isomorphism of the barycentric subdivisions, which are triangle-free. If these are not isomorphic, then your original graphs aren't isomorphic either; if the subdivisions are isomorphic, then so are the original graphs. The latter is what I gather from mathoverflow.net/questions/132408/…, but probably somebody else can say more about how isomorphism of the subdivisions implies isomorphism of the original graphs. | |
| Apr 19, 2016 at 14:57 | comment | added | Michael | @TobiasFritz ok just to be sure,consoder a situation, where we can decide GI if graphs are not triangle free graphs in $f(n)$ time using an algo. But algo does work if graphs are triangle free, according to you , we can reconstruct and use the algo? | |
| Apr 19, 2016 at 14:55 | comment | added | Tobias Fritz | @TonyHuynh: thanks, of course! I didn't see that this was just a special case of a familiar construction... | |
| Apr 19, 2016 at 14:50 | comment | added | logicute | As per Tobias's argument, any graph class able to encode all graphs has similar worst-case complexity, but average case and other randomized complexities can differ. | |
| Apr 19, 2016 at 14:49 | comment | added | Tony Huynh | @TobiasFritz The name of your construction is the ''barycentric subdivision.'' | |
| Apr 19, 2016 at 14:40 | comment | added | Tobias Fritz | What if you "blow up" a graph by replacing every edge by a path of length 2? This results in a triangle-free graph, and if all nodes of the original graphs have degree larger than 2, then two graphs are isomorphic if and only if their blow-ups are isomorphic. (BTW, does this construction have a name? It's definitely not blow-up, which already has a different meaning for graphs...) Hence graph isomorphism for triangle-free graphs should have complexity equal to graph isomorphism in general. | |
| Apr 19, 2016 at 14:32 | history | asked | Michael | CC BY-SA 3.0 |