A Tutte-type characterization for graph factors

الأصل · EN

Let G be a connected general graph. Let f V(G)→ + be a function. We show that G satisfies the Tutte-type condition o(G-S)≤ f(S) all vertex subsets S, if and only if it contains a colored Jf*-factor for any 2-end-coloring, where Jf*(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.