[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.
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
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.
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.)
- 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
- Pyramidal tours for the TSP
- Pointer to Traveling Salesman Challenge for code comparison
- 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?
- Pointers: Chinese Postman Problem
- 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.)
- Which graphs embed in a k-cube? (hard)
- 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.
- Polynomial-time algorithm to count paths in acyclic digraphs
- Euler cycles vs Hamiltonian cycles in a graph (when they exist)
- k shortest paths in a graph
- Pointer to software for combinatorial optimization (shortest path, etc.)
- Finding a minimal weight spanning tree (Kruskal's algorithm)
- Average (or total) lengths of the paths of a tree (Weiner index)
- Fan theorem (König's Theorem): finitely branching trees with only finite paths are finite
- Finding the k largest trees in a graph
- Constructing minimum spanning trees
- 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)
- Maximal number of maximal cliques in a graph with N vertices
- References to the Stable Marriages theorem
- Graham's number (very big!) in Ramsey Theory
- 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)
- Isn't the non-planarity of K5 sufficient to prove the four-color theorem? (no)
- [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.
- Chromatic numbers of non-planar graphs
- Computational complexity of n-coloring a planar graph?
- You need infinitely many colors to color "maps" in R^3, even if the regions are convex subsets of R^3.
- The p-colorability of knots and the dihedral groups
- 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.
- Non-planarity of K_{3,3} (the "three houses, three utilities" puzzle)
- 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}?
- Can planarity be expressed as a sentence in first-order logic? (no)
- Bounds for the number of cycles in a planar graph
- In any graph, an optimal traveling-salesman path is planar
- 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.
- No graphs on n vertices with automorphism group Alt(n) (the alternating group)
- Complexity of graph-isomorphism problem (NP but probably not NP-complete)
- Reduce Greechie-diagram isomorphism question to graph-isomorphism
- Pointers to Erdos problems in graph theory
- Graffiti -- program to generate conjectures in Graph Theory
- Pointers to resources on perfect graphs
You can reach this page through welcome.html
Last modified 2001/01/14 by Dave Rusin. Mail: ![[The Mathematical Atlas]](../images/title.gif)
![[MathMap Icon]](../images/mini.gif)