Recent results in graph decompositions

Summary

INTRODUCTION

The subject of graph decompositions is a vast and sprawling topic, one which we certainly cannot begin to cover in a paper of this length. Indeed, recently a number of survey articles and several books have appeared, each devoted to a particular subtopic within this domain (e.g., see [Fi-Wi], [Gr-Rot-Sp],[So 1],[Do-Ro]).

What we will attempt to do in this report is twofold. First, we will try to give a brief overall view of the landscape, mentioning various points of interest (to us) along the way. When possible, we will provide the reader with references in which much more detailed discussions can be found. Second, we will focus more closely on a few specific topics and results, usually for which significant progress has been made within the past few years. We will also list throughout various problems, questions and conjectures which we feel are interesting and/or contribute to a clearer understanding of some of the current obstacles remaining in the subject.

Notation

By a graph G we will mean a (finite) set V = V(G), called the vertices of G together with a set E = E(G) of (unordered) pairs of vertices of G, called the edges of G.

Let H denote a family of graphs. By an H-decomposition of G we mean a partition of E(G) into disjoint sets E(H.) such that each of the graphs Hi induced by the edge set E(H_i) is isomorphic to a graph in H.