Talk:Graph coloring

Article Checklist for "Graph coloring"

Workgroup category or categories	Mathematics Workgroup, Computers Workgroup [Categories OK]
Article status	Developed article: complete or nearly so
Underlinked article?	Yes
Basic cleanup done?	Yes
Checklist last edited by	Greg Woodhouse 12:19, 30 April 2007 (CDT)

To learn how to fill out this checklist, please see CZ:The Article Checklist.

---

Mathematics or Computer science?

My initial impression of this article is that there is a lot of good content here, and the article does a good job of basic terms. But one problem is that the article tries to be both a mathematics article and a computer science article. To some extent, this is unavoidable because the mathematical terminology may not be familiar to compiler designers, and it is useful to all readers to have a sense of the breadth of applicability of graph coloring. But, unfortunately, the result is that the article jumps back and forth between disciplines to some extent, and really doesn't do justice to either. My recommendation is to write a separate article on graph coloring in mathematics, perhaps summarizing the basic terminology and results in the computer science article. A more detailed account, say, of register allocation would be useful. In the mathematics article it would be interesting to hear a bit more about Sudoku. The article should also talk about th solution of the 4-color problem and (personal bias!) G. Ringel's work on colorings of graphs on surfaces other than the sphere. It would be nice to see a bit more about edge coloring and tractability. Greg Woodhouse 12:30, 30 April 2007 (CDT)