Re:Graph Coloring Methods
by siegelzero on Wednesday September 25, 2024 @02:45PM
(#41650598)
I can recommend the book Guide to Graph Colouring: Algorithms and Applications by Lewis. It covers techniques including some state of the art methods for getting good but not provably optimal colorings. It discusses in depth local search and hybrid evolutionary algorithms, which tend to be the best performing on academic benchmarks (DIMACS graphs and large random graphs).
Users might find this paragraph from the Preface helpful:
> This book is about graph coloring, one of the most popular and widely-studied areas of discrete mathematics. The intended reader is a graduate student or early career researcher, although it should be useful for readers who are both less and more experienced. The reader may find it useful to have taken a 1-semester course in graph theory, but this is not strictly necessary. My goal as the author is to help you understand, internalize, and add to (if you like) central results in many areas of graph coloring.
The first chapter also states:
> In this book we focus on the existence of colorings, rather than on algorithms to produce them
Does anyone know of resources for learning or implementing algorithms for graph colouring?