**DIMACS - Series in Discrete Mathematics and Theoretical Computer Science**

Volume: 49;
1999;
389 pp;
Hardcover

MSC: Primary 05; 06; 11; 60; 68; 92;

**Print ISBN: 978-0-8218-0963-1
Product Code: DIMACS/49**

List Price: $118.00

AMS Member Price: $94.40

MAA Member Price: $106.20

**Electronic ISBN: 978-1-4704-4007-7
Product Code: DIMACS/49.E**

List Price: $111.00

AMS Member Price: $88.80

MAA Member Price: $99.90

# Contemporary Trends in Discrete Mathematics: From DIMACS and DIMATIA to the Future

Share this page *Edited by *
*Ronald L. Graham; Jan Kratochvíl; Jaroslav Nešetřil; Fred S. Roberts*

A co-publication of the AMS and DIMACS

Discrete mathematics stands among the leading disciplines of
mathematics and theoretical computer science. This is due primarily to
its increasing role in university curricula 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.

Co-published with the Center for Discrete Mathematics and Theoretical Computer Science beginning with Volume 8. Volumes 1–7 were co-published with the Association for Computer Machinery (ACM).

#### Readership

Graduate students and research mathematicians interested in discrete mathematics, theoretical computer science and applications; operations research scientists and computer scientists.

# Table of Contents

## Contemporary Trends in Discrete Mathematics: From DIMACS and DIMATIA to the Future

- Cover Cover11
- Frontispiece iv5
- Title page v6
- Contents vii8
- Foreword ix10
- Preface xi12
- Program xv16
- List of participants xvii18
- Acyclic improper colourings of graphs with bounded degree 120
- Intersection graphs of Jordan arcs 1130
- Linear and nonlinear systems: A survey 2948
- Parameterized complexity: A framework for systematically confronting computational intractability 4968
- On the structure of large homothetic subsets 101120
- The complexity of an inverse shortest paths problem 113132
- Finding minimum weighted generators of a path system 129148
- On the distribution of sums of vectors in general position 139158
- The generalized matching problem on partial 𝑘-trees 143162
- Bases of cocycle lattices and submatrices of a Hadamard matrix 159178
- On the maximum lengths of Davenport-Schinzel sequences 169188
- On the minimum number of edges giving maximum oriented chromatic number 179198
- New trends in the theory of graph colorings: Choosability and list coloring 183202
- Topological minors in graphs of minimum degree 𝑛 199218
- Reducible properties and uniquely partitionable graphs 213232
- Induced monochromatic subconfigurations 219238
- Density 229248
- Spectra, graphs, and proteins. Towards understanding of protein folding 237256
- Meaningless statements 257276
- Graceful matchings in finite fields, the factor-difference sets of integers, and integers of the form 𝑎²+𝑘𝑏² 275294
- How to solve a Turán type extremal graph problem? (Linear decomposition) 283302
- Oriented list colouring of undirected graphs 307326
- On the limit values of probabilities for the first order properties of graphs 317336
- Ramsey theory and partially ordered sets 337356
- Generalizations of Davenport-Schinzel sequences 349368
- Back Cover Back Cover1409