Graph Coloring Methods
Daniel W. Cranston
 

This is a graduate textbook about how to color graphs.  Each chapter studies a single method, and presents numerous examples applying that method, generally in order of increasing difficulty. The book is designed to be suitable for a topics course in graph coloring, as well as self-study. The chapters are listed below.

  1.  Greedy Coloring
  2.  Gadgets: Constructions for Lower Bounds
  3.  Recoloring
  4.  Vertex Identification: Coloring Planar Graphs
  5.  The Kernel Method
  6.  Deletion and Contraction: Nowhere-Zero Flows
  7.  Rosenfeld Counting
  8.  The Combinatorial Nullstellensatz
  9.  The Activation Strategy
  10.  The Vertex Shuffle
  11.  Precoloring Extension
  12.  The Potential Method
  13.  The Rest of the Story

This book is (and always will be) freely available for download.  It is released under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.  License details are available at https://creativecommons.org/licenses/by-nc-nd/4.0.

If you would like a paperback version, you can purchase one on Amazon. In the United States, it costs $24. It is also available in other markets: US  CA  UK  FR  IT  ES  DE  AU  NL  PL  SE  JP