To order through AMS contact the AMS Customer Services Department, P.O. Box 6248, Providence, Rhode Island 02940-6248 USA. For Visa, Mastercard, Discover, and American Express orders call 1-800-321-4AMS.
You may also visit the AMS Bookstore and order directly from there. DIMACS does not distribute or sell these books.
Discrete mathematics stands among the leading disciplines of mathematics and theoretical computer science. This is due primarily to its increasing role in university curriculae and its growing importance in applications ranging from optimization to molecular biology. An inaugural conference was held cooperatively by DIMATIA and DIMACS to focus on the versatility, width, and depth of current progress in the subject area.
This volume offers a well-balanced blend of research and survey papers reflecting the exciting, attractive topics in contemporary discrete mathematics. Discussed in the book are topics such as graph theory, partially ordered sets, geometrical Ramsey theory, computational complexity issues and applications.
Forword ix Preface xi Program xv List of participants xvii Acyclic improper colourings of graphs with bounded degree P. Boiron, E. Sopena, and L. Vignal 1 Intersection graphs of Jordan arcs P. Ossona de Mendez and H. de Fraysseix 11 Linear and nonlinear systems: A survey J. Diaz, M. Serna, and P. Spirakis 29 Parameterized complexity: A framework for systematically confronting computational intractability R. G. Downey, M. R. Fellows, and U. Stege 49 On the structure of large homothetic subsets G. Elekes 101 The complexity of an inverse shortest paths problem S. P. Fekete, W. Hochstattler, S. Kromberg, and C. Moll 113 Finding minimum weighted generators of a path system A. Frank 129 On the distribution of sums of vectors in general position J. R. Griggs and G. Rote 139 The generalized matching problem on partial $k$-trees A. Gupta, D. Kaller, S. Mahajan, and T. Shermer 143 Bases of cocycle lattices and submatrices of a Hadamard matrix W. Hochstattler and M. Loebl 159 On the maximum lengths of Davenport-Schinzel sequences M. Klazar 169 On the minimum number of edges giving maximum oriented chromatic number A. V. Kostochka, T. Luczak, G. Simonyi, and E. Sopena 179 New trends in the theory of graph colorings: Choosability and list coloring J. Kratochvil, Zs. Tuza, and M. Voigt 183 Topological minors in graphs of minimum degree $n$ W. Mader 199 Reducible properties and uniquely partitionable graphs P. Mihok 213 Induced monochromatic subconfigurations J. Nesetril, J. Solymosi, and P. Valtr 219 Density J. Nesetril and C. Tardif 229 Spectra, graphs, and proteins. Towards understanding of protein folding P. Pancoska, V. Janota, and J. Nesetril 237 Meaningless statements F. S. Roberts 257 Graceful matchings in finite fields, the factor-difference sets of integers, and integers of the form a2 + kb2 M. Rosenfeld 275 How to solve a Turán type extremal graph problem? (Linear decomposition) M. Simonovits 283 Oriented list colouring of undirected graphs A. Sali and G. Simonyi 307 On the limit values of probabilities for the first order properties of graphs J. Spencer and L. Thoma 317 Ramsey theory and partially ordered sets W. T. Trotter 337 Generalizations of Davenport-Schinzel sequences P. Valtr 349