论文标题
从完美匹配中获得3分组
Towards obtaining a 3-Decomposition from a perfect Matching
论文作者
论文摘要
图的分解是一组子图，其边缘分区$ g $。霍夫曼·斯滕霍夫（Hoffmann-Ostenhof）在2011年提出的3分解猜想指出，每个连接的立方图都可以分解为生成树，一个2个规则的子图和匹配。它已定为特殊类图的特殊类别，这是哈密顿图的第一个结果之一。在过去的两年中，已经获得了几个新结果，并将平面，无爪和3个连接的树宽3图添加到列表中。 在本文中，我们考虑了哈密顿图的自然扩展：从立方图中删除哈密顿循环的循环留下了完美的匹配。相反，从立方图$ g $中删除完美的匹配$ m $，这会使周期不一致。收缩这些周期会产生新的图$ g_m $。如果$ g_m $是某种完美匹配的$ m $，则图表$ g $是星形的，使汉密尔顿图类似于明星。我们扩展了用于证明汉密尔顿图的技术满足3分解的猜想，以表明三连接的恒星样图也可以满足它。
A decomposition of a graph is a set of subgraphs whose edges partition those of $G$. The 3-decomposition conjecture posed by Hoffmann-Ostenhof in 2011 states that every connected cubic graph can be decomposed into a spanning tree, a 2-regular subgraph, and a matching. It has been settled for special classes of graphs, one of the first results being for Hamiltonian graphs. In the past two years several new results have been obtained, adding the classes of plane, claw-free, and 3-connected tree-width 3 graphs to the list. In this paper, we regard a natural extension of Hamiltonian graphs: removing a Hamiltonian cycle from a cubic graph leaves a perfect matching. Conversely, removing a perfect matching $M$ from a cubic graph $G$ leaves a disjoint union of cycles. Contracting these cycles yields a new graph $G_M$. The graph $G$ is star-like if $G_M$ is a star for some perfect matching $M$, making Hamiltonian graphs star-like. We extend the technique used to prove that Hamiltonian graphs satisfy the 3-decomposition conjecture to show that 3-connected star-like graphs satisfy it as well.
