Greedy Graph Coloring Count

Problem

Color an undirected graph with the greedy algorithm in node order 0 to n-1.

For each node, give it the smallest non-negative color not used by an already colored neighbor. Return the number of colors used. edges is a list of [u, v] pairs.

Hint

A greedy coloring may use more colors than the chromatic number.

Test cases

case 1

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

expected: 2

case 2

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

expected: 3

case 3

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

expected: 2

case 4

in: [3,[]]

expected: 1

Starter codePython

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

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