论文标题
甚至在无爪平面图中的周期和完美匹配
Even cycles and perfect matchings in claw-free plane graphs
论文作者
论文摘要
lov {Á} SZ表明，匹配的覆盖图$ g $具有$ g $的任意边缘开始的耳朵分解。让$ g $是具有完美匹配的图形。如果每个偶数$ c $ $ g $，$ g-v（c）$都具有完美的匹配，我们将称为$ g $ cycle-nice。如果$ g $是一个周期匹配的覆盖图，则$ g $的耳朵分解为$ g $的任意偶数。在本文中，我们表征了无爪爪平面图。我们表明，唯一的循环简单3连接的无爪平面图为$ k_4 $，$ w_5 $和$ \ 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$.
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$.
