Spectrum management is the process of regulating the use of radio frequencies to promote ecient use and gain a net social bene t. Given a set of broadcast emitting stations s1; : : : ; sn, a list of frequencies f1; : : : ; fm, where m n, and the set of adjacent stations f(si; sj)g for some i; j 2 [n]. The goal is to assign a frequency to each station so that adjacent stations use di erent frequencies and the number of used frequencies is minimized. Formulate this problem as an integer linear programming problem.