Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Even cycles and perf ...
Article

Even cycles and perfect matchings in claw-free plane graphs

Shanshan Zhang, Xiumei Wang, Jinjiang Yuan
Download article
Open on arXiv
Submitted on
January 31, 2020
Accepted on
August 30, 2020
Published on
October 12, 2020
Last modified on
March 31, 2025
Volume 22
vol. 22:4
Graph Theory
DOI
10.23638/DMTCS-22-4-6
License
arXiv.org - Non-exclusive license to distribute
Indicators
1306
Views
872
Downloads

Even cycles and perfect matchings in claw-free plane graphs

Shanshan Zhang, Xiumei Wang, Jinjiang Yuan
Abstract
Lov{\'a}sz showed that a matching covered graph $G$ has an ear decomposition starting with an arbitrary edge of $G$. Let $G$ be a graph which has a perfect matching. We call $G$ cycle-nice if for each even cycle $C$ of $G$, $G-V(C)$ has a perfect matching. If $G$ is a cycle-nice matching covered graph, then $G$ has ear decompositions starting with an arbitrary even cycle of $G$. In this paper, we characterize cycle-nice claw-free plane graphs. We show that the only cycle-nice simple 3-connected claw-free plane graphs are $K_4$, $W_5$ and $\overline C_6$. Furthermore, every cycle-nice 2-connected claw-free plane graph can be obtained from a graph in the family ${\cal F}$ by a sequence of three types of operations, where ${\cal F}$ consists of even cycles, a diamond, $K_4$, and $\overline C_6$. Comment: 12 pages
Keywords
  • Mathematics - Combinatorics
  • 05C70
Mathematics Subject Classification 2020
  • 05C10 - Planar graphs; geometric and topological aspects of graph theory
  • 05C38 - Paths and cycles
Preview
Loading PDF preview...