Authors:
M. Kano, Z. Yan
Title:
Strong Tutte type conditions and factors of graphs
Source:
Discussiones Mathematicae Graph Theory
Received 26.10.2017, Revised 26.06.2018, Accepted 26.06.2018, doi: 10.7151/dmgt.2158

Abstract:
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) \le \max{1, (1/k) |S|} for all S⊂ V(G), then G has a (k-1)-regular factor for k≥ 3 or an \mathbf{H}-factor for k=2, where we say that G has an \mathbf{H}-factor if for every labeling h:V(G)→ {\mbox{red, blue}} with #{v∈V(G):f(v)=\mbox{red}} even, G has a spanning subgraph F such that \degF(x)=1 if h(x)=\mbox{red} and \degF(x)∈{0,2} otherwise.
Keywords:
factor of graph, even factor, regular factor, Tutte type condition

Links:
PDF