  In this paper we study the MAX-CUT problem on power law graphs (PLGs) with
power law exponent $\beta$. We prove some new approximability results on that
problem. In particular we show that there exist polynomial time approximation
schemes (PTAS) for MAX-CUT on PLGs for the power law exponent $\beta$ in the
interval $(0,2)$. For $\beta>2$ we show that for some $\epsilon>0$, MAX-CUT is
NP-hard to approximate within approximation ratio $1+\epsilon$, ruling out the
existence of a PTAS in this case. Moreover we give an approximation algorithm
with improved constant approximation ratio for the case of $\beta>2$.
