Abstract
We introduce and study "path odd-covers", a weakening of Gallai's path decomposition problem and a strengthening of the linear arboricity problem. The "path odd-cover number" p_2(G) of a graph G is the minimum cardinality of a collection of paths whose vertex sets are contained in V(G) and whose symmetric difference of edge sets is E(G). We prove an upper bound on p_2(G) in terms of the maximum degree Δ and the number of odd-degree vertices v_{odd} of the form maxleft{v_{odd}/{2}, 2leftlceil Δ/{2}right rceilright}. This bound is only a factor of 2 from a rather immediate lower bound of the form max left{ {v_{odd} }/{2} , leftlceil Δ/{2}rightrceil right}. We also investigate some natural relaxations of the problem which highlight the connection between the path odd-cover number and other well-known graph parameters. For example, when allowing for subdivisions of G, the previously mentioned lower bound is always tight except in some trivial cases. Further, a relaxation that allows for the addition of isolated vertices to G leads to a match with the linear arboricity when G is Eulerian. Finally, we transfer our observations to establish analogous results for cycle odd-covers.
Get this paper in your agent:
hf papers read 2306.06487 Don't have the latest CLI?
curl -LsSf https://hf.co/cli/install.sh | bash Models citing this paper 0
No model linking this paper
Datasets citing this paper 0
No dataset linking this paper
Spaces citing this paper 0
No Space linking this paper
Collections including this paper 0
No Collection including this paper