***Is there any specific computational complexity result of Graph Isomorphism for Triangle Free graphs?***


Anything close to the subject will help and of course, I have searched Google.



Graph Isomorphism for Triangle Free graph
The following very simple answer addresses worst-case complexity. How to do the reduction in practice would be a different question, as would average complexity (as pointed out by logicute).


For a graph $G$, let $\hat{G}$ denote the [barycentric subdivision](https://en.wikipedia.org/wiki/Homeomorphism_%28graph_theory%29#Subdivision_and_smoothing) of $G$. This is triangle-free. I claim that $G$ can be reconstructed from $\hat{G}$, as follows. Since the connected components of $G$ and $\hat{G}$ are in an obvious bijection, it is enough to consider the case of connected $G$. This means that we can determine the bipartition of $\hat{G}$ into the vertices of $G$ and the edges of $G$, but we might not yet know which bipartition class is which. If $\hat{G}$ has a vertex of degree $\neq 2$, then we know that this vertex must belong to the bipartition class of vertices of $G$. This disambiguates things and we can reconstruct $G$ by taking this bipartition class and using the paths of length $2$ as the edges; this recovers $G$. Otherwise, all vertices in $\hat{G}$ have degree $2$, which implies that $\hat{G}$ is a cycle because of connectedness, and therefore also $G$ must have been a cycle (of half the size).



> 
> This reconstruction shows that if $\hat{G}$ and $\hat{H}$ are isomorphic, then so are $G$ and $H$. The converse is clear. Taking $G\mapsto \hat{G}$ is therefore a polynomial-time reduction from graph isomorphism to triangle-free graph isomorphism.
> 
> 
> 




---


Thanks to Tony Huynh for pointing out that replacing an edge by a path of length $2$ is exactly barycentric subdivision. For a discussion on whether isomorphism of barycentric subdivsions of simplicial complexes implies isomorphism, see [this question](https://mathoverflow.net/questions/132408/can-we-invert-barycentric-subdivision).


