A simple existence criterion for (g

DOI10.1016/0012-365X(90)90387-WMaRDI QIDQ757439zbMATH OpenOpenAlexWikidataFDO

Authors Katherine Heinrich, Pavol Hell, David Kirkpatrick, Guizhen 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)

Recommendations

• Simplified existence theorems for \((g,f)\)-factors
• Some remarks about factors of graphs
• An algorithmic proof of Tutte's f-factor theorem
• A Note on the Existence of All (g,f)-Factors
• Constructive proof of deficiency theorem of \((g,f)\)-factor

Cites work

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

Cited in

(31)

• Ryser's theorem for \(\rho\)-Latin rectangles
• scientific article; zbMATH DE number 3106448 (Why is no real title available?)
• Orthogonal (g, f)-factorizations in networks
• 3-Regular subgraphs and (3,1)-colorings of 4-regular pseudographs
• A Note on the Existence of All (g,f)-Factors
• Degree conditions for graphs to be fractional (a, b, n)-critical graphs
• An algorithmic proof of Tutte's f-factor theorem
• Relaxed and approximate graph realizations
• scientific article; zbMATH DE number 1762643 (Why is no real title available?)
• Perfect \(f\)-matchings and \(f\)-factors in hypergraphs -- a combinatorial approach
• Subgraphs with orthogonal factorizations and algorithms
• \((g, f)\)-factorizations randomly orthogonal to a subgraph in graphs
• Solving matching problems efficiently in bipartite graphs
• Fractional factors, component factors and isolated vertex conditions in graphs
• Graph realizations: maximum degree in vertex neighborhoods
• Nontrivial path covers of graphs: existence, minimization and maximization
• Some Results on Fractional Graph Theory
• Degree constrained subgraphs
• Constructive proof of deficiency theorem of \((g,f)\)-factor
• Randomly orthogonal (g,f)-factorizations in graphs
• Overlaying a hypergraph with a graph with bounded maximum degree
• Simplified existence theorems on all fractional \([a,b]\)-factors
• Factors of trees
• Toughness of graphs and \([2,b]\)-factors
• How many matchings cover the nodes of a graph?
• Simplified existence theorems for \((g,f)\)-factors
• Fractional factors and component factors in graphs with isolated toughness smaller than 1
• Graph factors and factorization: 1985--2003: a survey
• Some problems on factorizations with constraints in bipartite graphs
• Efficiently realizing interval sequences
• \((a,b,k)\)-critical graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q757439)