—One of the most important 5G features is their support for heterogeneous networks (HetNets). Complementing the classic macrocell base stations (MBS), femtocell base stations (FBS) are beneficial in terms of extensive coverage, including indoor, and enhancement of capacity. Unfortunately, FBSs performance in 5G HetNets is affected by complex cross-tier and co-tier interferences, causing reduced quality of service (QoS) and unfairness among users. This paper proposes an innovative resource allocation (RA) algorithm for interference mitigation (IM) based on graph coloring techniques to improve QoS and interuser fairness. The proposed algorithm, named Weighted EdgeWeighted Vertex Interference Mitigation (WEWVIM), employs a weight to the directed edge corresponding to the interference strength from nearby base stations (BSs) and a weight to every vertex, indicating the color with the smallest interference or higher transmission rate. A region of interest (ROI) is formed to find the interfering BSs. Simulation results show that WEWVIM outperforms existing schemes in terms of fairness and QoS, including throughput, packet loss ratio (PLR), delay, and jitter. Index Terms—HetNets, Graph Coloring, Interference Mitigation, 5G, QoS, Resource Allocation