Skip to main content
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