No label defined (Q4382863)

The table of contents may serve as a short description of the topics covered: (1) General theory: Hypergraphs. (2) Fractional matching. (3) Fractional coloring. (4) Fractional edge coloring. (5) Fractional arboricity and matroid methods. (6) Fractional isomorphism. (7) Fractional odds and ends. Appendix: Background. Bibliography. Author index. Subject index. The Foreword by Claude Berge reads: Graph theory is one of the branches of modern mathematics having experienced a most impressive development in recent years. In the beginning, graph theory was only a collection of recreational or challenging problems like Euler tours or the four coloring of a map, with no clear connection among them, or among techniques used to attach them. The aim was to get a ``yes'' or ``no'' answer to simple existence questions. Under the impulse of game theory, management sciences, and transportation network theory, the main concern shifted to the maximum size of entities attached to a graph. For instance, instead of establishing the existence of a 1-factor, as did Petersen and also König (whose famous theorem on bipartite graphs was discovered 20 years earlier by Steinitz in his dissertation in Breslau), the main problem was now to study the maximum number of edges in a matching, even if not a 1-factor or ``perfect matching''. In this book, Scheinerman and Ullman present the next step of this evolution: fractional graph theory. Fractional matchings, for instance, belong to this new facet of an old subject, a facet full of elegant results. By developing the fractional idea, the purpose of the authors is multiple: first, to enlarge the scope of applications in scheduling, in operations research, or in various kinds of assignment problems; second, to simplify. The fractional version of a theorem is frequently easier to prove than the classical one, and a bound for a ``fractional'' coefficient of the graph is also a bound for the classical coefficient (or suggests a conjecture). A striking example is the simple and famous theorem of Vizing about the edge-chromatic number of a graph; no similar result is known for the edge-chromatic number of a hypergraph, but the reader will find in this book an analogous statement for the ``fractional'' edge-chromatic number which is a theorem. The conjecture of Vizing and Behzad about the total chromatic number becomes in its fractional version an elegant theorem. This book will draw the attention of the combinatorialists to a wealth of new problems and conjectures. The presentation is made accessible to students, who could find a clear exposition of the background material and a stimulating collection of exercises. And, above all, the pleasure afforded by these pages will contribute to making combinatorics more appealing to many.