Towards the linear arboricity conjecture
Towards the linear arboricity conjecture
复制标题
走向线性树木性猜想
DOI：
10.1016/j.jctb.2019.08.009
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Jain, Vishesh
中科院分区：
文献类型：
--
作者：
Ferber, Asaf;Fox, Jacob;Jain, Vishesh
图 G 的线性树木性，用 la (G) 表示，是 G 中边不相交的线性森林（即其中每个连通分量都是一条路径的森林）的最小数量，其并集覆盖 G 的所有边。 Akiyama、Exoo 和 Harary 在 1981 年提出的一个著名猜想断言 la (G)≤⌈(Δ (G)+ 1)/2⌉，其中 Δ (G) 表示G 的最大度。这个推测的上限是最好的，通过将 G 视为正则图很容易看出。在本文中，我们表明，对于每个图 G，对于某些 α> 0，la (G)≤ Δ 2+ O (Δ 2/3− α) ，从而改进了 1992 年 Alon 和 Spencer 提出的先前最知名的界限。对于足够好的谱扩展器的图，我们给出了更好的界限。我们对这些结果的证明进一步给出了概率多项式时间算法，用于找到线性森林的此类分解。
The linear arboricity of a graph G, denoted by la (G), is the minimum number of edge-disjoint linear forests (ie forests in which every connected component is a path) in G whose union covers all the edges of G. A famous conjecture due to Akiyama, Exoo, and Harary from 1981 asserts that la (G)≤⌈(Δ (G)+ 1)/2⌉, where Δ (G) denotes the maximum degree of G. This conjectured upper bound would be best possible, as is easily seen by taking G to be a regular graph. In this paper, we show that for every graph G, la (G)≤ Δ 2+ O (Δ 2/3− α) for some α> 0, thereby improving the previously best known bound due to Alon and Spencer from 1992. For graphs which are sufficiently good spectral expanders, we give even better bounds. Our proofs of these results further give probabilistic polynomial time algorithms for finding such decompositions into linear forests.
登录
查看更多内容
1-伪随机图的因式分解
DOI：
--
发表时间：
2018
期刊：
IEEE Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Asaf Ferber;Vishesh Jain
通讯作者：
Vishesh Jain
稠密拟随机图的最优路径和循环分解
DOI：
--
发表时间：
2015
期刊：
Electron. Notes Discret. Math.
影响因子：
--
作者：
Stefan Glock;D. Kühn;D. Osthus
通讯作者：
D. Osthus
DOI：
--
发表时间：
1998
期刊：
Combinatorics, probability & computing
影响因子：
--
作者：
David A. Grable
通讯作者：
David A. Grable
DOI：
--
发表时间：
1968
期刊：
影响因子：
--
作者：
L. Mirsky
通讯作者：
L. Mirsky
具有给定行和列总和的矩阵的网络流方法
影响因子：
0.8
作者：
R. Anstee
通讯作者：
R. Anstee