DSATUR Coloring Step

Problem

Perform one DSATUR step on a partially colored graph.

Pick the uncolored node with the largest number of distinct colors among its colored neighbors (saturation), breaking ties by largest degree then smallest index; assign it the smallest available color. Return [node, color, updated_colors], or [-1, -1, colors] when all nodes are colored.

Hint

DSATUR greedily colors the most constrained node first, which often beats simple order.

Test cases

case 1

in: [3,[[0,1],[1,2],[2,0]],[-1,-1,-1]]

expected: [0,0,[0,-1,-1]]

case 2

in: [4,[[0,1],[1,2],[2,3],[3,0]],[0,-1,-1,-1]]

expected: [1,1,[0,1,-1,-1]]

case 3

in: [2,[[0,1]],[0,1]]

expected: [-1,-1,[0,1]]

case 4

in: [4,[[0,1],[0,2],[0,3]],[0,-1,-1,-1]]

expected: [1,1,[0,1,-1,-1]]

Starter codePython

def dsatur_step(n, edges, colors):
    # Your code here
    pass

4 test cases · run your code against them in the editor