Quo Vadis, Graph Theory?A Source Book for Challenges and Directions

Description

Graph theory, as a recognized discipline, is a relative newcomer to mathematics. The first formal paper is found in the work of Leonard Euler in 1736. In recent years the subject has grown so rapidly that in today's literature, graph theory papers abound with mathematical developments and significant applications. As with any academic field, it is good to step back occasionally and ask "Where is all this activity taking us?", "What are the outstanding fundamental problems?", "What are the next important steps to take?" In short, "Quo vadis, graph theory?". The contributors to this volume aim, together, to provide a comprehensive reference source for future directions and open questions in the field. Content: Advisory Editors Page ii Edited by Page iii Copyright page Page iv Foreword Pages v-vi John Gimbel, John W. Kennedy, Louis V. Quintas Whither Graph Theory? Original Research Article Pages 1-3 William T. Tutte The Future of Graph Theory Original Research Article Pages 5-11 Bela Bollobás New Directions in Graph Theory (With an Emphasis on the Role of Applications) Original Research Article Pages 13-43 Fred S. Roberts A Survey of (m, k)-Colorings Original Research Article Pages 45-57 Marietjie Frick Numerical Decks of Trees Original Research Article Pages 59-69 Fanica Gavril, Ilia Krasikov, Johanan Schönheim The Complexity of Colouring by Infinite Vertex Transitive Graphs Original Research Article Pages 71-79 Bruce Bauslaugh Rainbow Subgraphs in Edge-Colorings of Complete Graphs Original Research Article Pages 81-88 Paul Erdős, Zsolt Tuza Graphs with Special Distance Properties Original Research Article Pages 89-92 Martin Lewinter Probability Models for Random Multigraphs with Applications in Cluster Analysis Original Research Article Pages 93-108 Erhard A.J. Godehardt Solved and Unsolved Problems in Chemical Graph Theory Original Research Article Pages 109-126 Alexandru T. Balaban Detour Distance in Graphs Original Research Article Pages 127-136 Gary Chartrand, Garry L. Johns, Songlin Tian Integer-Distance Graphs Original Research Article Pages 137-144 Ralph P. Grimaldi Toughness and the Cycle Structure of Graphs Original Research Article Pages 145-151 Douglas Bauer, Edward Schmeichel The Birkhoff-Lewis Equations for Graph-Colorings Original Research Article Pages 153-158 William T. Tutte The Complexity of Knots Original Research Article Pages 159-171 Dominic J.A. Welsh The Impact of F-polynomials in Graph Theory Original Research Article Pages 173-178 Edward J. Farrell A Note on Well-Covered Graphs Original Research Article Pages 179-181 Václav Chvátal, Peter J. Slater Cycle Covers and Cycle Decompositions of Graphs Original Research Article Pages 183-189 Cun-Quan Zhang Matching Extensions and Products of Graphs Original Research Article Pages 191-200 Jiping Liu, Qinglin Yu Prospects for Graph Theory Algorithms Original Research Article Pages 201-210 Ronald C. Read The State of the Three Color Problem Original Research Article Pages 211-248 Richard Steinberg Ranking Planar Embeddings Using PQ-Trees Original Research Article Pages 249-260 Almira Karabeg Some Problems and Results in Cochromatic Theory Original Research Article Pages 261-264 Paul Erdós, John Gimbel From Random Graphs to Graph Theory Original Research Article Pages 265-273 Andrzej Ruciński Matching and Vertex Packing: How “hard” are They? Original Research Article Pages 275-312 Michael D. Plummer The Competition Number and its Variants Original Research Article Pages 313-326 Suh-Ryung Kim Which Double Starlike Trees Span Ladders? Original Research Article Pages 327-331 Martin Lewinter, William F. Widulski The Random f-Graph Process Original Research Article Pages 333-339 Krystyna T. BalińSka, Louis V. Quintas Quo Vadis, Random Graph Theory? Original Research Article Pages 341-348 Edgar M. Palmer Exploratory Statistical Anlaysis of Networks Original Research Article Pages 349-365 Ove Frank, Krzysztof Nowicki The Hamiltonian Decomposition of Circulant Graphs Original Research Article Pages 367-373 Jiping Liu Discovery-Method Teaching in Graph Theory Original Research Article Pages 375-384 Phyllis Zweig Chinn Index of Key Terms Pages 385-397