On the path partition number of 6‐regular graphs
Open Access
- 12 April 2022
- journal article
- research article
- Published by Wiley in Journal of Graph Theory
- Vol. 101 (3) , 345-378
Abstract
Apath partition(also referred to as a linear forest) of a graph is a set of vertex‐disjoint paths which together contain all the vertices of . An isolated vertex is considered to be a path in this case. The path partition conjecture states that every ‐vertex ‐regular graph has a path partition with at most paths. The conjecture has been proved for all . We prove the conjecture for .Keywords
All Related Versions
Funding Information
- Israel Science Foundation (1388/16)
This publication has 18 references indexed in Scilit:
- Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphsApplied Mathematics Letters, 2011
- Matching and edge-connectivity in regular graphsEuropean Journal of Combinatorics, 2011
- Balloons, cut‐edges, matchings, and total domination in regular graphs of odd degreeJournal of Graph Theory, 2009
- Optimal path cover problem on block graphsTheoretical Computer Science, 1999
- Almost all regular graphs are hamiltonianRandom Structures & Algorithms, 1994
- Optimal path cover problem on block graphs and bipartite permutation graphsTheoretical Computer Science, 1993
- The linear arboricity of some regular graphsJournal of Graph Theory, 1984
- Covering and packing in graphs IV: Linear arboricityNetworks, 1981
- Covering the vertices of a graph by vertex-disjoint pathsPacific Journal of Mathematics, 1975
- COVERING AND PACKING IN GRAPHS, I.Annals of the New York Academy of Sciences, 1970