تقرير
Linear arboricity of degenerate graphs
| العنوان: | Linear arboricity of degenerate graphs |
|---|---|
| المؤلفون: | Chen, Guantao, Hao, Yanli, Yu, Guoning |
| المصدر: | J. Graph Theory. 104 (2023) 360-371 |
| سنة النشر: | 2022 |
| المجموعة: | Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics, 05C35, 05C70 |
| الوصف: | A linear forest is a union of vertex-disjoint paths, and the linear arboricity of a graph $G$, denoted by $\operatorname{la}(G)$, is the minimum number of linear forests needed to partition the edge set of $G$. Clearly, $\operatorname{la}(G) \ge \lceil\Delta(G)/2\rceil$ for a graph $G$ with maximum degree $\Delta(G)$. On the other hand, the Linear Arboricity Conjecture due to Akiyama, Exoo, and Harary from 1981 asserts that $\operatorname{la}(G) \leq \lceil(\Delta(G)+1) / 2\rceil$ for every graph $ G $. This conjecture has been verified for planar graphs and graphs whose maximum degree is at most $ 6 $, or is equal to $ 8 $ or $ 10 $. Given a positive integer $k$, a graph $G$ is $k$-degenerate if it can be reduced to a trivial graph by successive removal of vertices with degree at most $k$. We prove that for any $k$-degenerate graph $G$, $\operatorname{la}(G) = \lceil\Delta(G)/2 \rceil$ provided $\Delta(G) \ge 2k^2 -k$. Comment: 15 pages, 1 figure |
| نوع الوثيقة: | Working Paper |
| DOI: | 10.1002/jgt.22967 |
| الوصول الحر: | http://arxiv.org/abs/2207.07169Test |
| رقم الانضمام: | edsarx.2207.07169 |
| قاعدة البيانات: | arXiv |
| DOI: | 10.1002/jgt.22967 |
|---|