On the path partition number of 6-regular graphs

2019/11/19 by Feige, Uriel, Fuchs, Ella · 2 citations
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1911.08397

Abstract

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

Cited by

• New bounds for linear arboricity and related problems
• Cycle-factors of regular graphs via entropy

Related

• Approximate path decompositions of regular graphs
• Internal Partitions of Regular Graphs
• The Path Partition Conjecture is True and its Validity Yields Upper Bounds for Detour Chromatic Number and Star Chromatic Number
• On the path partition of graphs
• Decomposing 8-regular graphs into paths of length 4