On Graph Odd Edge-Colorings and Odd Edge-Coverings

Abstract

An odd $k$-edge-coloring of a graph $G$ is a (not necessarily proper) edge-coloring with at most $k$ colors such that each non-empty color class induces a graph in which every vertex is of odd degree; similarly, if more than one color per edge is allowed, we speak of an odd $k$-edge-covering of $G$. In this paper, we fully resolve two major conjectures on odd edge-colorings and odd edge-coverings of graphs, proposed by Petru{Å¡}evski and {Å }krekovski ({\it European Journal of Combinatorics,} 91:103225, 2021). The first conjecture states that, apart from two particular exceptions which are respectively odd $5$- and odd-$6$-edge-colorable, for any other loopless and connected graph $G$ there exists an edge $e$ such that $G\backslash \{e\}$ is odd $3$-edge-colorable. The second conjecture states that any simple graph $G$ admits an odd $3$-edge-covering in which at most one edge receives more than one color. In addition, we strongly confirm the second conjecture by demonstrating that there exists an odd $3$-edge-covering in which at most one edge receives two colors and the rest of the edges receive unique colors.

17 pages. We fixed some gaps in the proofs and added five figures