×

New directions in graph theory (with an emphasis on the role of applications). (English) Zbl 0787.05089

Gimbel, John (ed.) et al., Quo vadis, graph theory? A source book for challenges and directions. Amsterdam: North-Holland. Ann. Discrete Math. 55, 13-43 (1993).
The author summarizes some of the themes he saw coming out of the Quo Vadis Graph Theory international conference that was held in August 1990 at the University of Alaska in Fairbanks. He admits to letting his personal preferences influence his choice of the specific topics which are listed below. The bibliography consists of an impressive list of 208 references which should prove useful to all researchers in the area.
Graph Coloring: Defective colorings, list colorings, \(T\)-colorings, \(H\)- colorings, \(I\)-colorings, \(J\)-colorings, \(D\)-colorings, \(n\)-tuple colorings.
Distance Concepts: Distance concepts on graphs, facility location problems, clustering problems, chemical applications, geometric graphs, metrics between graphs.
Intersection Graphs.
Other Variants Briefly Mentioned: Vulnerability, domination, tournaments, graph polynomials, coverings, matchings, planarity, crossing numbers, extremal problems, Ramsey theory.
Algorithms: On-line algorithms, existence of algorithms, algorithms based on lies, approximation algorithms and algorithms that may work on special classes of graphs, parallel and distributed algorithms, probabilistic algorithms.
Applied Problems: Genetics, chemistry, communication networks/information management, social sciences (balance, sign stability, pulse processes, meaningfulness of conclusions, social networks), relations to pure mathematics.
Randomness: Random graphs, deterministic graph problems arising from random graphs, the probabilistic method, probability and algorithms.
The Need for New Concepts.
The Role of Graph Theory in Mathematical Education.
For the entire collection see [Zbl 0773.00007].
Reviewer: S.Stahl (Lawrence)

MSC:

05C99 Graph theory
05C90 Applications of graph theory
PDFBibTeX XMLCite