5-正则图的路分解

Path decompositions of 5-regular graphs

对于正则图的路分解问题,Favaron等(2010)提出猜想:对于奇数l,任意包含一个完美匹配的l-正则图可以分解成长度为l的路.当l=5时,Favaron等(2010)证明了不含4-圈时猜想成立.后来Botler等(2015)证明了不含3-圈时猜想成立.本文证明当l=5且图中任意3-圈与4-圈的交为空集时,猜想成立.

Let l be an odd integer.It was conjectured that every l-regular graph containing a perfect matching can be decomposed into paths of length l.For the case l=5,Favaron et al.(2010)veri ed the conjecture for graphs with no cycle of length 4,and Botler et al.(2015)veri ed it for triangle-free graphs.In this paper,we prove that every 5-regular graph with a perfect matching can be decomposed into paths of length 5,provided that 3-cycles and 4-cycles in the graph have no edge in common.