Name
Abstract | ||
|---|---|---|
Let G be a graph with n vertices. A path decomposition of G is a set of edge-disjoint paths containing all the edges of G. Let p(G) denote the minimum number of paths needed in a path decomposition of G. Gallai Conjecture asserts that if G is connected, then p(G) <= inverted right perpendicularn/2inverted left perpendicular. If G is allowed to be disconnected, then the upper bound left perpendicular3/4nright perpendicular for p(G) was obtained by Donald [7], which was improved to left perpendicular2/3nright perpendicular independently by Dean and Kouider [6] and Yan [14]. For graphs consisting of vertex-disjoint triangles, left perpendicular2/3nright perpendicular is reached and so this bound is tight. If triangles are forbidden in G, then p(G) <= left perpendicularg+1/2g nright perpendicular can be derived from the result of Harding and McGuinness [11], where g denotes the girth of G. In this paper, we also focus on triangle-free graphs and prove that p(G) <= left perpendicular3n/5right perpendicular, which improves the above result with g = 4. (C) 2022 Elsevier B.V. All rights reserved. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1016/j.disc.2022.112866 | DISCRETE MATHEMATICS |
Keywords | DocType | Volume |
Path, Decomposition, <p>Gallai & rsquo,s conjecture</p>, Triangle-free | Journal | 345 |
Issue | ISSN | Citations |
7 | 0012-365X | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yanan Chu | 1 | 0 | 0.34 |
| Genghua Fan | 2 | 412 | 65.22 |
| Chuixiang Zhou | 3 | 0 | 0.34 |