Delphi.science

Gallai's path decomposition conjecture for $K_5$-minor-free graphs

Source: arxiv.org/abs/2611.21673

Junhao Zhang, Qinghai Liu, Yanmei Hong

arXivarxiv/2611.21673Nov 14, 2026math.COscore 0

Gallai conjectured that the edges of every connected graph on $n$ vertices can be partitioned into at most $\ceil{n/2}$ paths. We prove that every connected $K_5$-minor-free graph other than $K_3$ and $K_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 $4$-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…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2611.21673
curl -X POST /api/v1/records/arxiv/2611.21673/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.21673/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'