TY - GEN
T1 - Forbidden subgraph and perfect path-matchings
AU - Yan, Jingzhi
AU - Hu, Bin
AU - Zhang, Heping
AU - Zhu, Tingzhao
AU - Li, Xiaowei
PY - 2009
Y1 - 2009
N2 - As a common generalization of matchings and matroid intersection, Cunningham and Geelen introduced the notion of path-matchings in 1996. Let K1,t 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 existence of perfect path-matching of K1,t -free graphs are presented. As an immediate consequence, we improve Sumner's result.
AB - As a common generalization of matchings and matroid intersection, Cunningham and Geelen introduced the notion of path-matchings in 1996. Let K1,t 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 existence of perfect path-matching of K1,t -free graphs are presented. As an immediate consequence, we improve Sumner's result.
UR - http://www.scopus.com/inward/record.url?scp=70450160700&partnerID=8YFLogxK
U2 - 10.1109/SWS.2009.5271774
DO - 10.1109/SWS.2009.5271774
M3 - Conference contribution
AN - SCOPUS:70450160700
SN - 9781424441563
T3 - Proceedings - 2009 1st IEEE Symposium on Web Society, SWS 2009
SP - 86
EP - 89
BT - Proceedings - 2009 1st IEEE Symposium on Web Society, SWS 2009
T2 - 2009 1st IEEE Symposium on Web Society, SWS 2009
Y2 - 23 August 2009 through 24 August 2009
ER -