An odd graph is a graph whose vertex degrees are all odd. As introduced by Pyber in 1991, an odd edge-covering of graph $G$ is a family of odd subgraphs that cover its edges. The minimum size of such family is denoted by ${\rm cov}_0(G)$. Answering a question raised by Pyber, Mátrai proved in 2006 that ${\rm cov}_0(G) \le 3$ for every simple graph $G$. In this study, we characterize the same inequality for the class of loopless graphs by proving that, apart from four particular types of loopless graphs on three vertices, every other connected loopless graph admits an odd 3-edge-covering. Moreover, there exists such an edgecovering with at most two edges belonging to more than one subgraph and no edge to all three subgraphs. The latter part of this result implies an interesting consequence for the related notion of odd 3-edge-colorability. Our characterization presents a parity counterpart to the characterization of Matthews from 1978 concerning coverability of graph by three even subgraphs.
COBISS.SI-ID: 2048608787
The Petersen colouring conjecture states that every bridgeless cubic graph admits an edge-colouring with 5 colours such that for every edge $e$, the set of colours assigned to the edges adjacent to $e$ has cardinality either 2 or 4, but not 3. We prove that every bridgeless cubic graph $G$ admits an edge-colouring with 4 colours such that at most $8/15|E(G)|$ edges do not satisfy the above condition. This bound is tight and the Petersen graph is the only connected graph for which the bound cannot be decreased. We obtain such a 4-edge-colouring by using a carefully chosen subset of edges of a perfect matching, and the analysis relies on a simple discharging procedure with essentially no reductions and very few rules.
COBISS.SI-ID: 2048633619
Given a finite graph $G$ and a parity 2-dimensional vector-function $\pi=(\pi_1,\pi_2): V (G)\to \{0,1\}\times \{0,1\}$, a parity decomposition of $(G,\pi)$ is an ordered 2-partition $(E_1,E_2)$ of $E(G)$ such that the degree functions $d_{G[E_i]}$ $(i = 1,2)$ of the subgraphs induced by the partite sets are in parity accordance with the respective components of $pi$, i.e. $d_{G[E_i]}(v) \eqiiv_2 \pi_i(v)$ for each vertex v of $G[E_i]$. We show that the decision problem whether $(G,\pi)$ admits a parity decomposition is solvable in polynomial time. Contrarily, we conjecture that the analogous decision problem involving a parity 3-dimensional vector-function and concerning the existence of an adequate ordered 3-partition is not solvable in polynomial time.
COBISS.SI-ID: 2048602131