The currently emerging 802.16e (WiMax) and 3GPP Long Term Evolution (LTE) cellular systems are based on Orthogonal Frequency Division Multiple Access (OFDMA). OFDMA suffers from heavy inter-cell interference if neighboring base stations use the same frequency range. One possible approach to solve this issue is the application of beamforming antennas in combination with interference coordination (IFCO) mechanisms between base stations. In this paper, we trace the problem of IFCO back to the graph coloring problem and investigate the achievable resource utilization of the interference coordinated system. We develop a heuristic that allows the combination of arbitrary scheduling algorithms with the IFCO mechanism. This allows an efficient utilization of the radio system's frequency resources while still obeying scheduling constraints, such as Quality of Service requirements. Finally, we study the trade-off between fairness and the total system throughput.