GRAPH COLORING THEORY AND ITS APPLICATION IN SCHEDULING PROBLEMS

Background to the Study

Graph coloring is among the most immediately applicable branches of discrete mathematics, providing an exact mathematical framework for any problem in which a set of objects must be assigned to categories, or resources, subject to pairwise conflict constraints forbidding certain pairs of objects from sharing the same category. Formally, given a graph G = (V,E), a proper vertex coloring assigns a color to every vertex such that no two adjacent vertices share a color, and the chromatic number χ(G) is the minimum number of colors required.

Though originating in the nineteenth-century Four Colour Problem concerning the coloring of political maps, eventually resolved by Kenneth Appel and Wolfgang Haken in 1976 using extensive computer assistance, graph coloring has since become a central tool in scheduling, resource allocation, register allocation in compilers, frequency assignment in wireless networks, and, of particular relevance to this study, examination and course timetabling.

The connection between scheduling and graph coloring is direct and exact: given a collection of events (examinations, courses, meetings) to be assigned to time slots, and a conflict relation identifying pairs of events that cannot occupy the same slot (most commonly, examinations with at least one common candidate, or courses with at least one common instructor or room requirement), one constructs a conflict graph in which vertices represent events and edges represent conflicts. A valid schedule using k time slots corresponds exactly to a proper k-coloring of this conflict graph, and the minimum number of time slots required for any valid schedule is exactly the chromatic number of the conflict graph. This correspondence transforms an operational scheduling question into a precise, well-studied mathematical problem, for which both exact (but computationally expensive) and heuristic (fast but not always optimal) solution methods exist.

This study undertakes a rigorous, proof-based development of graph coloring theory, including the chromatic polynomial and key structural bounds on the chromatic number, followed by an original computational investigation applying this theory to a genuine examination-timetabling conflict graph, verifying chromatic polynomial and chromatic number claims by independent exhaustive computation, and directly benchmarking exact and heuristic coloring algorithms to characterise, empirically, the practical trade-off between guaranteed optimality and computational feasibility that is central to the graph coloring problem's well-known NP-hardness.

Mathematics project topics on ScholarnestHub | Computer science project topics | External: MIT OpenCourseWare - Graph Theory, American Mathematical Society - Graph Coloring, Stanford CS - NP-Hardness

Statement of the Problem

While the correspondence between scheduling and graph coloring is well known, many applied treatments of examination or course timetabling either assert a scheduling solution without exhibiting the underlying conflict graph and verifying its chromatic number exactly, or rely exclusively on a single heuristic coloring algorithm without demonstrating, on a concrete instance, both the algorithm's speed advantage and its potential suboptimality relative to an exact method.

There is, therefore, a need for a treatment that constructs an explicit conflict graph for a genuine scheduling scenario, determines its chromatic number by a verifiable exact method, and directly compares exact and heuristic coloring algorithms on both correctness (number of colors used) and computational cost, rather than treating either property in isolation. This gap is particularly relevant for Nigerian institutions where examination timetabling must minimise sessions while avoiding candidate conflicts.

Aim and Objectives of the Study

The aim of this study is to investigate graph coloring theory and its application to scheduling problems, with particular emphasis on examination timetabling.

