Basically got graph transformation related to graph isomorphism. Define $G \to G'$. $V(G')=V(G) \cup E(G)=\{v_1\ldots v_n\} \cup \{e_1\ldots e_m\}$. Call $v_i$ vertices $v'$ and $e_i$ vertices $e'$. Edges of $G'$. (1) Add $(v_i,e_j)$ iff $v_i \in e_j$. This graph is bipartite and is the subdivision of $G$. According to a paper this preserves GI. (2) Make a clique of $v'$ vertices, i.e. add $(v_i,v_j)$ for $i \ne j$ and without multiple edges. This graph is chordal and split and according to paper preserves GI. (3) Make a clique of $e'$ vertices, i.e. add $(e_i,e_j)$ for $i \ne j$ and without multiple edges. Vertices of $G'$ can be partitioned into two cliques on $v',e'$ and the edges between the cliques are from (1), are the subdivision of $G$. $G \cong H \implies G' \cong H'$. > Q1 Does this transformation preserves isomorphism? $G' \cong H' \implies G \cong H$? I am inclined to believe so, since the cliques doesn't matter much and the subdivision subgraph of (1) preserves isomorphism. A graph is $X$-free if it doesn't contain induced subgraph $X$. Claim 1. $G'$ is $(P_4 \cup K_1)$-free. $3$ or more $v'$ vertices induce triangle and $3$ or more $e'$ vertices induce triangle since they are in a clique. The $5$ vertices of $(P_4 \cup K_1)$ can't be partitioned in $v',e'$ without a triangle. > Is this correct? Conjecture based on experimental data and suggested proof: If $G$ is triangle-free, $G'$ is $\overline{3K_2}$-free. $\overline{3K_2}=K_{2,2,2}$ and the clique number is $3$, so if induced $\overline{3K_2}$ would exists it must be on $3e' \cup 3v'$ vertices. I suspect that the $v'$ vertices must induce triangle in $G$ for the following reason: The partitions of $K_{2,2,2}=\overline{3K_2}$ are $(v_1,e_1),(v_2,e_2),(v_3,e_3)$. The edges $(v_i,v_j),(e_i,e_j)$ come from the cliques. The remaining edges are $(v_1,\{e_2,e_3\}),(v_2,\{e_1,e_3\}),(v_3,\{e_1,e_2\})$, which is $C_6$, subdivision of triangle, contradicting triangle-free. Counterexamples are welcome. Appears to me correctness of the above and [paper top of p. 10](http://arxiv.org/abs/1208.0142) would imply GI is in P.