Guide to Graph Colouring : algorithms and applications.

Preface
	Organisation and Features
	Audience
	Supplementary Resources
Contents
1 Introduction to Graph Colouring
	1.1 Some Simple Practical Applications
		1.1.1 A Team Building Exercise
		1.1.2 Constructing Timetables
		1.1.3 Scheduling Taxis
		1.1.4 Compiler Register Allocation
	1.2 Why Colouring?
	1.3 Problem Description
	1.4 About This Book
		1.4.1 Algorithm Implementations
	1.5 A Note on Pseudocode and Notation
	1.6 Chapter Summary
2 Problem Complexity
	2.1 Algorithm Complexity and Big O Notation
	2.2 Solving Graph Colouring via Exhaustive Search
	2.3 Problem Intractability
		2.3.1 mathcalP and mathcalNP
		2.3.2 Polynomial-Time Reductions
		2.3.3 mathcalNP-Completeness
		2.3.4 Boolean Satisfiability Problems (SAT)
	2.4 Proofs of mathcalNP-Completeness
	2.5 Graphs that are Easy to Colour Optimally
		2.5.1 Complete Graphs
		2.5.2 Cycle, Wheel, and Planar Graphs
		2.5.3 Grid Graphs
	2.6 Chapter Summary and Further Reading
3 Bounds and Constructive Heuristics
	3.1 The Greedy Algorithm for Graph Colouring
	3.2 Bounds on the Chromatic Number
		3.2.1 Lower Bounds
		3.2.2 Upper Bounds
	3.3 The DSATUR Algorithm
	3.4 Colouring Using Maximal Independent Sets
		3.4.1 The RLF Algorithm
	3.5 Empirical Comparison
		3.5.1 Experimental Considerations
		3.5.2 Algorithm Complexities
		3.5.3 Results and Analysis
	3.6 Chapter Summary and Further Reading
4 Advanced Techniques for Graph Colouring
	4.1 Exact Algorithms
		4.1.1 Backtracking Approaches
		4.1.2 Integer Programming
		4.1.3 Minimum Coverings and Column Generation
	4.2 Inexact Heuristics and Metaheuristics
		4.2.1 Feasible-Only Solution Spaces
		4.2.2 Spaces of Complete, Improper k-Colourings
		4.2.3 Spaces of Partial, Proper k-Colourings
		4.2.4 Combining Solution Spaces
		4.2.5 Problems Related to Graph Colouring
	4.3 Reducing Problem Size
		4.3.1 Removing Vertices and Splitting Graphs
		4.3.2 Extracting Independent Sets
	4.4 Chapter Summary
5 Algorithm Case Studies
	5.1 The TABUCOL Algorithm
	5.2 The PARTIALCOL Algorithm
	5.3 The Hybrid Evolutionary Algorithm (HEA)
	5.4 The ANTCOL Algorithm
	5.5 The Hill-Climbing (HC) Algorithm
	5.6 The Backtracking Algorithm
	5.7 Algorithm Comparison
		5.7.1 Random Graphs
		5.7.2 Flat Graphs
		5.7.3 Planar Graphs
		5.7.4 Scale-Free Graphs
		5.7.5 Exam Timetabling Graphs
		5.7.6 Social Network Graphs
		5.7.7 Comparison Discussion
	5.8 Further Improvements to the HEA
		5.8.1 Maintaining Diversity
		5.8.2 Recombination
		5.8.3 Local Search
	5.9 Chapter Summary and Further Reading
6 Applications and Extensions
	6.1 Face Colouring
		6.1.1 Dual Graphs, Colouring Maps, and the Four Colour Theorem
		6.1.2 Four Colours Suffice
	6.2 Edge Colouring
	6.3 Precolouring
	6.4 Latin Squares and Sudoku Puzzles
		6.4.1 Relationship to Graph Colouring
		6.4.2 Solving Sudoku Puzzles
	6.5 Short Circuit Testing
	6.6 Graph Colouring with Incomplete Information
		6.6.1 Decentralised Graph Colouring
		6.6.2 Online Graph Colouring
		6.6.3 Dynamic Graph Colouring
	6.7 List Colouring
	6.8 Equitable Graph Colouring
	6.9 Weighted Graph Colouring
		6.9.1 Weighted Vertices
		6.9.2 Weighted Edges
		6.9.3 Multicolouring
	6.10 Chromatic Polynomials
	6.11 Chapter Summary
7 Designing Seating Plans
	7.1 Problem Background
		7.1.1 Relation to Graph Problems
		7.1.2 Chapter Outline
	7.2 Problem Definition
		7.2.1 Objective Functions
		7.2.2 Problem Intractability
	7.3 Problem Interpretation and Tabu Search Algorithm
		7.3.1 Stage 1
		7.3.2 Stage 2
	7.4 Algorithm Performance
	7.5 Comparison to an IP Model
		7.5.1 Results
	7.6 Chapter Summary and Discussion
8 Designing Sports Leagues
	8.1 Problem Background
		8.1.1 Further Round-Robin Constraints
		8.1.2 Chapter Outline
	8.2 Representing Round-Robins as Graph Colouring Problems
	8.3 Generating Valid Round-Robin Schedules
	8.4 Extending the Graph Colouring Model
	8.5 Exploring the Space of Round-Robins
	8.6 Case Study:  Welsh Premiership Rugby
		8.6.1 Solution Methods
	8.7 Chapter Summary and Discussion
9 Designing University Timetables
	9.1 Problem Background
		9.1.1 Designing and Comparing Algorithms
		9.1.2 Chapter Outline
	9.2 Problem Definition and Preprocessing
		9.2.1 Soft Constraints
		9.2.2 Problem Complexity
		9.2.3 Evaluation and Benchmarking
	9.3 Previous Approaches to This Problem
	9.4 Algorithm Description: Stage One
		9.4.1 Results
	9.5 Algorithm Description: Stage Two
		9.5.1 SA Cooling Scheme
		9.5.2 Neighbourhood Operators
		9.5.3 Dummy Rooms
		9.5.4 Estimating Solution Space Connectivity
	9.6 Experimental Results
		9.6.1 Influence of the Neighbourhood Operators
		9.6.2 Comparison to Published Results
		9.6.3 Differing Time Limits
	9.7 Chapter Summary and Discussion
Appendix A Computing Resources
	A.1 Algorithm User Guide
		A.1.1 Usage
		A.1.2 Output
	A.2 Graph Colouring in Sage
	A.3 Graph Colouring in Python with NetworkX
	A.4 Generating Planar Graphs in Python
	A.5 Graph Colouring with Commercial IP Software
	A.6 Useful Web Links
B Table of Notation
Index