07 Graph Coloring, Greedy Coloring, Smallest-Last Heuristics, Block Graph Colorings

Lecture from: 11.03.2025 | Video: Homelab

k-Coloring and Chromatic Number

Definition of k-Coloring

A k-coloring of a graph $G=(V,E)$ is an assignment of $k$ colors to the vertices of $G$ such that no two adjacent vertices share the same color. Formally, a k-coloring is a function $c:V\to [k]$, where $[k]=\{1,2,...,k\}$ represents the set of $k$ colors, such that for every edge $\{u,v\}\in E$, we have $c(u)\ne c(v)$.

In simpler terms, we are painting each vertex with one of $k$ colors so that connected vertices always have different colors.

Chromatic Number $\chi (G)$

The chromatic number of a graph $G$, denoted by $\chi (G)$, is the minimum number of colors required to properly color the vertices of $G$. In other words, $\chi (G)$ is the smallest integer $k$ for which a k-coloring of $G$ exists.

k-Partite Graphs and Chromatic Number

A graph $G$ is k-partite if its vertex set $V$ can be partitioned into $k$ disjoint sets $V_1,V_2,...,V_k$ such that no edge in $G$ connects two vertices within the same set $V_i$. An equivalent formulation for the chromatic number is:

$\chi (G)\le k$ if and only if $G$ is k-partite.

Each set $V_i$ in the k-partition represents a set of vertices that can all be colored with the same color without violating the coloring condition. These sets are also known as stable sets or independent sets, meaning they contain no edges within themselves.

Special Case: Bipartite Graphs

A special case of k-partite graphs is when $k=2$. A graph $G$ is bipartite if and only if it is 2-colorable, i.e., $\chi (G)\le 2$. We can efficiently determine if a graph is bipartite and find a 2-coloring (if one exists) in $O(|E|)$ time using Breadth-First Search (BFS) or Depth-First Search (DFS). If a connected graph is bipartite, it contains no odd cycles.

Applications of Graph Coloring

Graph coloring is not just a theoretical concept; it has numerous practical applications in various fields. Here are a few examples:

Examination Timetabling

Imagine we need to schedule exams for several students. Some students are taking multiple courses, so certain exams cannot be scheduled at the same time to avoid conflicts for students. We can model this problem using graph coloring:

• Vertices: Each vertex represents an exam.
• Edges: An edge between two vertices exists if there is at least one student taking both exams (meaning they cannot be scheduled at the same time).
• Colors: Each color represents a timeslot or exam period.

A valid graph coloring assigns timeslots to exams such that no conflicting exams are scheduled at the same time. The goal is to minimize the number of timeslots (colors) needed, which corresponds to finding the chromatic number of the graph.

Register Allocation in Compilers

In computer science, register allocation is a crucial step in compiling code. Registers are small, fast storage locations within a CPU. Variables frequently used in a program should ideally be stored in registers to speed up execution. However, the number of registers is limited.

We can use graph coloring to allocate registers efficiently:

• Vertices: Each vertex represents a variable in the program.
• Edges: An edge between two variables exists if they are “live” at the same time and thus interfere with each other (cannot be assigned to the same register).
• Colors: Each color represents a register.

A valid graph coloring assigns registers to variables such that interfering variables are assigned different registers. Minimizing the number of registers (colors) used is the objective. This is known as interference graph coloring.

Frequency Assignment in Wireless Networks

In wireless communication, different frequencies are used to avoid interference between signals. Consider a network of wireless transmitters (e.g., base stations in a cellular network or nodes in a sensor network). Transmitters that are geographically close or whose signals can interfere need to operate on different frequencies.

Graph coloring can model this frequency assignment problem:

• Vertices: Each vertex represents a wireless transmitter.
• Edges: An edge between two transmitters exists if their signals can interfere with each other.
• Colors: Each color represents a frequency band.

A valid graph coloring assigns frequencies to transmitters such that interfering transmitters use different frequencies. Minimizing the number of frequencies (colors) used is important to conserve the frequency spectrum.

Map Coloring and the Four-Color Theorem

A famous problem in graph theory is map coloring. Imagine a map of countries or states. We want to color each region such that no two adjacent regions (sharing a border) have the same color.

This can be represented as a graph:

• Vertices: Each vertex represents a region.
• Edges: An edge between two regions exists if they share a border.
• Colors: Colors are used to color the regions.

The Four-Color Theorem states that any planar map (and therefore any planar graph) can be colored with at most four colors. This theorem has a long history and was famously proven using computer assistance.

Why is Graph Coloring So Hard?

Despite its seemingly simple definition, graph coloring is computationally challenging in general. Let’s briefly touch upon why this is the case.

Colorability is Computationally Hard

While graph coloring has many applications, determining the chromatic number of a graph or even just checking if a graph is k-colorable for $k\ge 3$ is computationally difficult. For $k=2$ it’s a trivial check, since we need to alternate colors.

Graphs with High Chromatic Number and No Short Cycles

