Factors in graphs with odd-cycle property (Q1210551): Difference between revisions

Let \(G\) be a graph and \(g\), \(f\) two labellings of its vertices with nonnegative integers. A spanning subgraph \(F\) of \(G\) is called a \((g,f)\)- factor if the inequalities \[ g(x)\;\leq\;d(x)\;\leq \;f(x)\tag{1} \] hold for all degrees \(d(x)\) of \(F\). (Compare with the review Zbl 0787.05077.) Furthermore, if \(g(x)\equiv d(x)\equiv f(x) \pmod 2\) for all degrees \(d(x)\) of \(F\) then this spanning subgraph \(F\) is called a \((g,f)\)-parity factor. The authors present some conditions for the existence of a \((g,f)\)-factor or a \((g,f)\)-parity factor in a graph \(G\) with odd-cycle property (i.e. the distances between any two odd cycles are \(\leq 1\) in \(G\)). (In some cases, the results are close to the known theorems, e.g. of Lovász (1970), Tutte (1952), Fulkerson (1970), etc.) We give two examples of the presented results: Theorem 3. Let \(G\) be a connected graph with the odd-cycle property and \(g\), \(f\) two labellings of \(G\) satisfying (1), the inequalities \(g(x)< d(x)\) and \(0< f(x)\) for all \(x\) of \(G\), and some of the two following formulas \(\sum_ x f(x)\equiv 0\pmod 2\) and \(g(y)< f(y)\) (for some \(y\)). Then \(G\) has a \((g,f)\)-factor if \(g(x)/d(x)\leq f(y)/d(y)\) for any two adjacent vertices \(x\), \(y\) of \(G\). The conditions for the existence of a \((g,f)\)-parity factor in a graph \(G\) is presented analogously. Theorem 4. Every \(r\)-regular graph \(G\) with the odd-cycle property has a \(k\)-factor, where \(0\leq k\leq r\) and \(k| V(G)|\equiv 0\pmod 2\).