Network densification is needed to meet the throughput demands likely to arise in 2020 and beyond, and small cells are expected to carry a majority of traffic. Since the number of small cells is huge, and they are always randomly deployed, the interference scenarios become much more complicated than in conventional cellular systems. In this paper, an interference coordination scheme based on graph method and clustering strategy for hyper-dense heterogeneous networks (HetNets) is presented. It is shown that the proposed scheme improves the network throughput and user satisfaction by dynamically allocating frequency sub-bands in K-tier networks.