Graph Theory and combinatorics 1988, Proceedings of the Cambridge Combinatorial Conference in Honour of Paul Erdös

B. Bollobás (Eds.)978-0-444-87329-3

Combinatorics has not been an established branch of mathematics for very long: the last quarter of a century has seen an explosive growth in the subject. This growth has been largely due to the doyen of combinatorialists, Paul Erdos, whose penetrating insight and insatiable curiosity has provided a huge stimulus for workers in the field. There is hardly any branch of combinatorics that has not been greatly enriched by his ideas. This volume is dedicated to Paul Erdos on the occasion of his seventy-fifth birthday.

---

Table of contents :
Content:
General Editor:
Page ii

Edited by
Page iii

Copyright page
Page iv

Preface
Page 1
B. Bollobiis

Paul ErdÕs at Seventy-Five Original Research Article
Pages 3-5
Béla Bollobás

Packing Smaller Graphs into a Graph Original Research Article
Pages 7-9
Jin Akiyama, Fumi Nakada, Sinichi Tokunaga

The Star Arboricity of Graphs Original Research Article
Pages 11-22
I. Algor, N. Alon

Graphs with a Small Number of Distinct Induced Subgraphs Original Research Article
Pages 23-30
Noga Alon, Béla BollobÁs

Extensions of Networks with Given Diameter Original Research Article
Pages 31-40
J.-C. Bermond, K. Berrada, J. Bond

Confluence of some Presentations Associated with Graphs Original Research Article
Pages 41-46
Norman Biggs

Long Cycles in Graphs With no Subgraphs of Minimal Degree 3 Original Research Article
Pages 47-53
Béla BollobÁs, Graham Brightwell

First Cycles in Random Directed Graph Processes Original Research Article
Pages 55-68
Béla Bollobás, Steen Rasmussen

Trigraphs Original Research Article
Pages 69-79
J.A. Bondy

On Clustering Problems with Connected Optima in Euclidean Spaces Original Research Article
Pages 81-88
Endre Boros, PeterL. Hammer

Some Sequences of Integers Original Research Article
Pages 89-102
PeterJ. Cameron

1-Factorizing Regular Graphs of High Degree-an Improved Bound Original Research Article
Pages 103-112
A.G. Chetwynd, A.J.W. Hilton

Graphs with Small Bandwidth and Cutwidth Original Research Article
Pages 113-119
F.R.K. Chung, P.D. Seymour

Simplicial Decompositions of Graphs: a Survey of Applications Original Research Article
Pages 121-144
Reinhard Diestel

On The Number of Distinct Induced Subgraphs of a Graph Original Research Article
Pages 145-154
P. ErdÕs, A. Hajnal

On The Number of Partitions of N Without a Given Subsum (I) Original Research Article
Pages 155-166
P. Erdõs, J.L. Nicolas, A. Sárkõzy

The First Cycles in an Evolving Graph Original Research Article
Pages 167-215
Philippe Flajolet, DonaldE. Knuth, Boris Pittel

Covering the Complete Graph by Partitions Original Research Article
Pages 217-226
Zoltán Füredi

A Density Version of the Hales-Jewett Theorem for K = 3 Original Research Article
Pages 227-241
H. Furstenberg, Y. Katznelson

On the Path-Complete Bipartite Ramsey Number Original Research Article
Pages 243-245
Roland Häggkvist

Towards a Solution of the Dinitz Problem? Original Research Article
Pages 247-251
Roland Häggkvist

A Note on Latin Squares with Restricted Support Original Research Article
Pages 253-254
Roland Häggkvist

Pseudo-Random Hypergraphs Original Research Article
Pages 255-278
Julie Haviland, Andrew Thomason

Bouquets of Geometric Lattices: some Algebraic and Topological Aspects Original Research Article
Pages 279-313
Monique Laurent, Michel Deza

A Short Proof of a Theorem of VÁmos on Matroid Representations Original Research Article
Pages 315-317
Imre Leader

An On-Line Graph Coloring Algorithm with Sublinear Performance Ratio Original Research Article
Pages 319-325
László Lovász, Michael Saks, W.T. Trotter

The Partite Construction and Ramsey Set Systems Original Research Article
Pages 327-334
Jaroslav neŝetril, Vojtêch Rödl

Scaffold Permutations Original Research Article
Pages 335-342
P. Rosenstiehl

Bounds on the Measurable Chromatic Number of Rn: “Sight may distinguish of colours; but suddenly To nominate them all, ‘s impossible.” -W. Shakespeare, King Henry VZ, Part ZZ. Original Research Article
Pages 343-372
L.A. Székely, N.C. Wormald

A Simple Linear Expected Time Algorithm for Finding a Hamilton Path Original Research Article
Pages 373-379
Andrew Thomason

Dense Expanders and Pseudo-Random Bipartite Graphs Original Research Article
Pages 381-386
Andrew Thomason

Forbidden Graphs for Degree and Neighbourhood Conditions Original Research Article
Pages 387-404
D.R. Woodall

Combinatorics 1988: List of Contributors
Pages 405-407

Author Index
Pages 409-410