Graph Isomorphism for Triangle Free graph 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.
 A: 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 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.
