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 \deg_{F}(x)=1 if h(x)=\mbox{red} and \deg_{F}(x)∈{0,2} otherwise. | |
Keywords: factor of graph, even factor, regular factor, Tutte type condition | |
Links: |