Pith. sign in

REVIEW 1 cited by

Approximate path decompositions of regular graphs

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2406.02514 v1 pith:OFKOZLFO submitted 2024-06-04 math.CO

Richard Montgomery , Alp Müyesser , Alexey Pokrovskiy , Benny Sudakov This is my paper · ORCID
classification math.CO
keywords regularalmostapproximategraphpathsalongasymptoticallyconfirming
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

We show that the edges of any $d$-regular graph can be almost decomposed into paths of length roughly $d$, giving an approximate solution to a problem of Kotzig from 1957. Along the way, we show that almost all of the vertices of a $d$-regular graph can be partitioned into $n/(d+1)$ paths, asymptotically confirming a conjecture of Magnant and Martin from 2009.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Hamilton cycles in pseudorandom graphs: resilience and approximate decompositions

    math.CO 2025-07 conditional novelty 8.0 of 10

    For pseudorandom graphs with large spectral gap, every subgraph with minimum degree above d/2 is Hamiltonian, and the whole edge set can be packed into, and covered by, about d/2 Hamilton cycles.

Pith tools