A Tutte-type characterization for graph factors
classification
🧮 math.CO
keywords
characterizationfactorgraphkanoproblemtutte-typeaddressesakiyama
read the original abstract
Let $G$ be a connected general graph. Let $f\colon V(G)\to \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^*$-factor for any $2$-end-coloring, where $J_f^*(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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.