Graph Coloring Problem Solver Desktop App in Python

The Graph Coloring Problem is one of the most important topics in graph theory and computer science. It is used in many real-world applications such as scheduling, time-table creation, register allocation, map coloring, and network optimization. To make this concept easy to understand and test, I created a simple and powerful Graph Coloring Problem Solver Desktop App in Python.

This desktop application allows you to enter a graph, choose the number of colors, and instantly see whether the graph can be colored without assigning the same color to adjacent nodes. It also visualizes the graph using clear color-coded nodes, which makes learning and experimenting much easier.

In this blog, I will explain the features, working, and importance of this app, along with why this tool is useful for students, programmers, and graph theory learners.

What Is the Graph Coloring Problem?

The graph coloring problem is the task of assigning colors to the vertices of a graph such that:

No two adjacent nodes share the same color.
The total number of colors used is minimized.

The minimum number of colors required for a proper coloring of the graph is called the chromatic number.

Graph coloring plays a major role in:

Scheduling classrooms and exams
Allocating registers in compilers
Coloring maps
Avoiding frequency conflicts in communication networks
Creating efficient timetables

Understanding this concept becomes easier when you can visualize how colors are assigned to nodes. That is where this Python desktop app helps.

Overview of the Python Desktop App

The Graph Coloring Problem Solver is built using:

Tkinter for the desktop interface
NetworkX for graph creation
Matplotlib for visual graph drawing
A custom backtracking algorithm for exact graph coloring
Optional greedy coloring when quick results are needed

This app works entirely on your computer. You simply open it, enter your graph’s edges, choose options, and click the Solve button.

It is perfect for:

Students learning graph theory
Teachers teaching algorithms
Programmers solving graph optimization problems
Competitive programmers
Anyone preparing for technical interviews

Key Features of the Desktop App

1. User-Friendly Interface

The app comes with a clean Tkinter interface where you can enter edges, select the number of colors, and click Solve. No command-line usage is required.

2. Supports Any Graph Input

You can enter edges in the format:


A B
A C
B D

Each line represents an edge between two nodes. The app automatically builds the graph from your input.

3. Exact Backtracking Solver

If you enter a specific number of colors (k), the app checks using backtracking whether a valid k-coloring exists.
This method is exact and can find the true solution, not just approximations.

4. Chromatic Number Finder

If you enable “Search for minimum k,” the app tries k = 1, 2, 3… until it finds the smallest number of colors required.
This gives you the true chromatic number of the graph.

5. Graph Visualization

The app displays a beautiful visual graph using matplotlib.
Each node is colored according to the solution, so you can instantly understand how the coloring works.

6. Copy Result Feature

You can copy the node-color mapping with a single click.
This is useful for assignments, research, and presentations.

How to Use the App

Run the Python file.
Enter edges in the input section.
Choose:
- A specific k, or
- Tick “Search for minimum k”
Click the Solve button.
The result will appear on the left side.
A colored graph visualization will appear on the right side.

This makes experimenting with graphs extremely simple.

Why This App Is Useful

✔ Great for Learning Algorithms

Students can see how backtracking works in real time.

✔ Perfect for Colleges and Classrooms

Teachers can show graph coloring concepts visually.

✔ Ideal for Competitive Programming Practice

You can test custom graphs and verify coloring constraints.

✔ Helps in Research & Project Work

If you are working on graph-related projects, this tool saves time.

✔ No Online Tools Needed

Everything runs offline on your computer.

Conclusion

The Graph Coloring Problem Solver Desktop App is a complete learning tool for anyone who wants to understand graph coloring, backtracking, chromatic numbers, and graph visualization. With an easy-to-use interface and powerful backend algorithm, this tool is perfect for students, teachers, and professionals.

If you are studying algorithms, preparing for coding interviews, or working on graph-based projects, I highly recommend using this app. It will help you visualize problems and understand concepts much more clearly.

#!/usr/bin/env python3

"""

Graph Coloring Problem Solver - Desktop app (Tkinter)

Features:

- Enter graph as edges (one per line) like "0 1" or "A B"

- Optionally enter number of colors (k). If left blank, app will search for minimum k.

- Solve using backtracking (exact) with simple heuristics (degree ordering).

- Visualize result with networkx + matplotlib inside a Tk window.

- Export result (coloring) to clipboard / copyable text.

Author: Generated for user (example)

"""

import tkinter as tk

from tkinter import ttk, messagebox, scrolledtext, filedialog

import networkx as nx

import matplotlib

matplotlib.use("TkAgg")

from matplotlib.backends.backend_tkagg import FigureCanvasTkAgg

import matplotlib.pyplot as plt

import threading

import queue

# ---------- Graph parsing helpers ----------

def parse_edges(text):

