Phased array radars are able to provide highly accurate airplane surveillance and tracking performance if they are properly calibrated. However, the ambient temperature variation and device aging could greatly deteriorate their performance. Currently, performing a calibration over a large-scale phased array with thousands of antennas is time-consuming. To facilitate the process, we propose a fast calibration method for phased arrays with omnidirectional radiation patterns based on the graph coloring theory. This method transforms the calibration problem into a coloring problem that aims at minimizing the number of used colors. By reusing the calibration time slots spatially, more than one omnidirectional antenna can perform calibration simultaneously. The simulation proves this method can prominently reduce total calibration time and recover the radiation pattern from amplitude and phase errors and noise. It is worth noting that the total calibration time consumed by the proposed method remains constant and is negligible compared with other calibration methods.