Theorem: For any integers $k\in \mathbb{N}$ and $r\in \mathbb{N}$, there exist graphs that do not contain any cycles of length $\le k$ (i.e., they are locally tree-like) but have a chromatic number of at least $r$.

This theorem demonstrates that a graph can be locally sparse (resembling a tree locally) yet still require a large number of colors for proper vertex coloring. This is counterintuitive because sparse graphs often have small chromatic numbers. The proof for $k=3$ is given in the lecture script.

This property highlights that global constraints of graph coloring, rather than just local structure, make the problem hard. Just because a graph looks locally simple (like a tree) does not imply that it’s easy to color globally.

NP-Completeness

Theorem: For every fixed integer $k\ge 3$, the problem of determining whether a given graph $G=(V,E)$ is k-colorable (i.e., whether $\chi (G)\le k$) is NP-complete.

This NP-completeness result implies that, unless P=NP, there is no polynomial-time algorithm to solve the k-coloring problem for $k\ge 3$. This makes finding optimal graph colorings for general graphs very challenging for larger instances.

Approximation Hardness

Not only is finding the exact chromatic number NP-hard, but even approximating it is also hard.

Approximation Hardness Result: For every $ϵ>0$, it is NP-hard to approximate the chromatic number $\chi (G)$ within a factor of $n^{1-ϵ}$, where $n=|V|$ is the number of vertices.

This means that finding an algorithm that always produces a coloring using at most $c\cdot \chi (G)$ colors for some constant $c$, or even within a factor of $n^{1-ϵ}$ of the chromatic number, is unlikely to be possible in polynomial time (unless P=NP).

Exponential Algorithms

Despite the NP-hardness, we can still find exact solutions using exponential-time algorithms. One such approach is based on inclusion-exclusion and dynamic programming. This algorithm can determine the chromatic number of a graph using polynomial space and time $O(2.3^n)$, which is better than brute-force checking of all possible color assignments ($k^n$ for k colors).

Special Cases and Heuristics

Due to the computational hardness of general graph coloring, research often focuses on:

• Special Classes of Graphs: Finding efficient coloring algorithms for specific types of graphs, such as planar graphs, perfect graphs, interval graphs, etc.
• Approximation Algorithms: Designing algorithms that provide colorings that are “good enough” (though constant-factor approximations are hard in general, as mentioned).
• Heuristics: Developing practical algorithms that may not guarantee optimality or performance bounds but work well in practice for many instances.

Greedy Coloring Algorithm

A simple and widely used approach for graph coloring is the Greedy Coloring Algorithm. It is a heuristic algorithm, meaning it doesn’t guarantee to find an optimal coloring (a coloring using $\chi (G)$ colors), but it is often effective in practice and easy to implement.

Algorithm Description

GREEDY-COLORING (G):

1. Choose a Vertex Ordering: Select an arbitrary ordering of the vertices $V=\{v_1,v_2,...,v_n\}$. The performance of the greedy algorithm can depend significantly on this ordering.

2. Initialize Colors: Assign color 1 to the first vertex in the ordering, $c[v_1]\leftarrow 1$.

3. Iterate Through Vertices: For each vertex $v_i$ from $i=2$ to $n$:

   • Find Available Colors: Consider the neighbors of $v_i$ that have already been colored (i.e., neighbors in the set $\{v_1,v_2,...,v_{i-1}\}$).
   • Choose the Smallest Available Color: Assign to $v_i$ the smallest positive integer color $k\in \mathbb{N}$ that is not already used by any of its neighbors in $\{v_1,v_2,...,v_{i-1}\}$. Formally: $c[v_i]\leftarrow \min \{k\in \mathbb{N}\mid k\ne c(u)\text{ for all }u\in N(v_i)\cap \{v_1,...,v_{i-1}\}\}$

Performance of Greedy Coloring

Observation 1: Upper Bound on Colors Used

For any vertex ordering, the Greedy Coloring Algorithm never uses more than $\Delta (G)+1$ colors, where $\Delta (G)$ is the maximum degree of the graph $G$.

Explanation: When we color vertex $v_i$, it has at most $\Delta (G)$ neighbors in the entire graph, and thus at most $\Delta (G)$ neighbors that have already been colored (from $\{v_1,...,v_{i-1}\}$). Therefore, there is always at least one color available from $\{1,2,...,\Delta (G)+1\}$ that is not used by its already-colored neighbors.

Notation: $\Delta (G):={\max }_{v\in V}\text{deg}(v)$ (maximum degree in $G$).

Observation 2: Best-Case Performance

There exists a vertex ordering for which the Greedy Coloring Algorithm uses exactly $\chi (G)$ colors. This means that for some orderings, the greedy algorithm can find an optimal coloring.

Explanation: Consider an optimal coloring of $G$ that uses $\chi (G)$ colors. We can order the vertices such that vertices of color 1 come first, then vertices of color 2, and so on, up to color $\chi (G)$. When we apply the greedy algorithm with this ordering, each vertex will be assigned a color no greater than its optimal color, and thus the algorithm will use at most $\chi (G)$ colors (and at least $\chi (G)$ by definition). Note that finding this sort of ordering is equivalent and equally hard.

