In this paper, we consider frequency assignment for orthogonal frequency division multiple access-based cellular networks. We develop a new framework for the mathematical modeling of the frequency assignment problem, which aims at suppressing multi-links interference and enhancing spectral efficiency. The concept of incidence coloring from modern graph theory is utilized to recast the original frequency assignment problem and guide the solution from graph theory perspective. In addition, optimal position of relay stations in a hierarchical cluster based two-hop cellular networks is investigated, and proposes an efficient frequency assignment scheme based on the incidence coloring. System-level simulation results demonstrate that the frequency assignment scheme can effectively mitigate inter-cell interference and improve signal-to-interference-plus-noise ratio. Compared with existing frequency assignment schemes, better coverage performance is obtained and throughput of cell-edge mobile stations is greatly improved.