摘要 Abstract
对于完美匹配相关问题的研究,通常可以限制在匹配覆盖图上——即连通非平凡且每条边都包含在一个完美匹配中的图。这类图也被称为1-可扩图(因为每条边都可以扩展为一个完美匹配),其文献非常丰富,包括Lovász和Plummer提出的耳分解定理。若图 \( G \) 的一个圈 \( C \) 满足 \( G-V(C) \) 存在一个完美匹配,则称该圈为一致圈;这类圈在完美匹配的研究中尤为重要,特别是在研究Pfaffian定向问题时。若匹配覆盖图 \( G \) 中每个偶圈 \( C \) 都是一致圈,或者等价地,\( C \) 的每个完美匹配都能扩展到 \( G \) 的完美匹配中,则称 \( G \) 为圈可扩图。这类图也被称为圈良好的图或1-圈共振图。Zhang、Wang、Yuan、Ng和Cheng [Discrete Mathematics, 345:7 (2022), 112876] 给出了爪自由圈可扩图的刻画。Guo和Zhang [Discrete Mathematics, 275:1-3 (2004), 151-164] 以及Zhang和Li [Discrete Applied Mathematics, 160:13-14 (2012), 2069-2074] 分别独立给出了二部平面圈可扩图的刻画。本文建立了所有平面圈可扩图的刻画——通过 \( K_2 \) 和四个无穷族来描述。
For most problems pertaining to perfect matchings, one may restrict attention to matching covered graphs -- that is, connected nontrivial graphs with the property that each edge belongs to some perfect matching. There is extensive literature on these graphs that are also known as $1$-extendable graphs (since each edge extends to a perfect matching) including an ear decomposition theorem due to Lovasz and Plummer. A cycle $C$ of a graph $G$ is conformal if $G-V(C)$ has a perfect matching; such cycles play an important role in the study of perfect matchings, especially when investigating the Pfaffian orientation problem. A matching covered graph $G$ is cycle-extendable if -- for each even cycle $C$ -- the cycle $C$ is conformal, or equivalently, each perfect matching of $C$ extends to a perfect matching of $G$, or equivalently, $C$ is the symmetric difference of two perfect matchings of $G$, or equivalently, $C$ extends to an ear decomposition of $G$. In the literature, these are also known as cycle-nice or as $1$-cycle resonant graphs. Zhang, Wang, Yuan, Ng and Cheng [Discrete Mathematics, 345:7 (2022), 112876] provided a characterization of claw-free cycle-extendable graphs. Guo and Zhang [Discrete Mathematics, 275:1-3 (2004), 151-164] and independently Zhang and Li [Discrete Applied Mathematics, 160:13-14 (2012), 2069-2074], provided characterizations of bipartite planar cycle-extendable graphs. In this paper, we establish a characterization of all planar cycle-extendable graphs -- in terms of $K_2$ and four infinite families.