2015年12月
Perfect matchings avoiding prescribed edges in a star-free graph
DISCRETE MATHEMATICS
- ,
- ,
- ,
- ,
- 巻
- 338
- 号
- 12
- 開始ページ
- 2260
- 終了ページ
- 2274
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1016/j.disc.2015.05.014
- 出版者・発行元
- ELSEVIER SCIENCE BV
Aldred and Plummer (1999) have proved that every m-connected K-1,K-m-k+2-free graph of even order contains a perfect matching which avoids k prescribed edges. They have also proved that the result is best possible in the range 1 <= k <= 1/2(m + 1). In this paper, we show that if 1/2(m + 2) <= k <= m - 1, their result is not best possible. We prove that if m >= 4 and 1/2(m + 2) <= k <= m - 1, every K-1,K-[2m-k+4/3]-free graph of even order contains a perfect matching which avoids k prescribed edges. While this is a best possible result in terms of the order of a forbidden star, if 2m - k + 4 equivalent to 0 (mod 3), we also prove that only finitely many sharpness examples exist. (C) 2015 Elsevier B.V. All rights reserved.
- リンク情報
- ID情報
-
- DOI : 10.1016/j.disc.2015.05.014
- ISSN : 0012-365X
- eISSN : 1872-681X
- Web of Science ID : WOS:000359955700012