论文标题
加莱的2级图的路径分解
Gallai's Path Decomposition for 2-degenerate Graphs
论文作者
论文摘要
加莱的路径分解猜想指出，如果$ g $是$ n $顶点上的连接图，则$ g $的边缘最多可以分解为$ \ lceil \ lceil \ frac {n} {2} {2} \ rceil $ paths。如果可以通过删除$ k-1 $的边缘从$ 2K+1 $的顶点获得$ 2K+1 $顶点的集团，则据说这是一个奇怪的半固定。 Bonamy和Perrett询问$ n $顶点上每个连接的图形$ G $的边缘是否可以最多被分解成$ \ lfloor \ frac {n} {2} {2} \ rfloor $ paths $ g $是一个奇数的半平台。如果$ g $的每个子图最多有$ 2 $，则据说图$ g $是2级。在本文中，我们证明，$ n $ vertices上任何连接的2级$ g $的边缘最多可以分解为$ \ lfloor \ frac {n} {n} {2} {2} \ rfloor $ paths，除非$ g $是三角形。
Gallai's path decomposition conjecture states that if $G$ is a connected graph on $n$ vertices, then the edges of $G$ can be decomposed into at most $\lceil \frac{n }{2} \rceil$ paths. A graph is said to be an odd semi-clique if it can be obtained from a clique on $2k+1$ vertices by deleting at most $k-1$ edges. Bonamy and Perrett asked if the edges of every connected graph $G$ on $n$ vertices can be decomposed into at most $\lfloor \frac{n}{2} \rfloor$ paths unless $G$ is an odd semi-clique. A graph $G$ is said to be 2-degenerate if every subgraph of $G$ has a vertex of degree at most $2$. In this paper, we prove that the edges of any connected 2-degenerate graph $G$ on $n$ vertices can be decomposed into at most $\lfloor \frac{n }{2} \rfloor$ paths unless $G$ is a triangle.
