A simple existence criterion for \((g

DOI10.1016/0012-365X(90)90387-WzbMath0723.05101OpenAlexW2082659364WikidataQ56688017 ScholiaQ56688017MaRDI QIDQ757439

Katherine Heinrich, Pavol Hell, David G. Kirkpatrick, Gui Zhen Liu

Publication date: 1990

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0012-365x(90)90387-w

zbMATH Keywords

algorithm(g,f)-factorcriterion of Lovász

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (25)

Factors of trees ⋮ Toughness of graphs and \([2,b\)-factors] ⋮ Some Results on Fractional Graph Theory ⋮ Graph factors and factorization: 1985--2003: a survey ⋮ \((a,b,k)\)-critical graphs ⋮ Solving Matching Problems Efficiently in Bipartite Graphs ⋮ Ryser's theorem for \(\rho\)-Latin rectangles ⋮ Graph realizations: maximum degree in vertex neighborhoods ⋮ How many matchings cover the nodes of a graph? ⋮ Efficiently Realizing Interval Sequences ⋮ Degree conditions for graphs to be fractional \((a, b, n)\)-critical graphs ⋮ Degree constrained subgraphs ⋮ Overlaying a hypergraph with a graph with bounded maximum degree ⋮ Orthogonal (g, f)-factorizations in networks ⋮ Perfect \(f\)-matchings and \(f\)-factors in hypergraphs -- a combinatorial approach ⋮ Subgraphs with orthogonal factorizations and algorithms ⋮ Fractional factors, component factors and isolated vertex conditions in graphs ⋮ Constructive proof of deficiency theorem of \((g,f)\)-factor ⋮ Nontrivial path covers of graphs: existence, minimization and maximization ⋮ Some problems on factorizations with constraints in bipartite graphs ⋮ Simplified existence theorems for \((g,f)\)-factors ⋮ \((g, f)\)-factorizations randomly orthogonal to a subgraph in graphs ⋮ 3-Regular subgraphs and (3,1)-colorings of 4-regular pseudographs ⋮ Randomly orthogonal \((g,f)\)-factorizations in graphs ⋮ Relaxed and approximate graph realizations

Cites Work

• Unnamed Item
• [a,b-factors of graphs]
• Matching theory
• Graph factors
• An extension of Tutte's 1-factor theorem
• Simplified existence theorems for \((g,f)\)-factors
• A remark on the factor theorems of lovász and tutte
• Algorithms for Degree Constrained Graph Factors of Minimum Deficiency
• The Subgraph Problem
• An algorithmic proof of Tutte's f-factor theorem
• Subgraphs with prescribed valencies
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• The Factorization of Linear Graphs

This page was built for publication: A simple existence criterion for \((g<f)\)-factors