As a common generalization of matchings and matroid intersection, Cunningham and Geelen introduced the notion of path-matchings in 1996. Let K1,t denote the star with t + 1 vertices. A graph is K1. t-free if G contains no K1, t, as its induced subgraph. Sumner showed that (t — 1)-connected K1, t-free graphs with even number of vertices have a perfect matching. In this paper, some sufficient conditions for the existence of perfect path-matching of K1, t-free graphs are presented. As an immediate consequence, we improve Sumner's result.
展开▼
