Zhang, Shanshan and Wang, Xiumei and Yuan, Jinjiang - Even cycles and perfect matchings in claw-free plane graphs

dmtcs:6062 - Discrete Mathematics & Theoretical Computer Science, October 12, 2020, vol. 22 no. 4 - https://doi.org/10.23638/DMTCS-22-4-6
Even cycles and perfect matchings in claw-free plane graphs

Authors: Zhang, Shanshan and Wang, Xiumei and Yuan, Jinjiang

Lov{Ă¡}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$.


Volume: vol. 22 no. 4
Section: Graph Theory
Published on: October 12, 2020
Submitted on: January 31, 2020
Keywords: Mathematics - Combinatorics,05C70


Share

Consultation statistics

This page has been seen 166 times.
This article's PDF has been downloaded 63 times.