to $2^{ O\left( \log^2 n \right) }$.
author:
- |
    Wenxue Du\
    [*School of Mathematical Science, Anhui University, Hefei, 230601, China*]{}\
    [E-mail: wenxuedu@gmail.com ]{}
title: '**On Graph Isomorphism Problem** '
---

2010 [*Mathematics Subject Classification*]{}. Primary 05C25, 05C50, 05C60; Secondary 05C85.

Introduction
============

Let $G$ and $H$ be two simple graphs. A bijective map $\phi$ from $V(G)$ to $V(H)$ is called an [*isomorphism*]{} between $G$ and $H$ if $(\phi\hspace{0.5mm} v_i)(\phi\hspace{0.5mm} v_j) \in E(H)$ $\Leftrightarrow$ $v_i v_j\in E(G)$ for any two vertices $v_i$ and $v_j$ of $G$. In the case that there is such an isomorphism between $G$ and $H$, we say that $G$ and $H$ are isomorphic, which is denoted by $G \cong H$. The problem of determining whether or not two given graphs are isomorphic is called [*Graph Isomorphism Problem*]{} (GI).

One of striking facts about GI is the following established by Whitney in 1930s.

\[Thm-WhitneyIsomorphism\] Two connected graphs are isomorphic if and only if their line graphs are isomorphic, with a single exception: $K_3$ and $K_{1,3}$, which are not isomorphic but both have $K_3$ as their line graph.

Clearly, the relation above offers a reduction of GI from general graphs to a special class of graphs — line 