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 would imply GI is in P.

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 would imply GI is in P.

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:

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$.

Counterexamples are welcome.

Appears to me correctness of the above and paper top of p. 10 would imply GI is in P.

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 would imply GI is in P.