betaFeedback

WorksMathematics

Gallai's path decomposition conjecture for K5K_5-minor-free graphs

Abstract

Gallai conjectured that the edges of every connected graph on nn vertices can be partitioned into at most \ceil{n/2} paths. We prove that every connected K5K_5-minor-free graph other than K3K_3 and K5−eK_5-e admits such a partition into at most \floor{n/2} paths. The two exceptions require \ceil{n/2} paths. In a smallest counterexample we find a 44-connected planar part containing four vertices of degree five. Their neighborhoods meet the boundary in at most one vertex. This allows us to apply the planar configurations of Blanché, Bonamy, and Bonichon and to realize the reduced graph as a minor of the original graph.

Paper details

vlnc:W_9nc5dnqn
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…