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.


For triangle-free $G$, $G'$ is $(P\_4 \cup K\_1,\overline{3K2})$-free.


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.



Graph transformation related to graph isomorphism
Here is a proof that the answer to Q1 is **yes**. 


Let $f$ be the described transformation and suppose that $G'=f(G)$ for some $G$. Let $A$ and $B$ be the vertices of $G'$ that correspond to the vertices and edges of $G$ respectively. Note that $(A,B)$ is a partition of $V(G')$ such that $A$ is a clique, $B$ is a clique and each vertex in $B$ has exactly two neighbours in $A$. Call such a partition *good*. 


**Claim.** $G'$ has a unique good partition unless $G$ is a star or $2$-regular. 


**Proof.** Let $(A',B')$ be a good partition different from $(A,B)$. Write $A'=A\_1 \cup B\_1$ and $B'=A\_2 \cup B\_2$ where $A\_1 \cup A\_2=A$ and $B\_1 \cup B\_2=B$. First suppose that for some $i$, both $A\_i$ and $B\_i$ are non-empty. Since, $A\_i \cup B\_i$ is a clique, it follows that $B\_i$ are the edges of a star, and $A\_i=\{x\}$ where $x$ is the middle vertex of this star. Since the claim obviously holds if $|V(G)| \leq 2$, the only remaining possibilities are 


1. $(A',B')=(B,A)$, or
2. $|A\_1|=1$ and $B\_2=\emptyset$, or
3. $|A\_2|=1$ and $B\_1=\emptyset$.


The third possibility is impossible since the vertices in $B\_2$ would only have one neighbour in $A'$. The first possibility implies that $G$ is $2$-regular, and the second possibility implies that $G$ is a star. This completes the proof of the claim.


Note the above proof shows that if $G$ is $2$-regular or a star, then $G'$ has exactly two good partitions. For a good partition $(A,B)$ let $G'(A,B)$ be the graph obtained by removing the edges of the cliques on $A$ and $B$. If $G'$ has two good partitions $(A,B)$ and $(A',B')$, it is easy to see (and somewhat magical) that $G'(A,B) \cong G'(A',B')$. Therefore, we can recover $G$ from $G'$ by finding a good partition $(A,B)$ and computing $G'(A,B)$ (this will be the graph obtained from $G$ by subdividing every edge once). 


