scientific article; zbMATH DE number 1131873
Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Combinatorial aspects of matroids and geometric lattices (05B35) Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Linear programming (90C05)
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.
- Worst case analysis of a greedy algorithm for graph thickness
- On the fractional chromatic number of monotone self-dual Boolean functions
- Set covering and packing formulations of graph coloring: Algorithms and first polyhedral results
- On types of growth for graph-different permutations
- Nordhaus-Gaddum inequalities for the fractional and circular chromatic numbers
- Minimum fractional dominating functions and maximum fractional packing functions
- On the ultimate lexicographic Hall-ratio
- On colorings of graph powers
- The fractional chromatic number, the Hall ratio, and the lexicographic product
- The fractional dimension of subsets of Boolean lattices and cartesian products
- On fractional Ramsey numbers
- Dot product representations of graphs
- Approximate strong separation with application in fractional graph coloring and preemptive scheduling.
- Tile invariants: New horizons.
- The multichromatic numbers of some Kneser graphs
- Fractional dominations and fractional total dominations of graph complements
- A neighborhood union condition for fractional ID-\([a, b]\)-factor-critical graphs
- Total \([1,2]\)-domination in graphs
- The fractional strong metric dimension in three graph products
- Integer \(k\)-matchings of graphs
- Fractional and circular separation dimension of graphs
- Strong resolving graphs: the realization and the characterization problems
- Gromov hyperbolicity in the Cartesian sum of graphs
- On complexities of minus domination
- The fractional chromatic number of triangle-free graphs with \(\varDelta \leq 3\)
- Some new bounds for cover-free families through biclique covers
- Rank, term rank and chromatic number of a graph
- Coloring the vertices of a graph with measurable sets in a probability space
- Resource-sharing system scheduling and circular chromatic number
- How important are branching decisions: fooling MIP solvers
- Planar graphs are \(9/2\)-colorable
- Graph imperfection. I
- Graph imperfection. II
- A class of matchings and a related lattice
- Chromatic number of distance graphs generated by the sets \(\{2,3,x,y\}\)
- Homomorphism bounds and edge-colourings of \(K_{4}\)-minor-free graphs
- Fractional \(f\)-edge cover chromatic index of graphs
- The fractional metric dimension of permutation graphs
- On maximal energy of line graphs with given parameters
- On a conjecture for the university timetabling problem
- On the expressive power of linear algebra on graphs
- The star dichromatic number
- Probabilistic refinement of the asymptotic spectrum of graphs
- On the global strong resilience of fault Hamiltonian graphs
- A note on maximum fractional matchings of graphs
- Rees algebras of filtrations of covering polyhedra and integral closure of powers of monomial ideals
- Fractional matching preclusion number of graphs
- Maximum size of a graph with given fractional matching number
- File placements, fractional matchings, and normal ordering
- Fractional cocoloring of graphs
- Spectral radius and \([a,b]\)-factors in graphs
- The nullity of a graph with fractional matching number
- The fractional \(k\)-truncated metric dimension of graphs
- The rank of a signed graph
- Independent domination, colorings and the fractional idomatic number of a graph
- Homomorphisms of partial \(t\)-trees and edge-colorings of partial 3-trees
- Fractional matching preclusion of product networks
- A game of hide and seek in networks
- The fractional (strong) matching preclusion number of complete \(k\)-partite graph
- The \(A_\alpha\)-spectral radius and perfect matchings of graphs
- On the strong metric dimension of the strong products of graphs
- Fractional aspects of the Erdős-Faber-Lovász conjecture
- Fractional matching preclusion of the restricted HL-graphs
- Matchings with few colors in colored complete graphs and hypergraphs
- Fractional matching preclusion number of graphs and the perfect matching polytope
- Remarks on fractional ID-\(k\)-factor-critical graphs
- Computing the weighted isolated scattering number of interval graphs in polynomial time
- Fractional matching preclusion for arrangement graphs
- A note on coloring vertex-transitive graphs
- \((\mathcal{P},\mathcal{Q})\)-total \((r,s)\)-colorings of graphs
- Fractional matching preclusion of graphs
- Asymptotic values of the Hall-ratio for graph powers
- How many attackers can selfish defenders catch?
- Some results on fractional n-factor-critical graphs
- Some results on binding number and fractional perfect matching
- Maximum fractional factors in graphs
- Toughness and the existence of fractional k-factors of graphs
- Independent sets in triangle-free cubic planar graphs
- Berge's theorem for the maximum charge problem
- The fractional chromatic number of triangle-free subcubic graphs
- Homomorphisms of binary Cayley graphs
- Generalized fractional total colorings of graphs
- Generalized fractional and circular total colorings of graphs
- The Waldschmidt constant for squarefree monomial ideals
- Local chromatic number and Sperner capacity
- The \((p, q)\)-extremal problem and the fractional chromatic number of Kneser hypergraphs
- Shannon capacity and the categorical product
- Fractional matchings, component-factors and edge-chromatic critical graphs
- Graphs whose Kronecker covers are bipartite Kneser graphs
- Efficient random graph matching via degree profiles
- The price of defense
- Spectral radius and fractional matchings in graphs
- Arboricity games: the core and the nucleolus
- Lower bounds of distance Laplacian spectral radii of \(n\)-vertex graphs in terms of fractional matching number
- Conditional fractional matching preclusion for burnt pancake graphs and pancake-like graphs (extended abstract)
- Fractionally edge colouring graphs with large maximum degree in linear time
- The fractional strong metric dimension of graphs
- On complexities of minus domination
- Toughness and degree condition for fractional ID-k-factor-critical graphs
- On the fractional f-chromatic index of a graph
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4382863)