"Both authors are excellent expositors-exceptionally so-and this makes for a pleasurable read and allows for clear understanding of the mathematical concepts." -Joel Spencer Fractional Graph Theory explores the various ways in which integer-valued graph theory concepts can be modified to derive nonintegral values. Based on the authors' extensive review of the literature, it provides a unified treatment of the most important results in the study of fractional graph concepts. Professors Scheinerman and Ullman begin by developing a general fractional theory of hypergraphs and move on to provide in-depth coverage of fundamental and advanced topics, including fractional matching, fractional coloring, and fractional edge coloring; fractional arboricity via matroid methods; and fractional isomorphism. The final chapter is devoted to a variety of additional issues, such as fractional topological graph theory, fractional cycle double covers, fractional domination, fractional intersection number, and fractional aspects of partially ordered sets. Supplemented with many challenging exercises in each chapter as well as an abundance of references and bibliographic material, Fractional Graph Theory is a comprehensive reference for researchers and an excellent graduate-level text for students of graph theory and linear programming.
Author(s): Edward R. Scheinerman, Daniel H. Ullman
Series: Wiley Series in Discrete Mathematics and Optimization
Edition: 1
Publisher: Wiley-Interscience
Year: 2008
Language: English
Commentary: Vector PDF with bookmarks, cover and pagination
Pages: 169
Table of Contents
Cover
Fractional Graph Theory - A Rational Approach to the Theory of Graphs
ISBN-10: 0471178640 ISBN-13: 9780471178644
Contents
Foreword
Preface
Rationalization
Goals
Chapter Overview
Acknowledgments
Feedback
Finally
Exercise
1 General Theory: Hypergraphs
1.1 Hypergraph covering and packing
1.2 Fractional covering and packing
1.3 Some consequences
1.4 A game-theoretic approach
1.5 Duality and duality
1.6 Asymptotic covering and packing
1.7 Exercises
1.8 Notes
2 Fractional Matching
2.1 Introduction
2.2 Results on maximum fractional matchings
Fractional Tutte's theorem
Fractional Berge's theorem
Fractional Gallai's theorem
2.3 Fractionally Hamiltonian graphs
The middle levels problem: a fractional solution
2.4 Computational complexity
2.5 Exercises
2.6 Notes
3 Fractional Coloring
3.1 Definiions
3.2 Homomorphisms and the Kneser graphs
3.3 The duality gap
3.4 Graph products
A communication complexity story
3.5 The asymptotic chromatic and clique numbers
3.6 The fractional chromatic number of the plane
3.7 The Erd os-Faber-Lovasz conjecture
3.8 List coloring
3.9 Computational complexity
3.10 Exercises
3.11 Notes
4 Fractional Edge Coloring
4.1 Introduction
The edge chromatic number
The fractional edge chromatic number
4.2 An exact formula
4.3 The matching polytope
4.4 Proof and consequences
4.5 Computational complexity
4.6 Fractional total chromatic number
4.7 Exercises
4.8 Notes
5 Fractional Arboricity and Matroid Methods
5.1 Arboricity and maximum average degree
5.2 Matroid theoretic tools
Basic de.nitions
Bases
Rank
Circuits
5.3 Matroid partitioning
5.4 Arboricity again
5.5 Maximum average degree again
5.6 Duality, duality, duality, and edge toughness
Hypergraph duality and mathematical programming duality
Matroid duality
Dual rank
Covering number of the dual of a matroid
Edge toughness
5.7 Exercises
5.8 Notes
6 Fractional Isomorphism
6.1 Relaxing isomorphism
Another view
6.2 Linear algebra tools
Direct sum and reducibility
Positive matrices: the Perron-Frobenius theorem
Doubly stochastic matrices: Birkho. decomposition
Kronecker product
6.3 Equitable partitions
6.4 Iterated degree sequences
6.5 The main theorem
Some consequences
6.6 Other relaxations of isomorphism
Semi-isomorphism
6.7 Exercises
6.8 Notes
7 Fractional Odds and Ends
7.1 Fractional topological graph theory
Fractional genus
Fractional crossing number
Fractional thickness
7.2 Fractional cycle double covers
7.3 Fractional Ramsey theory
7.4 Fractional domination
The duality gap
Fractional Vizing conjecture
7.5 Fractional intersection number
7.6 Fractional dimension of a poset
7.7 Sperner's theorem: a fractional perspective
7.8 Exercises
7.9 Notes
Appendix A Background
A.1 Basic graph theory and notation
A.2 Hypergraphs, multigraphs, multisets, fuzzy sets
A.3 Linear programming
Computational complexity
A.4 The subadditivity lemma
A.5 Exercises
A.6 Notes
Bibliography
Author Index
Subject Index
