# Graph Coloring Theory & Chromatic Numbers Explained
> Learn about graph coloring, the Four Color Theorem, greedy algorithms, and real-world applications like scheduling and register allocation.

Tags: graph-theory, chromatic-numbers, four-color-theorem, computer-science, algorithms, discrete-mathematics, scheduling
## Introduction to Graph Coloring
* Definition: Assigning labels (colors) to nodes so no two adjacent vertices share the same color.
* Comparison to map coloring where neighboring countries must have different colors.

## Chromatic Numbers - χ(G)
* The chromatic number χ(G) is the minimum number of colors required for a valid coloring.
* Key values: χ(G)=1 (empty graph), χ(G)=2 (bipartite), χ(Kₙ)=n (complete graph).

## The Greedy Coloring Algorithm
* A step-by-step heuristic: order vertices and assign the smallest available color.
* Time Complexity: O(V + E).
* Limitation: It does not always find the optimal chromatic number, depending on vertex ordering.

## Special Graph Classes
* Trees & Bipartite Graphs: χ=2.
* Odd Cycles: χ=3.
* Planar Graphs: χ≤4 (guaranteed by the Four Color Theorem).

## The Four Color Theorem
* History: Proposed by Francis Guthrie (1852), proven by Appel & Haken (1976).
* First major theorem to be proven via computer assistance, checking 1,936 unavoidable configurations.

## Mathematical Bounds
* Lower Bound: χ(G) ≥ ω(G) (clique number).
* Upper Bound: χ(G) ≤ Δ(G) + 1 (Brooks' Theorem covers cases where χ(G) ≤ Δ(G)).

## Real-World Applications
* **Academic Scheduling**: Nodes = exams, edges = shared students. Colors = time slots.
* **Compiler Register Allocation**: Minimizing CPU register usage for variables.
* **Frequency Assignment**: Radio towers with overlapping coverage areas.
* **Other uses**: Sudoku solving, Map coloring, and chemical storage safety.

## Complexity Results
* 2-Coloring: Polynomial time (Easy).
* 3-Coloring & k-Coloring: NP-Complete (Hard).
---
This presentation was created with [Bobr AI](https://bobr.ai) — an AI presentation generator.