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
Index of Volumes
DIMACS Homepage