Discrete Mathematics — background for the 3-SAT project
Notes By Pr. El Hadiq Zouhair
Graph coloring is one of the most useful ideas in all of discrete mathematics. The question it answers sounds like a children's puzzle — "paint the dots so neighbours never match" — yet it powers timetables, maps, compilers, radio networks, and the famous 3-SAT reduction in this folder.
The definition
A proper coloring of a graph $G$ assigns a color to every vertex so that no edge joins two vertices of the same color. A $k$-coloring is a proper coloring that uses at most $k$ colors. If one exists, $G$ is said to be $k$-colorable.
The colors themselves carry no meaning — only the pattern of "same / different" matters. The single rule is: the two endpoints of every edge must get different colors.
A proper 3-coloring: check any edge — its two ends always have different colors.
If even one edge had matching ends, the coloring would be improper (illegal). The whole game is to satisfy every edge at once.
The chromatic number
The chromatic number $\chi(G)$ is the smallest number of colors needed for a proper coloring of $G$.
So "$G$ is $k$-colorable" means $\chi(G) \le k$. Computing $\chi(G)$ is asking: how few colors can we get away with? Some small cases tell the whole story.
Triangle: $\chi = 3$ — all three mutually joined, so all differ.Square (4-cycle): $\chi = 2$ — two colors alternate.
Pentagon (5-cycle): $\chi = 3$ — an odd loop forces a third color.$K_4$ (all 4 joined): $\chi = 4$ — every pair adjacent, so all colors differ.
A clique of $n$ mutually-adjacent vertices always needs $n$ colors, so $\chi(G)$ is at least the size of the largest clique. The triangle and $K_4$ above are the cases $n=3$ and $n=4$.
The special case of two colors
A graph is 2-colorable if and only if it is bipartite — its vertices split into two groups with every edge crossing between them — which happens if and only if it has no odd-length cycle.
That is why the square ($\chi=2$) and the pentagon ($\chi=3$) differ: the even loop alternates two colors perfectly, but the odd loop comes back to itself and clashes, demanding a third. Checking 2-colorability is easy and fast (color along a breadth-first search, alternating two colors).
How do we find a coloring?
Greedy. Go through the vertices in some order; give each the smallest color not used by its already-colored neighbours. Fast, but the number of colors depends on the order — it is not guaranteed to be minimal.
Backtracking. Try colors for one vertex, recurse to the next, and undo a choice when it leads to a dead end. This is exact (it finds a $k$-coloring whenever one exists, or proves none does) but can be slow.
For $k = 2$ there is a fast exact method (the bipartite test). For $k \ge 3$ no fast method is known in general — see the last section.
Why coloring matters
Many real problems are "assign labels so that conflicting things differ" — exactly graph coloring:
Timetabling. Vertices = exams, edges = shared students, colors = time slots. A proper coloring is a clash-free schedule; $\chi(G)$ is the fewest slots needed.
Map coloring. Vertices = regions, edges = shared borders. The Four-Color Theorem says every planar map needs at most 4 colors.
Register allocation. Compilers color an "interference graph" of program variables; colors = CPU registers.
Frequency assignment. Vertices = transmitters, edges = "too close", colors = radio frequencies that must not interfere.
How hard is it? — and the link to 3-SAT
Coloring splits sharply by the number of colors:
2 colors: easy — decidable in linear time (bipartite test).
3 or more colors: deciding whether a graph is 3-colorable is NP-complete — believed to have no fast algorithm in general.
Deciding 3-colorability is exactly as hard as Boolean satisfiability. That is the whole point of the 3-SAT project in this folder: it turns any formula $\varphi$ into a graph $G_\varphi$ that is 3-colorable if and only if $\varphi$ is satisfiable — so a 3-coloring algorithm would solve 3-SAT, and vice versa.
So this little "paint the dots" puzzle sits right at the frontier of what computers can do efficiently — and the project shows you exactly why.