An example embodiment includes determining a cut of a graph to obtain a bi-partite sub-graph, where the graph represents a plurality of nodes and links between the plurality of nodes in a wireless mesh network. A channel is assigned to the bi-partite graph, and the obtained bi-partite subgraph is removed from the graph. The determining, assigning and removing steps are repeated until the graph has been divided into k bi-partite subgraphs, where k is the number of channels being used for scheduling.