Graph Coloring Methods | Hacker News Reader

Graph Coloring Methods

graphcoloringmethods.com

71 pointssilasdb16 comments

This looks like a nice book. I took courses in graph theory and ramsey theory at university many years ago. Reading the first couple of pages of the first chapter, it's pitched at a good level for me to jump back into things.

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?

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).

I was expecting some pretty, colored graphs, but the book is in black and white.

From Wikipedia [0]:

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints.

[0] https://en.wikipedia.org/wiki/Graph_coloring

I'm surprised too, especially given that this seems primarily intended as a book to read online so the extra printing costs for color wouldn't be an issue. I imagine there are some places in the book where there are large numbers of "colors" and so it wouldn't be helpful to show them as actual colors - but surely there are some places where actual colors would be useful.

it makes more sense in the applications, asking AI, you get examples like how to schedule exams so that no student has a conflict, scheduling flight crews, radio frequency assignment to avoid overlap. e.g. "By representing flights as vertices and connecting edges between flights that share crew members, a coloring algorithm assigns crews to flights to minimize conflicts"

If you think you must ask AI for this, wait till you learn Wikipedia article you replied on says just that but with more sourced detail and less possibility for accidental falsehood

the falsehoods on wikipedia are usually purposeful deceptions so I tend not to bother with it as a go-to. net-net AI has about the same level of accuracy and lacks the actual mendacity.

almost none of us are going to move any discipline forward, let alone discover new math, but as part of the long tail of people who could benefit from recognizing classes of problems with solutions in the domain of graph colouring, AI is sufficient for most purposes.

sorry that nobody appreciates your effort though.

sorry to break it but AI is nothing but roughly speaking sum / average of data it is fed, if you believe it has some magic layer that excludes mendacity present in that data or in people who select which data to include...

Lots of academic authors have decided color is a gimmick (color printing is expensive and not clear how long-lived; grayscale printing kills yellow and light-green lines; then there is colorblindness). Certainly I agree that load-bearing color is to be avoided, and I do so in my own writing.

Daniel is a buddy of mine, and I'm proud of him for self-publishing this. I know 1st hand the crazy amount of hours he put into this over the last 8(?) years. Also relevant to this journey for him is his challenges with his tenured math superiors, leading him to 'leave' the math department for the engineering dept years ago. He chose to self-publish after nearly publishing with one of the math societies, which he's a member of, because he wanted this book to belong to the people doing the work. Big ups to the homie. I'll pass this thread along to him; feedback is appreciated!

Is there any good reference (in this book or another) that gives a sense of what coloring methods work well for various practical problems? Do they still use graph coloring for register allocation--and if so, which method is used?

I have heard of some people using the "degree saturation" method (DSATUR: https://en.wikipedia.org/wiki/DSatur), but a systematic review would be really interesting.

With so many methods, it'd be interesting to get some feel for what percentage of random graphs, or graphs of a particular type perhaps, can be optimally colored using each technique.

The subject reminds me of a YACC-like parser generator I wrote back in the early 80's... Using graph coloring to compress the parser tables.

My generator was more general than YACC, accepting LR(1) grammars rather than LALR(1) ones, a feat which was considered impractical at that time (said Aho & Ullman's "dragon book"). Certainly a canonical Knuth parser would be huge, but what made it possible was to use an at the time obscure state-combining technique invented by Prof. Pager. However, the resulting parse tables (2-D array, indexed by parser state and current symbol) were still huge, although sparse. One solution was to represent the tables as linked lists, but I wanted to instead compress them to keep the speed of array access.

The solution I used was to convert the sparse 2-D array to a graph, color the graph, then convert it back to a compressed array where non-conflicting (sparse) rows and columns had been combined.

The idea was to:

1) Convert each row of the 2-D array to a graph node, and connect that node to all other nodes who's corresponding row had a conflicting column entry.

2) Color the resulting graph (i.e. assign colors to nodes, such that connected nodes have different colors, using fewest possible colors). The simple but effective coloring heuristic I used was just to assign colors to the "hardest" (i.e. most constrained) nodes first - those with the most connections.

3) Convert the colored graph back to a 2-D array by combining all rows (nodes) of the same color, which by construction meant rows not having any conflicting entries would be combined, and the array would be compressed in accordance to how few colors had been used.

4) Repeat steps 1-3 for the columns.

What I liked about this algorithm was that any future research into optimal graph coloring could be applied to it to achieve better compression, although this was just a side project and I never did revisit it.

The resulting parsers (I implemented both K&R C and Modula-2) were indeed stupid fast due to just using array access. I don't remember how big the compressed tables were for these languages, but they happily ran on the Acorn 32016 2nd processor I was using for development (I did this while working for Acorn Computers).

Incidentally, the "do the hardest/most-constrained bits first" is a useful heuristic for many problems - e.g. I remember also using it so solve the "knight's tour" chessboard problem (have a knight visit each square on a chessboard exactly once).

I'm seeing some influence of [Diestel](https://diestel-graph-theory.com/) at least on the layout of the text.

"More precisely, it is NP-hard1. So it is unlikely that we will find an efficient algorithm to optimally solve the coloring problem on an arbitrary input graph. This fundamental hardness result casts a long shadow across the landscape of graph coloring."

Yes, but in practice heuristic approaches can work well, even if there are no guarantees of optimality. See for example my response about a simple "most constrained first" heuristic.

Why are colorings so well studied?

Reply on news.ycombinator.com