Graph Coloring — Interactive Visualizer

Made during a research internship at Université Sorbonne Paris Nord (2022, 10th grade).
Three coloring algorithms with a Pygame interface.

---

Click to place nodes, connect them, then press Enter to color the graph. Use Tab to switch algorithm.

---

What is graph coloring?

A graph is a set of vertices connected by edges. The goal of vertex coloring is to assign a color to each vertex so that no two connected vertices share the same color.

The minimum number of colors needed is called the chromatic number χ(G).

This is a NP-hard problem — there is no known algorithm that solves it efficiently for all graphs. The three algorithms in this project are heuristics: they find a good coloring quickly, but it may not always be optimal.

---

Algorithms

Algorithm	How it works	Complexity
Greedy	Goes through vertices one by one and assigns the smallest available color	O(V + E)
Welsh-Powell	Same as Greedy, but starts with the highest-degree vertices first	O(V log V + E)
DSATUR (Brélaz, 1979)	At each step, picks the vertex with the most different colors already around it — this makes it adapt better than the two others	O(V² + E)

DSATUR gives the best results in most cases, but like the others it is still a heuristic — not an exact algorithm.

---

Code structure

Data structure

The graph is stored as a Python dictionary:

graph = {
    (x, y): {
        "color":     int | None,   # color index, None if not colored yet
        "neighbors": [(x,y), ...]  # list of connected nodes
    }
}

Node positions (pixel coordinates) are used as keys. This avoids a separate position table and keeps the structure simple.

Files

├── main.py              # Pygame window, events, drawing
├── vertex_coloring.py   # Algorithms only (no Pygame code)
└── README.md

The algorithms in vertex_coloring.py work on plain Python dicts and do not depend on Pygame at all. Each algorithm returns a deep copy of the graph — the original is never modified.

Main functions

vertex_coloring.py

Function	What it does
get_min_color(node, graph)	Finds the smallest color not used by any neighbor
get_saturation(node, graph)	Counts how many different colors are around a node
greedy / welsh_powell / dsatur	The three coloring algorithms
reset_colors(graph)	Removes all colors (sets them back to None)

main.py

Function	What it does
find_nearby_node(pos)	Snaps a click to a nearby existing node
add_edge(a, b)	Adds an edge, checks for duplicates and self-loops
run_algorithm()	Runs the selected algorithm and computes χ(G)
draw_hud()	Draws the info panel (algorithm, node count, χ(G))

Adding a new algorithm only requires one line in the registry:

ALGORITHMS = [
    {"label": "DSATUR (Brélaz, 1979)", "fn": dsatur},
    {"label": "Welsh-Powell",          "fn": welsh_powell},
    {"label": "Greedy",                "fn": greedy},
    # {"label": "New algorithm",       "fn": my_function},
]

---

Controls

Key	Action
Click on empty space	Add a node
Click on a node	Start or finish an edge
Enter	Run the algorithm
Tab	Switch algorithm
Escape	Cancel current edge
Delete	Clear everything

---

How to run

pip install pygame
python main.py

Python 3.10 or higher is required.

---

Made during a research internship at Université Sorbonne Paris Nord, 2022.