2023/08/02 by Rose McCarty, McCarty, Rose
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2308.01456
openalex publication_date 2023/08/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
We prove a precise min-max theorem for the following problem. Let G be an Eulerian graph with a specified set of edges S ⊆ E(G), and let b be a vertex of G. Then what is the maximum integer k so that the edge-set of G can be partitioned into k non-zero b-trails? That is, each trail must begin and end at b and contain an odd number of edges from~S. This theorem is motivated by a connection to vertex-minors and yields two conjectures of Máčajová and Škoviera as corollaries.