Equimatchable graphs are C2k+1-free for k≥4
Discrete Mathematics, cilt.339, sa.12, ss.2964-2969, 2016 (SCI-Expanded, Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 339 Sayı: 12
- Basım Tarihi: 2016
- Doi Numarası: 10.1016/j.disc.2016.06.003
- Dergi Adı: Discrete Mathematics
- Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
- Sayfa Sayıları: ss.2964-2969
- Anahtar Kelimeler: Equimatchable graph, Factor-critical, Forbidden subgraph, Gallai–Edmonds decomposition
- Boğaziçi Üniversitesi Adresli: Evet
Özet
A graph is equimatchable if all of its maximal matchings have the same size. Equimatchable graphs are extensively studied in the literature mainly from structural point of view. Here we provide the first family of forbidden subgraphs of equimatchable graphs. Since equimatchable graphs are by definition not hereditary, this task of finding forbidden subgraphs requires the use of structural results from previous works.