Strong Tutte type conditions and factors of graphs
Mikio Kanō, Zheng Yan · Discussiones Mathematicae Graph Theory · 2018
Let odd(G) denote the number of odd components of a graph G and k 2 be an integer. We give sufficient conditions using odd(G -S) for a graph G to have an even factor. Moreover, we show that if a graph G satisfies odd(G -S) max{1, (1/k)|S|} for all S V (G), then G has a (k -1)-regular factor for k 3 or an H-factor for k = 2, where we say that G has an H-factor if for every labeling h : V (G) {red, blue} with #{v V (G) : f (v) = red} even, G has a spanning subgraph F such that deg F (x) = 1 if h(x) = red and deg F (x) {0, 2} otherwise.