A simple existence criterion for (g

The criterion of Lovász for the existence of a (g,f)-factor when $g<f$, or when the graph is bipartite is simplified and a simple direct proof, implying an O($\sqrt{(g(V))}\cdot | E|)$ algorithm, for these cases is given.

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

[a,b]-factors of graphs
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
scientific article; zbMATH DE number 3587078 (Why is no real title available?)
Matching theory
Simplified existence theorems for $(g,f)$-factors
Subgraphs with prescribed valencies
The Factorization of Linear Graphs
The Subgraph Problem

Cited in

(36)

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

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)