Observation 3: Worst-Case Performance

There exist bipartite graphs (which have $\chi (G)=2$) and vertex orderings for which the Greedy Coloring Algorithm uses $|V|/2$ colors. This demonstrates that for some graphs and orderings, the greedy algorithm can perform quite poorly compared to the optimal chromatic number.

Example: Consider a complete bipartite graph $K_{n/2,n/2}$ (where $n$ is even). In a worst-case ordering, the greedy algorithm might color vertices in a way that it uses a new color for every vertex in one partition, resulting in $n/2$ colors, even though the chromatic number is 2.

Heuristics for Vertex Ordering in Greedy Coloring

The choice of vertex ordering is crucial for the performance of the Greedy Coloring Algorithm. A good ordering can often lead to colorings that are closer to optimal. One common and effective heuristic is the smallest-last ordering (also known as reverse Cuthill-McKee ordering in some contexts, though slightly different):

Smallest-Last Vertex Ordering Heuristic:

1. Find Minimum Degree Vertex: Find a vertex $v_n$ with the minimum degree in the current graph.
2. Remove and Recurse: Remove $v_n$ and all incident edges from the graph. Recursively find a smallest-last ordering for the remaining graph. Let this ordering be $v_1,v_2,...,v_{n-1}$.
3. Reverse Order: The smallest-last ordering for the original graph is $v_1,v_2,...,v_{n-1},v_n$.

In essence, we repeatedly pick a vertex of minimum degree in the remaining graph, remove it, and place it last in the ordering. This heuristic tends to place low-degree vertices towards the end, giving them more color choices when they are colored by the greedy algorithm.

Observation about Smallest-Last Ordering:

If for a given graph $G=(V,E)$ and the smallest-last vertex ordering $v_1,...,v_n$, it holds that for every $2\le i\le n$, the number of neighbors of $v_i$ in $\{v_1,...,v_{i-1}\}$ is at most $k$ (i.e., $|N(v_i)\cap \{v_1,...,v_{i-1}\}|\le k$), then the Greedy Coloring Algorithm using this ordering will use at most $k+1$ colors.

Why smallest-last heuristic works well:

The smallest-last ordering tends to create a situation where, when we color a vertex $v_i$, it has relatively few already-colored neighbors. This increases the chances of finding a small color index that is available, thus reducing the total number of colors used.

Trees and Planar Graphs

• Trees: For trees, the smallest-last ordering (or even a simple BFS or DFS ordering) used with the Greedy Coloring Algorithm will always produce a 2-coloring (which is optimal since trees are bipartite, except for $K_1$).

• Planar Graphs: It is known (though without proof here) that in every planar graph, there exists a vertex of degree at most 5. If we apply the smallest-last vertex ordering heuristic to a planar graph, it is likely that for each vertex $v_i$, it will have at most 5 neighbors among $\{v_1,...,v_{i-1}\}$. Therefore, using the Greedy Coloring Algorithm with the smallest-last ordering on a planar graph typically uses at most 6 colors. While the 4-Color Theorem guarantees that 4 colors are always sufficient for planar graphs, the greedy algorithm with this heuristic often performs reasonably well in practice.

Corollary: For a connected graph $G=(V,E)$, if there exists a vertex $v\in V$ with degree $\text{deg}(v)<\Delta (G)$, then using the smallest-last ordering (or even BFS/DFS ordering), the Greedy Coloring Algorithm will use at most $\Delta (G)$ colors. This is a slight improvement over the general $\Delta (G)+1$ bound.

Block Graphs and Coloring

Finally, let’s briefly mention block graphs. A block in a graph is a maximal 2-connected subgraph (or a bridge or an isolated vertex). Block graphs have a tree-like structure in terms of their blocks.

Property of Block Graphs and Coloring:

If a graph $G$ is such that every block in $G$ can be colored with $k$ colors, then the entire graph $G$ can also be colored with $k$ colors.

Algorithm Idea for Coloring Block Graphs:

1. Color Blocks Individually: Color each block of $G$ with $k$ colors.
2. Handle Articulation Points: Blocks can share vertices, specifically articulation points (cut vertices). When coloring blocks, we need to ensure consistency in colors assigned to articulation points. We can achieve this by potentially performing color interchanges (permutations of color classes) within blocks to ensure that when we move from one block to an adjacent block (sharing an articulation point), the coloring remains valid at the articulation point.

By carefully coloring blocks and managing colors at articulation points, we can extend k-colorings of individual blocks to a k-coloring of the entire block graph. This is a useful technique for simplifying the coloring problem for certain types of graphs by breaking them down into smaller, more manageable components (blocks).

Continue here: 08 Five-Color Theorem, Brooks Theorem, 3-Colorable Coloring Approximation, Randomness