Optimal Path Partitions in Subcubic and Almost-subcubic Graphs

Tomáš Masařík, Michał Włodarczyk, Mehmet Akif Yıldız

We consider the problem of partitioning the edges of a graph into as few paths as possible. This is a~subject of the classic conjecture of Gallai and a recurring topic in combinato…