Forbidden subgraph and perfect path-matchings

Jingzhi Yan*, Bin Hu, Heping Zhang, Tingzhao Zhu, Xiaowei Li

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

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.

Original languageEnglish
Title of host publicationProceedings - 2009 1st IEEE Symposium on Web Society, SWS 2009
Pages86-89
Number of pages4
DOIs
Publication statusPublished - 2009
Externally publishedYes
Event2009 1st IEEE Symposium on Web Society, SWS 2009 - Lanzhou, China
Duration: 23 Aug 200924 Aug 2009

Publication series

NameProceedings - 2009 1st IEEE Symposium on Web Society, SWS 2009

Conference

Conference2009 1st IEEE Symposium on Web Society, SWS 2009
Country/TerritoryChina
CityLanzhou
Period23/08/0924/08/09

Fingerprint

Dive into the research topics of 'Forbidden subgraph and perfect path-matchings'. Together they form a unique fingerprint.

Cite this

Yan, J., Hu, B., Zhang, H., Zhu, T., & Li, X. (2009). Forbidden subgraph and perfect path-matchings. In Proceedings - 2009 1st IEEE Symposium on Web Society, SWS 2009 (pp. 86-89). Article 5271774 (Proceedings - 2009 1st IEEE Symposium on Web Society, SWS 2009). https://doi.org/10.1109/SWS.2009.5271774