- The best source here is [BiLl].
- A good source for these kinds of applications is Fred Roberts (see
[Ro2]
and [Ro4]).
Graph theory is also being used extensively now in the human genome
project and other areas of biology.
- See the comments for Writing Project 2.
- See the comments for Writing Project 5.
- There should be some material in [EaTa]
and [Sk].
The author of the latter also has a Web
site on this topic. Using a search engine on the Web should turn up
some useful information, such as this Java-based site.
There are some graph-drawing macros in dialects of TeX. The wonderful software called The Geometer's
Sketchpad lets you manipulate geometric pictures, and it could come in
handy in this Project. Graph-drawing is an active area of research; see this Web page or this
one for other resources and information on current research. Probably
the best contemporary resources are as follows (these were gleaned from a
list
produced by Anthony Thyssen). Brendan McKay wrote a program
called nauty, which has a
good many graph theory algorithms. This program computes automorphism
groups, canonical labeling, and other things.
Hermann Stamm-Wilbrandt wrote a program called LEDA. It's a collection of algorithms
in C++ that one can use in writing programs. There is another interactive
graph-visualization system called daVinci. Finally, we
mention a program called Cabri-Graph.
- The definitive work is [KoSc].
Numerous Web sites, such as this one, deal
with the problem; try using a search engine to see what's available.
- Check out [Ra] and
this Web
site.
- Most advanced graph theory or combinatorics texts will mention
this. Look at [Ro1],
which also has further references. There is also a relevant chapter in [MiRo].
- Try general graph theory references, such as [BoMu],
[GrYe],
or [We]. A
specialized article on this topic is [Go2].
- There is a whole book on this topic, namely [La3].
Up-to-date information (such as the size of the largest traveling salesman
problem that has been solved) can also be found on the Web using a search
engine; one good site is called TSPBIB Home
Page.
- Try [BoMu]
or, better yet, books on graph algorithms like [ChOe]
or [Ev2].
- This would be a good time to search the Mathematical Reviews database, under
the keywords "book embedding" or "pagenumber".
- Try [Mi], [FrFr],
[SaKa],
or [WoWi].
For something quite new, follow this link.
- This is related to Writing Project 2
in Chapter 3; see the references listed there. Also see [ApHa]
and the references listed in Writing Project 13.
- One article to look at is B. Manvel's "Extremely greedy coloring
algorithms" in [HaMa],
which is a conference proceedings. It will be an educational experience to
browse through that volume, to see what research mathematicians do. Also,
books on algorithmic graph theory, such as [Mc] or
those mentioned above in the suggestion for Writing Project 11, will have
some material. A general source for graph algorithms, useful throughout
this chapter's Writing Projects, is The Stony Brook Algorithm
Repository; it has a section on coloring.
- There is a relevant article in [MiRo].
- There are entire books on random graphs and, more generally,
probabilistic methods in discrete mathematics. Two books to consult are [Bo2]
and the more elementary (and fun) [Pa].
There is also a paper-length introduction, [Bo3].
For something more general, try [AlSp],
although it is rather advanced.