The existence of a path-factor without small odd paths
type: Item
instance of: scholarly article
title: The existence of a path-factor without small odd paths
zbMATH Open document ID: 1391.05204
author: Yoshimi Egawa
author: Michitaka Furuya
published in: The Electronic Journal of Combinatorics
publication date: 2018-05-25T00:00:00Z
full work available at URL: v25i1p40
review text: Summary: A \(\{P_{2},P_{5}\}\)-factor of a graph is a spanning subgraph of the graph each of whose components is isomorphic to either \(P_{2}\) or \(P_{5}\), where \(P_{n}\) denote the path of order \(n\).~In this paper, we show that if a graph \(G\) satisfies \(c_{1}(G-X)+\frac{2}{3}c_{3}(G-X)\leq \frac{4}{3}|X|+\frac{1}{3}\) for all \(X\subseteq V(G)\), then \(G\) has a \(\{P_{2},P_{5}\}\)-factor, where \(c_{i}(G-X)\) is the number of components \(C\) of \(G-X\) with \(|V(C)|=i\). Moreover, it is shown that above condition is sharp.
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 6873084
zbMATH Keywords: path-factor
zbMATH Keywords: component-factor
zbMATH Keywords: matching
MaRDI profile type: Publication
cites work: Q3910557
cites work: Q3577833
cites work: Path-factors involving paths of order seven and nine
cites work: Sufficient conditions for the existence of a path‐factor which are related to odd components
cites work: A necessary and sufficient condition for the existence of a path factor every component of which is a path of length at least two
cites work: Path and cycle factors of cubic bipartite graphs
cites work: Path factors in cubic graphs
cites work: Efficient subgraphs packing
description: scientific article; zbMATH DE number 6873084