"""

Parse edges from multiline text. Each line: "u v"

Node labels can be strings; returned graph uses nodes as strings.

"""

G = nx.Graph()

for ln in text.strip().splitlines():

ln = ln.strip()

if not ln:

continue

parts = ln.split()

if len(parts) < 2:

# ignore single node lines but add node

G.add_node(parts[0])

continue

u, v = parts[0], parts[1]

G.add_edge(u, v)

return G

# ---------- Coloring solver ----------

def order_nodes_by_degree(G):

return sorted(G.nodes(), key=lambda n: G.degree(n), reverse=True)

def can_color_with_k(G, k, node_order=None, time_limit=None):

"""

Backtracking exact solver. Returns (True, coloring) if coloring found, else (False, None).

node_order optional: list of nodes to consider in order.

"""

if node_order is None:

node_order = order_nodes_by_degree(G)

n = len(node_order)

coloring = {}

adjacency = {n: set(G[n]) for n in G.nodes()}

def backtrack(idx):

if idx == n:

return True

node = node_order[idx]

used = {coloring[nb] for nb in adjacency[node] if nb in coloring}

for color in range(k):

if color in used:

continue

coloring[node] = color

if backtrack(idx + 1):

return True

del coloring[node]

return False

ok = backtrack(0)

return ok, (coloring if ok else None)

def find_chromatic_number(G, max_k=None):

"""

Try increasing k from 1..max_k (or n) until a coloring is found.

Returns (k, coloring).

"""

n = G.number_of_nodes()

max_try = max_k or n

node_order = order_nodes_by_degree(G)

for k in range(1, max_try + 1):

ok, coloring = can_color_with_k(G, k, node_order)

if ok:

return k, coloring

return None, None

# ---------- UI ----------

class GraphColoringApp:

def __init__(self, root):

self.root = root

self.root.title("Graph Coloring Problem Solver")

self._build_ui()

self.solve_thread = None

self.result_queue = queue.Queue()

def _build_ui(self):

frm = ttk.Frame(self.root, padding=8)

frm.pack(fill=tk.BOTH, expand=True)

# Input area

input_label = ttk.Label(frm, text="Enter edges (one per line): u v")

input_label.pack(anchor=tk.W)

self.input_text = scrolledtext.ScrolledText(frm, width=40, height=10)

self.input_text.pack(fill=tk.X)

sample = "0 1\n0 2\n1 2\n1 3\n2 3\n3 4"

self.input_text.insert("1.0", sample)

options = ttk.Frame(frm)

options.pack(fill=tk.X, pady=6)

ttk.Label(options, text="Number of colors (k):").grid(row=0, column=0, sticky=tk.W)

self.k_var = tk.StringVar()

self.k_entry = ttk.Entry(options, textvariable=self.k_var, width=6)

self.k_entry.grid(row=0, column=1, sticky=tk.W, padx=(4, 20))

self.find_min_var = tk.BooleanVar(value=False)

ttk.Checkbutton(options, text="Search for minimum k", variable=self.find_min_var).grid(row=0, column=2, sticky=tk.W)

ttk.Button(options, text="Load from file", command=self.load_file).grid(row=0, column=3, padx=6)

ttk.Button(options, text="Solve", command=self.on_solve).grid(row=0, column=4, padx=6)

# Result and visualization area

bottom = ttk.Frame(frm)

bottom.pack(fill=tk.BOTH, expand=True)

left = ttk.Frame(bottom)

left.pack(side=tk.LEFT, fill=tk.BOTH, expand=True)

ttk.Label(left, text="Result / Coloring:").pack(anchor=tk.W)

self.result_text = scrolledtext.ScrolledText(left, width=30, height=12)

self.result_text.pack(fill=tk.BOTH, expand=True)

ttk.Button(left, text="Copy result", command=self.copy_result).pack(pady=4)

right = ttk.Frame(bottom)

right.pack(side=tk.RIGHT, fill=tk.BOTH, expand=True)

ttk.Label(right, text="Graph visualization:").pack(anchor=tk.W)

self.fig, self.ax = plt.subplots(figsize=(5,4))

self.fig.tight_layout()

self.canvas = FigureCanvasTkAgg(self.fig, master=right)

self.canvas_widget = self.canvas.get_tk_widget()

self.canvas_widget.pack(fill=tk.BOTH, expand=True)

# status

self.status_var = tk.StringVar(value="Ready")

ttk.Label(self.root, textvariable=self.status_var, relief=tk.SUNKEN, anchor=tk.W).pack(fill=tk.X, side=tk.BOTTOM)

# poll queue

self.root.after(200, self._poll_queue)

def load_file(self):

path = filedialog.askopenfilename(title="Open edge list", filetypes=[("Text files","*.txt"), ("All files","*.*")])

if not path:

return

try:

with open(path, "r", encoding="utf-8") as f:

