[The Mathematical Atlas] [Search][Subject Index][MathMap][Tour][Help!]
[MathMap Icon]
ABOUT: [Introduction][History][Related areas][Subfields]
POINTERS: [Texts][Software][Web links][Selected topics here]

05C: Graph theory


Introduction

[Yes, a longer introduction to graph theory will eventually appear...]

Classified in the MSC as a subfield of 05: Combinatorics, Graph Theory has emerged as a related but largely independent discipline.

A graph is a set V of vertices and a set E of edges -- pairs of elements of V. This simple definition makes Graph Theory the appropriate language for discussing (binary) relations on sets, which is clearly a broad topic. Among the topics of interest are topological properties such as connectivity and planarity (can the graph be drawn in the plane?); counting problems (how many graphs of a certain type?); coloring problems (recognizing bipartite graphs, the Four-Color Theorem); paths, cycles, and distances in graphs (can one cross the Köningsberg bridges exactly once each?). There is a significant number of graph-theoretic topics which are the object of complexity studies in computation (e.g. the Traveling Salesman problem, sorting algorithms, the graph-isomorphism problem). The theory also extends to directed, labeled, or multiply-connected graphs.

History

See e.g. Wilson, Robin J.: "200 years of graph theory---a guided tour" Theory and applications of graphs (Proc. Internat. Conf., Western Mich. Univ., Kalamazoo, Mich., 1976), pp. 1--9. Lecture Notes in Math., Vol. 642, Springer, Berlin, 1978. MR58 #15981. A longer version appeared in book form: Biggs, Norman L.; Lloyd, E. Keith; Wilson, Robin J.: "Graph theory: 1736--1936" Clarendon Press, Oxford, 1976. 239 pp. MR56#2771

Applications and related fields

Particularly regular graphs are related to Group Theory. This includes discussion of automorphism groups, Cayley diagrams for groups, and regular graphs.

Many graph-theoretic problems can be solved by exhaustive enumeration; the questions then involve complexity. Further topics in this area are included in 68: Computer Science. (In particular this area of overlap includes topics such as the Traveling Salesman Problem, treated here.)

A graph may be viewed as a one-dimensional CW-complex and hence studied with tools from Algebraic Topology, in particular, questions of planarity (and genus).

There are some additional topics in Operations Research related to graph theory, including optimization of network flows and transportation.

Applications of graph theory to circuitry and networks are included in 94C15: Information theory.

Subfields

Parent field: 05: Combinatorics

Browse all (old) classifications for this area at the AMS.


Textbooks, reference works, and tutorials

Among the journals most significant in this field we mention the Journal of Combinatorial Theory, Series B primarily to date the separation of Graph Theory from Combinatorics proper; beginning 1971 (vol. 10) the Journal of Combinatorial Theory split into two concurrent Series each covering one of the two parts of what was until then covered as one whole.

Some texts include:

A unique complement is Capobianco, Michael; Molluzzo, John C.: "Examples and counterexamples in graph theory", North-Holland, New York-Amsterdam-Oxford, 1978. ISBN 0-444-00255-3.

A complete collection of abstracts of articles in Graph Theory is the "Reviews in Graph Theory 1940-1978", American Mathematical Society

Here is an Online text [Christopher P. Mawata] to accompany the Petersen software.

Online Graph theory tutorial

Online Graph theory glossary.

Look soon for "An atlas of graphs", Read and Wilson, Oxford U. P. See Bull. Inst. Combin. Appl. 12 (1994), 44--54.

There is a graph-theory mailing list; archives are available.

Software and tables

InterTools, an archive of interactive tools for discrete optimization algorithms to be used through the Internet

Online (Java) program to allow experimentation with graph drawing, coloring, etc.

experiment with undirected, unweighted graphs.

Nauty, a program for computing automorphism groups of graphs and digraphs.

Packages for Mathematica, versions 2.2 and 3.0. especially Combinatorica: A Mathematica Package for Combinatorics and Graph Theory

Stanford graphbase.

LEDA handles combinatoric and graph-theoretic problems as well as discrete geometry.

The answer to "How do I ... efficiently?" is often contained in some code at Netlib, say (traveling salesman, graph-coloring, etc.)

Other web sites with this focus

Selected topics at this site


You can reach this page through http://www.math-atlas.org/welcome.html
Last modified 2001/01/14 by Dave Rusin. Mail: