Coloring¶
In graph theory, vertex coloring refers to the process of assigning colors to the vertices of a graph such that no two adjacent vertices share the same color. The smallest number of colors needed for a valid coloring is called the chromatic number of the graph.
A simple greedy algorithm for vertex coloring:
def greedy_color(graph, order):
color = {}
for v in order: # default order
# neighboring colors
neighboring_colors = {color[u] for u in graph[v] if u in color}
# first available color
for c in itertools.count(0):
if c not in neighboring_colors:
color[v] = c
break
return color
Edge coloring and face coloring (for planar graphs) are also fundamental concepts. The Four Color Theorem states that any planar graph can be colored with at most four colors such that no adjacent regions share the same color.
Special cases: - Bipartite graphs: Chromatic number = 2 - Trees: Chromatic number = 2 - Odd cycles: Chromatic number = 3
Example of checking bipartiteness:
def is_bipartite(graph):
color = {}
for v in graph:
if v not in color:
stack = [v]
color[v] = 0
while stack:
node = stack.pop()
for neighbor in graph[node]:
if neighbor in color:
if color[neighbor] == color[node]:
return False
else:
color[neighbor] = 1 - color[node]
stack.append(neighbor)
return True # graph is bipartite
Applications include scheduling, register allocation, and Sudoku puzzles.
Vertex Coloring¶
In vertex coloring, each vertex is assigned a color such that no two adjacent vertices share the same color.
k-colorable¶
If we can color the vertices of a graph using at most k colors, the graph is called k-colorable.
Proper k-Coloring¶
If in vertex coloring we use k colors (such that for each color z, there exists at least one vertex colored with z), then the resulting coloring is called a proper k-coloring.
Chromatic Number¶
A graph is called k-chromatic if it is k-colorable but not (k-1)-colorable. The value k is referred to as the chromatic number of the graph, denoted by χ(G) = k. Essentially, the chromatic number of a graph indicates the minimum number of colors required to color the vertices of the graph.
Edge Coloring¶
If the edges of a graph can be colored with k colors, we say that the graph is k-edge-colorable.
Edge Chromatic Number¶
If a graph is edge-colorable with k colors but not edge-colorable with k-1 colors, we say the graph is k-edge-colorable. Here, k is considered the edge chromatic number of the graph and is denoted as χ′(G) = k.
Francis Guthrie was the first to conjecture that every map can be colored with 4 colors. In 1976, Guthrie's conjecture was proven with computer assistance and became a theorem.
This book is made by The Shaazzz contributors.
It is publicly available with cc-by-sa license.
Last updated at آوریل 19, 2025.
Rendered by Sphinx (4.3.2) and Minoo theme (Beta 0.9.7).