text = f.read()

self.input_text.delete("1.0", tk.END)

self.input_text.insert("1.0", text)

except Exception as e:

messagebox.showerror("Load error", str(e))

def on_solve(self):

txt = self.input_text.get("1.0", tk.END).strip()

if not txt:

messagebox.showwarning("Input missing", "Please enter edges in the input area.")

return

try:

G = parse_edges(txt)

if G.number_of_nodes() == 0:

messagebox.showwarning("Empty graph", "No nodes found.")

return

except Exception as e:

messagebox.showerror("Parse error", str(e))

return

k_input = self.k_var.get().strip()

k_given = None

if k_input != "":

try:

k_given = int(k_input)

if k_given < 1:

raise ValueError("k must be >= 1")

except Exception as e:

messagebox.showerror("Invalid k", f"Invalid number of colors: {e}")

return

search_min = self.find_min_var.get()

# run solver in background thread to avoid freezing UI

self.status_var.set("Solving...")

self.result_text.delete("1.0", tk.END)

self.ax.clear()

self.canvas.draw()

self.solve_thread = threading.Thread(target=self._solve_worker, args=(G, k_given, search_min), daemon=True)

self.solve_thread.start()

def _solve_worker(self, G, k_given, search_min):

try:

if search_min:

k, coloring = find_chromatic_number(G, max_k=None)

if k is None:

self.result_queue.put(("done", "No coloring found (unexpected).", G, None, None))

else:

self.result_queue.put(("done", f"Found chromatic number k = {k}", G, k, coloring))

else:

if k_given is None:

# if user didn't give and search_min is off -> default greedy with min colors found by greedy

coloring = nx.coloring.greedy_color(G, strategy="largest_first")

used = set(coloring.values())

k = max(used) + 1 if used else 0

self.result_queue.put(("done", f"Greedy coloring used k = {k}", G, k, coloring))

else:

ok, coloring = can_color_with_k(G, k_given)

if ok:

self.result_queue.put(("done", f"Found a {k_given}-coloring.", G, k_given, coloring))

else:

self.result_queue.put(("done", f"No {k_given}-coloring exists (tried exact search).", G, k_given, None))

except Exception as e:

self.result_queue.put(("error", str(e), None, None, None))

def _poll_queue(self):

try:

while True:

item = self.result_queue.get_nowait()

tag = item[0]

if tag == "done":

msg, G, k, coloring = item[1], item[2], item[3], item[4]

# Note: ordering in put differs above; handle both shapes

# Determine real payload:

if isinstance(G, nx.Graph):

graph = G

k_val = k

coloring_map = coloring

msg_text = msg

else:

# fallback if different ordering

msg_text = item[1]

graph = item[2]

k_val = item[3]

coloring_map = item[4]

if coloring_map is None:

self.result_text.insert(tk.END, f"{msg_text}\n")

self.status_var.set("Done (no coloring).")

# still draw graph uncolored

self._draw_graph(graph, {})

else:

self.status_var.set("Done")

self.result_text.insert(tk.END, f"{msg_text}\n\nColoring (node: color):\n")

for node, c in sorted(coloring_map.items(), key=lambda x: str(x[0])):

self.result_text.insert(tk.END, f"{node}: {c}\n")

# draw

self._draw_graph(graph, coloring_map)

elif tag == "error":

msg = item[1]

messagebox.showerror("Solver error", msg)

self.status_var.set("Error")

except queue.Empty:

pass

self.root.after(200, self._poll_queue)

def _draw_graph(self, G, coloring):

self.ax.clear()

pos = nx.spring_layout(G, seed=42)

# generate color map

if coloring:

colors = []

# normalize integer colors to indices and map to matplotlib colormap

unique = sorted(set(coloring.values()))

index_of = {v:i for i,v in enumerate(unique)}

cmap = plt.get_cmap('tab10')

for n in G.nodes():

if n in coloring:

colors.append(cmap(index_of[coloring[n]] % 10))

else:

colors.append('#cccccc')

else:

colors = '#88ccee'

nx.draw_networkx(G, pos=pos, ax=self.ax, node_color=colors, with_labels=True, node_size=650, font_size=9)

self.ax.set_axis_off()

self.canvas.draw()

def copy_result(self):

txt = self.result_text.get("1.0", tk.END).strip()

if not txt:

return

self.root.clipboard_clear()

self.root.clipboard_append(txt)

messagebox.showinfo("Copied", "Result copied to clipboard.")

def main():

root = tk.Tk()

app = GraphColoringApp(root)

root.geometry("1000x650")

root.mainloop()

if __name__ == "__main__":

main()

https://github.com/gagandeep44489/DiscreteStrucutreAndAlgoApp/blob/main/Graph%20Coloring%20Problem%20Solver.py

Search This Blog

DesktopApp