[Search] |

ABOUT:
[Introduction]POINTERS:
[Texts]## 05C: Graph theory |

[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.

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.

- 05C05: Trees
- 05C07: Degree sequences [new in 2000]
- 05C10: Topological graph theory, imbedding, See also 57M15, 57M25
- 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]
- 05C25: Graphs and groups, See also 20F32
- 05C30: Enumeration of graphs and maps
- 05C35: Extremal problems, See also 90C35
- 05C38: Paths and cycles, See also 90B10
- 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]
- 05C85: Graph algorithms, See also 68Q20, 68R10
- 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.

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.

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.

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.)

- Graph theory resources
- Graph drawing.
- Other Graph Theory and Related Pages
- Stewart and Xu's graph families page
- Traveling Salesman bibliography, software, links.
- UTK archives page

- A randomly selected response to the FAQ, "How do you solve the Traveling Salesman Problem?"
- Traveling Salesman: citations, some code.
- References and pointers for the Traveling Salesman problem
- Pointers to TSP code
- Summary: there are polynomial-time algorithms giving near-optimal results in the Traveling Salesman Problem.
- What's the best route from London to Edinburgh? (It's not the Traveling Salesman; it is polynomial-time.)
- The Chinese Postman problem: is a given eulerization of a graph optimal?
- Comparison of assignment problem and traveling salesman problem.
- How many tours on a hypercube? (No answer; it's the same as in the Cayley diagram of (Z/2Z)^n.)
- Tait's conjecture: polyhedra have Hamiltonian cycles through the vertex set (false), and its connection to the four-color theorem.
- The Köningsberg bridge problem: it is impossible to draw a path visiting each region in a certain picture without crossing certain edges twice.
- Pointer to software for combinatorial optimization (shortest path, etc.)
- Finding a minimal weight spanning tree (Kruskal's algorithm)
- Are highly symmetrical graphs always Cayley diagrams?
- Is there a Moore graph? (diameter 2, degree 57)
- Pointer to graph theory software.
- Pointer to (lecture notes and) algorithms for graphs (diameter, etc)
- How to describe graphs which can be 3-colored?
- Finding a 4-coloring of a planar graph is easy but checking for 3-colorability is an NP-complete problem
- How many colors needed to color a planar graph if opposite corners are considered touching (as at Four Corners USA)
- Mail from Tim Chow on coloring planar graphs.
- Perfect graphs (chromatic number = clique number)
- Mycielski's construction of graphs with high chromatic number but no small cycles
- Checking chromatic number of graphs derived from minimally-triangulated tori
- Two pointers to graph-coloring sites.
- Transcription of planar graph "requiring 5 colors" (joked Martin Gardner)
- [Offsite] New proof of the Four Color Theorem (simpler than Haken and Appel's original proof).
- Efficiently four-coloring planar graphs
- Chromatic number of genus-g graphs, with history.
- Four Color Theorem and analogues to surfaces with holes.
- Drawing 7 regions on a torus, each touching all others.
- You need infinitely many colors to color "maps" in R^3, even if the regions are convex subsets of R^3.
- Combinatorial question reducing to 2-colorability of a graph.
- Variants of Kuratowski's theorem for positive genus: graphs which prevent embeddings to surface of genus g.
- Applications of Kuratowski's theorem (planar graphs are those avoiding K_5 and K_{3,3}) and generalizations to higher genus.
- Determining the genus of a graph is NP-complete.
- Three utilities, three houses: K_{3,3} is not a planar graph.
- The genus of the Petersen graph, complete graphs, etc.
- The genus of K_{3,6} is 1; other K_{m,n}?
- Pointer: tournament scheduling program.
- Arranging a round-robin tournament
- Literature review on regular (completely-tied) tournaments; how rare are they?
- Number of graphs with n vertices.
- A graph whose symmetry group has order exactly 3.

Last modified 1999/05/12 by Dave Rusin. Mail: feedback@math-atlas.org