期刊
ADVANCES IN MATHEMATICS
卷 437, 期 -, 页码 -出版社
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.aim.2023.109434
关键词
Sublinear expansion; Expander decomposition; Graph decomposition; Erdos-Gallai conjecture
类别
This article improves upon previous research by showing that any n-vertex graph can be decomposed into O(n log* n) cycles and edges.
In the 1960's, Erdos and Gallai conjectured that the edges of any n-vertex graph can be decomposed into O(n) cycles and edges. We improve upon the previous best bound of O(n log log n) cycles and edges due to Conlon, Fox and Sudakov, by showing an n-vertex graph can always be decomposed into O(n log* n) cycles and edges, where log* n is the iterated logarithm function.(c) 2023 Elsevier Inc. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据