Abstract: A spectrum assignment scheme for cognitive radio networks is proposed by means of combining graph theory with immune optimization algorithm. A binary matrix coding scheme is introduced to represent antibody population. Two operators Random-Constraint Satisfaction Operator (RCSO) and Fair-Constraint Satisfaction Operator (FCSO) are designed to guarantee efficiency and fairness respectively. A novel spectrum assignment algorithm based on Immune-Clonal-Selection (ICS) is proposed, which is an improvement of the classical immune clonal selection algorithm. With Constraint Satisfaction Operation (CSO) applied to the encoded populations, the constraints can be satisfied to achieve the global optimization. The CSO is proved to be effective theoretically, and then the computational complexity and applicability are analyzed. Simulation results show that, compared to the Color-Sensitive Graph Coloring (CSGC) algorithm, the ICS can significantly increases the network utilization. Especially when the spectrum conflict is severe, the fairness reward is efficiently improved by using the ICS with FCSO. Meanwhile, its high convergence speed is validated by simulation.