Graph Coloring in Go

Graph coloring is a classic problem in graph theory with applications in scheduling, resource allocation, and map coloring. 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. This challenge asks you to implement a graph coloring algorithm in Go.

Problem Description

You are tasked with writing a Go program that colors a given graph using a backtracking algorithm. The graph will be represented as an adjacency list, where each key in the map represents a vertex, and the value is a slice of integers representing its neighbors. Your program should take this adjacency list as input and return a map where the keys are vertices and the values are the assigned colors (represented as integers starting from 1). The algorithm should attempt to use the minimum number of colors possible. If the graph cannot be colored, return an empty map.

Key Requirements:

• Input: An adjacency list represented as a map[int][]int. The keys are vertex IDs (integers), and the values are slices of integers representing the neighbors of that vertex.
• Output: A map[int]int where keys are vertex IDs and values are the assigned colors (integers starting from 1). Return an empty map if no valid coloring exists.
• Coloring: Adjacent vertices must have different colors.
• Minimum Colors: The algorithm should attempt to use the fewest colors possible.
• Backtracking: Use a backtracking approach to explore different color assignments.

Expected Behavior:

The program should take the adjacency list as input and return a valid coloring if one exists. If no valid coloring is possible, it should return an empty map. The coloring should use the minimum number of colors needed.

Edge Cases to Consider:

• Empty Graph: An empty graph (no vertices) should return an empty map.
• Disconnected Graph: The graph may be disconnected. The algorithm should still find a valid coloring for each connected component.
• Complete Graph: A complete graph (every vertex is connected to every other vertex) requires n colors, where n is the number of vertices.
• Single Vertex: A graph with only one vertex can be colored with a single color.
• No Valid Coloring: Some graphs may not be colorable with a limited number of colors.

Examples

Example 1:

Input: map[int][]int{
    1: {2, 3},
    2: {1, 3, 4},
    3: {1, 2, 4},
    4: {2, 3},
}
Output: map[int]int{
    1: 1,
    2: 2,
    3: 3,
    4: 1,
}
Explanation: This graph can be colored with 3 colors. Vertex 1 is assigned color 1, vertex 2 is assigned color 2, vertex 3 is assigned color 3, and vertex 4 is assigned color 1.  This is a valid coloring because no adjacent vertices share the same color.

Example 2:

Input: map[int][]int{
    1: {2},
    2: {1},
}
Output: map[int]int{
    1: 1,
    2: 2,
}
Explanation: A simple graph with two connected vertices can be colored with two colors.

Example 3: (Edge Case - No Valid Coloring)

Input: map[int][]int{
    1: {2, 3},
    2: {1, 3},
    3: {1, 2},
}
Output: map[int]int{}
Explanation: This is a complete graph with 3 vertices.  It requires 3 colors. If the algorithm is limited to only 2 colors, it will return an empty map, indicating no valid coloring was found.

Constraints

• The number of vertices in the graph will be between 1 and 20 (inclusive).
• Vertex IDs will be integers starting from 1.
• The adjacency list will only contain valid vertex IDs.
• The algorithm should attempt to find a coloring using a reasonable number of colors (e.g., up to 5). Excessive color usage should be avoided.
• The algorithm should complete within 5 seconds.

Notes

• Consider using a recursive backtracking approach.
• Keep track of the colors assigned to each vertex.
• Before assigning a color to a vertex, check if any of its neighbors already have that color.
• If no valid color can be found for a vertex, backtrack to the previous vertex and try a different color.
• The order in which you explore vertices can affect the number of colors used. Consider heuristics for vertex ordering (e.g., vertices with the highest degree first).
• You can define a helper function to check if a coloring is valid.
• The problem does not require finding the optimal coloring (minimum number of colors), but it should attempt to use as few colors as possible.