On the path partition number of 6‐regular graphs. Issue 3 (12th April 2022)

• Record Type: Journal Article
• Authors: Feige, Uriel; Fuchs, Ella
• Is Part Of: Journal of graph theory. Volume 101:Issue 3(2022)
• Page Start: 345
• Page End: 378
• Publication Date: 2022-04-12
• Subjects: linear arboricity -- path partition -- path partition number -- regular graphs; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22830
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: A path partition (also referred to as a linear forest) of a graph G $G$ is a set of vertex‐disjoint paths which together contain all the vertices of G $G$ . An isolated vertex is considered to be a path in this case. The path partition conjecture states that every n $n$ ‐vertex d $d$ ‐regular graph has a path partition with at most n d + 1 $\frac{n}{d+1}$ paths. The conjecture has been proved for all d < 6 $d\lt 6$ . We prove the conjecture for d = 6 $d=6$ .