A graph model of the resource reuse problem for relay networks is constructed. Based on this model, an innovative approach called ARRS (adaptive resource reuse scheduling) is presented to enhance the resource utilization. Since the key process of ARRS involves in graph coloring, which is NP-hard, an approximation algorithm called ARRS_Greedy is provided for optimal resource reuse constrained coloring of vertex weighted graph G(V,E,W). ARRS_Greedy is proved to obtain a tight approximation ratio of ?(Δ+1)/2? in time O(|V|²), where Δ is the maximum degree of vertex in graph G. Simulations demonstrate that ARRS_Greedy achieves near optimal performance in practice and prove that ARRS is dynamically adaptive to network status and thus enhances the system capacity more efficiently than previous solutions.