Even cycles and perfect matchings in claw-free plane graphs
Discrete mathematics & theoretical computer science, Tome 22 (2020-2021) no. 4
Voir la notice de l'article provenant de la source Episciences
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$.
@article{DMTCS_2020_22_4_a7,
author = {Zhang, Shanshan and Wang, Xiumei and Yuan, Jinjiang},
title = {Even cycles and perfect matchings in claw-free plane graphs},
journal = {Discrete mathematics & theoretical computer science},
publisher = {mathdoc},
volume = {22},
number = {4},
year = {2020-2021},
doi = {10.23638/DMTCS-22-4-6},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-4-6/}
}
TY - JOUR AU - Zhang, Shanshan AU - Wang, Xiumei AU - Yuan, Jinjiang TI - Even cycles and perfect matchings in claw-free plane graphs JO - Discrete mathematics & theoretical computer science PY - 2020-2021 VL - 22 IS - 4 PB - mathdoc UR - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-4-6/ DO - 10.23638/DMTCS-22-4-6 LA - en ID - DMTCS_2020_22_4_a7 ER -
%0 Journal Article %A Zhang, Shanshan %A Wang, Xiumei %A Yuan, Jinjiang %T Even cycles and perfect matchings in claw-free plane graphs %J Discrete mathematics & theoretical computer science %D 2020-2021 %V 22 %N 4 %I mathdoc %U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-4-6/ %R 10.23638/DMTCS-22-4-6 %G en %F DMTCS_2020_22_4_a7
Zhang, Shanshan; Wang, Xiumei; Yuan, Jinjiang. Even cycles and perfect matchings in claw-free plane graphs. Discrete mathematics & theoretical computer science, Tome 22 (2020-2021) no. 4. doi: 10.23638/DMTCS-22-4-6
Cité par Sources :