 [Search][Subject Index][MathMap][Tour][Help!] # 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

• 05C05: Trees
• 05C07: Degree sequences [new in 2000]
• 05C12: Distance in graphs
• 05C15: Coloring of graphs and maps
• 05C17: Perfect graphs [new in 2000]
• 05C20: Directed graphs (digraphs), tournaments
• 05C22: Signed, gain and biased graphs [new in 2000]
• 05C30: Enumeration of graphs and maps
• 05C40: Connectivity
• 05C45: Eulerian and Hamiltonian graphs
• 05C50: Graphs and matrices
• 05C55: Generalized Ramsey theory
• 05C60: Isomorphism problems (reconstruction conjecture, perfect graphs, etc.)
• 05C62: Graph representations (geometric and intersection representations, etc.) [new in 2000]
• 05C65: Hypergraphs
• 05C69: Dominating sets, independent sets, cliques [new in 2000]
• 05C70: Factorization, matching, covering and packing
• 05C75: Structural characterization of types of graphs
• 05C78: Graph labelling (graceful graphs, bandwidth, etc.)
• 05C80: Random graphs
• 05C83: Graph minors [new in 2000]
• 05C90: Applications
• 05C99: None of the above but in this section

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:

• "Graph theory", by W.T. Tutte, Encyclopedia of Mathematics and its Applications v 21, Addison-Wesley Publishing Co., Reading, Mass., 1984. ISBN 0-201-13520-5 (A classic text by an eminent graph-theorist)
• "Pearls in graph theory, A comprehensive introduction", by Nora Hartsfield and Gerhard Ringel, Academic Press, Inc., Boston, MA, 1994 (revision of 1990 original) ISBN 0-12-328553-4
• "Graph Theory with Applications", by J.A. Bondy and U.S.R. Murty, Elsevier North-Holland 1976 -- a common undergraduate text.

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.

Mauty, a program for computing automorphism groups of graphs an 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.)