Literature on graph coloring

[acken@informatik.uni-kl.de]

[Bri92]
  P. Briggs
  Register Allocation via Graph Coloring
  Ph.D. thesis, Rice University, Houston, Texas, 1992
  available as Technical Report Rice COMP TR92-183
  ftp://cs.rice.edu/public/preston/thesis.ps.gz (154 pages)

Covers the algorithm for graph coloring, its extension to register
pairs, and the technique of rematerialization in some detail.  Also
gives hints how to handle 2-address target architectures and multiple
register classes (like in the m68k architecture).  Most of the results
presented in this paper are applicable to hierarchical graph coloring,
too.  

[BCT94]
  P. Briggs, K. D. Cooper, and L. Torczon 
  "Improvements to Graph Coloring Register Allocation" 
  ACM Transactions on Programming Languages and Systems (TOPLAS),
  16(3):428-455, May 1994.
  http://www.cs.rice.edu/MSCP/papers/toplas94.ps.gz

Covers the most important stuff from [Bri92].  Saves a lot of paper,
too.  The postscript file is just 24 pages, compared to 154 of the
thesis.