DIMACS Series in
Discrete Mathematics and Theoretical Computer Science

VOLUME Forty Nine
TITLE: "Contemporary Trends in Discrete Mathematics: From DIMACS and DIMATIA to the Future"
EDITORS: Ronald L. Graham, Kratochví, Jaroslav Nesetril and Fred S. Roberts.


Ordering Information

This volume may be obtained from the AMS or through bookstores in your area.

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.



PREFACE


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.


TABLE OF CONTENTS



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 Index of Volumes
DIMACS Homepage
Contacting the Center
Document last modified on November 8, 1999.