Graph Coloring in Go

Graph coloring is a fundamental problem in computer science with applications in various fields like scheduling, resource allocation, and register allocation in compilers. The goal is to assign colors to the vertices of a graph such that no two adjacent vertices share the same color, using the minimum number of colors possible.

Problem Description

Your task is to implement a function in Go that finds a valid coloring for a given undirected graph using a greedy approach. The function should take the graph as input and return a map where keys are vertex identifiers and values are the assigned colors.

Requirements:

1. Graph Representation: The graph will be represented as an adjacency list, where a map[int][]int is used. The keys of the map represent vertices, and the values are slices of integers representing their adjacent vertices. Vertices are identified by non-negative integers.
2. Greedy Coloring Algorithm: Implement a greedy coloring algorithm. This typically involves iterating through the vertices and assigning the smallest available color that is not used by any of its already colored neighbors.
3. Color Assignment: Colors should be represented by non-negative integers starting from 0.
4. Output: The function should return a map[int]int, where keys are vertex IDs and values are their assigned colors.
5. No Two Adjacent Vertices with Same Color: Ensure that for any edge (u, v) in the graph, the color assigned to vertex u is different from the color assigned to vertex v.
6. Minimum Colors (Greedy): While a true minimum coloring is an NP-hard problem, the greedy algorithm aims to find a "good" coloring, not necessarily the absolute minimum. The algorithm should try to use as few colors as possible based on the order of vertex processing.

Edge Cases to Consider:

• An empty graph (no vertices).
• A graph with isolated vertices (no edges).
• A complete graph (every vertex is connected to every other vertex).
• A bipartite graph.

Examples

Example 1:

Input Graph (Adjacency List):
{
    0: [1, 2],
    1: [0, 2, 3],
    2: [0, 1, 3],
    3: [1, 2]
}

Output Coloring:
{
    0: 0,
    1: 1,
    2: 2,
    3: 0
}
Explanation:
- Vertex 0 is colored 0.
- Vertex 1 is adjacent to 0 (color 0), so it gets color 1.
- Vertex 2 is adjacent to 0 (color 0) and 1 (color 1), so it gets color 2.
- Vertex 3 is adjacent to 1 (color 1) and 2 (color 2), so it gets color 0.
This coloring uses 3 colors (0, 1, 2).

Example 2:

Input Graph (Adjacency List):
{
    0: [1],
    1: [0, 2],
    2: [1, 3],
    3: [2]
}

Output Coloring:
{
    0: 0,
    1: 1,
    2: 0,
    3: 1
}
Explanation:
- Vertex 0 is colored 0.
- Vertex 1 is adjacent to 0 (color 0), so it gets color 1.
- Vertex 2 is adjacent to 1 (color 1), so it gets color 0.
- Vertex 3 is adjacent to 2 (color 0), so it gets color 1.
This coloring uses 2 colors (0, 1), which is optimal for this bipartite graph.

Example 3: (Empty Graph)

Input Graph (Adjacency List):
{}

Output Coloring:
{}
Explanation: An empty graph results in an empty coloring.

Constraints

• The number of vertices in the graph will be between 0 and 1000.
• The number of edges in the graph will be between 0 and 10000.
• Vertex identifiers will be non-negative integers.
• The provided graph representation will be a valid adjacency list for an undirected graph (if vertex u has v in its list, then vertex v will have u in its list).
• Your solution should be reasonably efficient, aiming for a time complexity that is polynomial in the number of vertices and edges.

Notes

• You will need to decide on an order in which to process the vertices. A simple approach is to process them in the order they appear in the map keys or sorted by their identifier.
• For each vertex, you'll need to keep track of the colors used by its neighbors that have already been colored.
• The "smallest available color" means iterating through colors 0, 1, 2, ... and picking the first one that is not used by any adjacent, already colored vertex.
• Consider how to handle vertices that might not be present as keys in the map but are listed as neighbors (though the constraints imply a well-formed graph).