·         Develop the theoretical foundations of proper vertex coloring, the chromatic number, the chromatic polynomial, and key structural bounds (the clique-number lower bound and Brooks' theorem);

·         Construct a genuine examination-timetabling conflict graph and determine its chromatic number by exact backtracking search, with optimality independently confirmed via a clique lower bound;

·         Compute the chromatic polynomial of a specific graph by exhaustive enumeration and verify it against the known closed-form formula for cycle graphs;

·         Demonstrate explicitly, using a graph constructed for this purpose, the dependence of greedy coloring quality on vertex ordering; and

·         Directly benchmark exact backtracking search against greedy coloring on graphs of increasing size, characterising the empirical trade-off between optimality and computational cost.

Research Questions

·         How does the scheduling problem of assigning conflicting events to a minimum number of time slots correspond exactly to the graph coloring problem?

·         What is the minimum number of examination slots required for a genuine conflict graph, and how can this minimum be verified as exact rather than merely achieved by some heuristic?

·         Does exhaustive enumeration of proper colorings confirm the known closed-form chromatic polynomial for a cycle graph?

·         How sensitive is the number of colors used by greedy coloring to the order in which vertices are processed?

·         How does the running time of exact chromatic-number computation compare with that of greedy coloring as graph size increases, and what does this reveal about the practical implications of the chromatic number problem's NP-hardness?

Significance of the Study

This study is significant academically because it connects graph theory, a core discrete mathematics subject, directly to an operational problem, timetabling, that every academic institution must solve. Pedagogically, it provides a fully worked, independently verified numerical example of the scheduling-to-coloring correspondence, together with original benchmark data illustrating the practical meaning of NP-hardness, a concept often introduced abstractly without direct computational demonstration.

Practically, the examination-timetabling application developed in this study is directly representative of the scheduling problems faced by Nigerian secondary and tertiary institutions, including WAEC and JAMB-style examination administration, where minimising the number of examination sessions while avoiding candidate conflicts is a genuine operational concern.

Methodologically, the study demonstrates how exact backtracking and exhaustive enumeration can verify theoretical claims, while also showing limitations of greedy heuristics under adversarial orderings, providing a template for rigorous applied graph theory research.

Operations research project topics | Algorithm analysis topics

Scope of the Study

The study covers proper vertex coloring, the chromatic number, the chromatic polynomial, the clique-number lower bound, and Brooks' theorem, together with one fully worked examination-timetabling application (eight courses, thirteen conflicts, χ=3), one chromatic polynomial verification for C5, one demonstration of greedy ordering-dependence using the crown graph on ten vertices (χ=2 but greedy uses 5 under adversarial order), and one direct computational benchmark of exact versus heuristic algorithms (up to 26 vertices, exact >1 second, greedy microseconds).

The study does not extend to edge coloring, list coloring, or the full proof of the Four Colour Theorem (whose only known proofs rely on extensive computer verification of thousands of cases), nor to more elaborate real-world timetabling constraints such as room capacity or instructor availability, which are noted as directions for further study.

Operational Definition of Terms

Graph: A pair G = (V,E) consisting of a set of vertices V and a set of edges E, each edge an unordered pair of distinct vertices.

Proper Vertex Coloring: An assignment of colors to the vertices of a graph such that no two adjacent vertices share the same color.

Chromatic Number: The minimum number of colors needed for a proper vertex coloring of a graph, denoted χ(G).

Chromatic Polynomial: The polynomial P(G,k) counting the number of proper colorings of G using at most k colors.

Clique: A subset of vertices that are pairwise adjacent; the clique number ω(G) is the size of the largest clique, giving lower bound ω(G) ≤ χ(G).

Conflict Graph: A graph constructed from a scheduling problem in which vertices represent events and edges represent pairs of events that cannot be scheduled simultaneously.

Greedy Coloring: A heuristic coloring algorithm that processes vertices in some order, assigning each the smallest available color not used by its already-colored neighbours.

NP-hard: A complexity classification indicating that no polynomial-time exact algorithm is known (or, under P≠NP, exists) for solving it exactly in the worst case.

Conclusion

The study demonstrates that graph coloring provides an exact and computationally verifiable framework for minimum-conflict scheduling. By constructing an eight-course conflict graph with thirteen overlaps and proving χ=3 via exact backtracking matched by a 3-clique lower bound, it shows three examination slots are both necessary and sufficient.

Verification of the chromatic polynomial for C5 as (k−1)^5−(k−1) by exhaustive enumeration for k=1..5 confirms theory computationally. The crown graph on ten vertices illustrates that greedy coloring quality depends materially on vertex ordering – bipartite graphs (χ=2) can be colored with five colours under adversarial order, 2.5× optimum, while largest-first, smallest-last, and saturation-largest-first heuristics recover optimality.

Benchmarking reveals the practical trade-off implied by NP-hardness: exact algorithm time grows sharply and irregularly (exceeding one second at 26 vertices) while greedy remains in microseconds but may use one extra colour. The findings validate graph coloring as both theoretically exact and practically implementable for timetabling, with heuristic choice and ordering critical for solution quality.

Frequently Asked Questions (FAQs)

What is graph coloring theory?

Graph coloring assigns colors to vertices so that no two adjacent vertices share a color; the chromatic number χ(G) is the minimum colors needed, central to scheduling and resource allocation.

How does graph coloring apply to examination timetabling?

Courses become vertices, edges link courses with common students, a proper k-coloring gives a valid k-slot timetable, and χ(G) equals minimum slots required.

What is chromatic number and why does it matter?

Chromatic number is the smallest number of colors for proper coloring; in scheduling it is the optimal minimum time slots needed to avoid all conflicts.

What is chromatic polynomial for C5?

For the 5-cycle, P(C5,k) = (k−1)^5 − (k−1), verified in this study by exhaustive enumeration for k=1..5 matching the closed-form formula.

What is clique-number lower bound?

Any clique of size ω needs ω distinct colors, so ω(G) ≤ χ(G). Finding a 3-clique proves at least 3 slots are necessary, matching upper bound to prove optimality.

What is Brooks' theorem?

Brooks' theorem states that for connected graphs not complete or odd cycle, χ(G) ≤ Δ(G), where Δ is maximum degree, providing a useful upper bound.

Why does greedy coloring depend on vertex order?

Greedy assigns smallest available color; adversarial orders (as in crown graph on 10 vertices) can force 5 colors on a bipartite graph with χ=2, while degree-based orders recover optimal 2.

What is crown graph and why use it?

Crown graph is bipartite with χ=2 but demonstrates worst-case greedy behavior; largest-first, smallest-last, DSATUR all find optimum while adversarial order uses 2.5× optimum.

Is graph coloring NP-hard?

Yes, computing chromatic number is NP-hard. Exact backtracking grows exponentially (over 1 sec at 26 vertices in benchmark) while greedy stays microseconds but may be suboptimal.

How can this be applied in Nigerian institutions?

WAEC, JAMB, and universities face candidate-overlap constraints; constructing conflict graphs and using exact/heuristic coloring minimizes examination sessions while avoiding clashes.