pith. sign in

arxiv: 1512.05182 · v1 · pith:V6P4BHR5new · submitted 2015-12-16 · 🧮 math.CO

A Tutte-type characterization for graph factors

classification 🧮 math.CO
keywords characterizationfactorgraphkanoproblemtutte-typeaddressesakiyama
0
0 comments X
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.