A simple existence criterion for (g < f)
โ
Katherine Heinrich; Pavol Hell; David G. Kirkpatrick; Guizhen Liu
๐
Article
๐
1990
๐
Elsevier Science
๐
English
โ 312 KB
We simplify the criterion of Lovasz for the existence of a (g, f)-factor when g <f, or when the graph is bipartite. Moreover, we give a simple direct proof, implying an O(m. IQ) algorithm, for these cases. We then illustrate the convenience of the new criterion by deriving some old and some new fact