A Tutte-type characterization for graph factors

Abstract

Let $G$ be a connected general graph. Let $f:V(G)\to {\mathbb{Z}}^{+}$ be a function. We show that $G$ satisfies the Tutte-type condition \[ o(G-S)\le f(S)\qquad\text{for all vertex subsets $S$}, \] if and only if it contains a colored $J_f^{\ast }$-factor for any $2$-end-coloring, where $J_f^{\ast }(v)$ is the union of all odd integers smaller than $f(v)$ and the integer $f(v)$ itself. This is a generalization of the $(1,f)$-odd factor characterization theorem, and answers a problem of Cui and Kano. We also derive an analogous characterization for graphs of odd orders, which addresses a problem of Akiyama and Kano.

12 pages