Gimbel J., Kennedy J.W., Quintas L.V. (eds.) Quo Vadis, Graph Theory? A Source Book for Challenges and Directions

North-Holland, 1993. — 406 p. — (Annals of discrete mathematics, 55). — ISBN 0-444-89441-1.In the spectrum of mathematics, graph theory, as a recognized discipline, is a relative newcomer. The first formal paper is found in the work of Leonhard Euler in 1736. In recent years the subject has grown rapidly so that, in today's literature, mathematical and scientific, graph theory papers abound with new mathematical developments and significant applications. Three factors, perhaps, account for this explosive growth of the subject:
1) Graph theory provides the natural structures from which to construct mathematical models that are appropriate to almost all fields of scientific (natural and social) enquiry. The underlying subject of study in these fields is some set of "objects" and one or more "relations" between the objects.
2) Graph theory has developed a rich language of terms to render concise the expression of intricate concepts associated with object-relation structures. This facilitates, indeed encourages, interdisciplinary communication of ideas and techniques to the benefit of all fields that use graph theory.
3) Graph theory offers a huge selection of intellectual challenges that range in level from simple exercises for the novice, to deep open questions for the mathematical sophisticate. Many fascinating and compelling questions in graph theory are easy to comprehend, but their complete solutions are elusive. Nevertheless, in pursuit of these solutions, graph theorists are frequently rewarded by achieving results that contribute to further development of the subject.
As with any academic field, it is beneficial periodically to step back and ask: "Where is all this activity taking us?" "What are the outstanding fundamental problems?" "What are the next important steps we should take?" In short, "Quo Vadis, Graph Theory?" Thanks to our contributors, this volume offers a comprehensive reference source for future directions and open questions in graph theory.
The idea for this volume originated together with that for an international discussion meeting, also under the title "Quo Vadis, Graph Theory? " held at the University of Alaska, Fairbanks in August of 1990. By means of discussion, rather than by formal presentation of results, participants considered significant avenues for further exploration in graph theory. This volume is not a proceedings of that meeting; rather, it is a collection of papers written with the discussions of that meeting as background.
The first three papers in the volume are special in that they provide the reader with complementary perspectives on the future of graph theory in general. "Whither Graph Theory?" by William T. Tutte and "The Future of Graph Theory" by Bela Bollobas each take a philosophical approach. "New Directions in Graph Theory" by Fred S. Roberts offers a comprehensive overview of questions and developments in the subject with an emphasis on applications. It is with these three papers that we recommend that the reader start.
The remaining papers are arranged by topic, in the order used in the paper by Roberts. These papers elaborate on the potential for future developments in specific topics of graph theory. Among them the reader will find a rich source of worthwhile and challenging questions that await resolution.Whither graph theory?
The future of graph theory.
New directions in graph theory (with an emphasis on the role of applications).
A survey of (m, k)-colorings.
Numerical decks of trees.
The complexity of colouring by infinite vertex transitive graphs.
Rainbow subgraphs in edge-colorings of complete graphs.
Graphs with special distance properties.
Probability models for random multigraphs with applications in cluster analysis.
Solved and unsolved problems in chemical graph theory.
Detour distance in graphs.
Integer-distance graphs.
Toughness and the cycle structure of graphs.
The Birkhoff-Lewis equations for graph-colorings.
The complexity of knots.
The impact of F-polynomials in graph theory.
A note on well-covered graphs.
Cycle covers and cycle decompositions of graphs.
Matching extensions and products of graphs.
Prospects for graph theory algorithms.
The state of the three color problem.
Ranking planar embeddings using PQ-trees.
Some problems and results in cochromatic theory.
From random graphs to graph theory.
Matching and vertex packing: How "hard" are they?
The competition number and its variants.
Which double starlike trees span ladders?
The random f-graph process.
Quo vadis, random graph theory?
Exploratory statistical analysis of networks.
The Hamiltonian decomposition of certain circulant graphs.
Discovery-method teaching in graph theory.