A method allocates frequency subchannels in an orthogonal frequency-division multiple access (OFDMA) network including a set of base stations and a set of mobile stations for each base station. A graph of nodes and edges is constructed, in which the nodes represent the mobile stations in the network, and the edges connecting the nodes represent subchannel allocation constraints to be satisfied for the mobile stations represented by the nodes. The nodes are colored with colors selected from a set of colors such that subchannel allocation constraints of a pair of nodes connected by one of the edges are satisfied. The subchannels are allocated to the mobile stations according to the colors of the corresponding the nodes.