Factors in graphs with odd-cycle property
type: Item
instance of: scholarly article
title: Factors in graphs with odd-cycle property
zbMATH Open document ID: 0787.05075
DOI: 10.1016/0012-365X(93)90221-E
published in: Discrete Mathematics
publication date: 1993-08-30T00:00:00Z
review text: 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\).
reviewed by: M.Koman
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 179586
zbMATH Keywords: regular graph
zbMATH Keywords: cycle
zbMATH Keywords: spanning subgraph
zbMATH Keywords: factor
author: Ciping Chen
author: Jianfang Wang
MaRDI profile type: Publication
cites work: Odd and even factors with given properties
cites work: Sufficient conditions for graphs to have \((g,f)\)-factors
cites work: Flows in infinite graphs
cites work: Some Properties of Graphs with Multiple Edges
cites work: [a,b]-factors of graphs
cites work: Subgraphs with prescribed valencies
cites work: Q3880849
cites work: The factorization of graphs. II
cites work: On Factors of a Graph
cites work: The Factors of Graphs
description: scientific article; zbMATH DE number 179586