20.500.12556/RUL-134886 Coverability of graphs by parity regular subgraphs A graph is even (resp. odd) if all its vertex degrees are even (resp. odd). We consider edge coverings by prescribed number of even and/or odd subgraphs. In view of the 8-Flow Theorem, a graph admits a covering by three even subgraphs if and only if it is bridgeless. Coverability by three odd subgraphs has been characterized recently [Petruševski, M.; Škrekovski, R. Coverability of graph by three odd subgraphs. J. Graph Theory 2019, 92, 304–321]. It is not hard to argue that every acyclic graph can be decomposed into two odd subgraphs, which implies that every graph admits a decomposition into two odd subgraphs and one even subgraph. Here, we prove that every 3-edge-connected graph is coverable by two even subgraphs and one odd subgraph. The result is sharp in terms of edge-connectivity. We also discuss coverability by more than three parity regular subgraphs, and prove that it can be efficiently decided whether a given instance of such covering exists. Moreover, we deduce here a polynomial time algorithm which determines whether a given set of edges extends to an odd subgraph. Finally, we share some thoughts on coverability by two subgraphs and conclude with two conjectures. covering even subgraph odd subgraph T-join spanning tree pokritje sodi podgraf lihi podgraf T-spoj vpeto drevo true false true Angleški jezik Slovenski jezik Članek v reviji 2022-02-10 10:38:25 2022-02-10 10:38:26 2022-09-14 04:10:30 0000-00-00 00:00:00 2021 0 0 15 str. iss. 2, art. 182 Vol. 9 2021 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 2227-7390 10.3390/math9020182 47971331 RAZ_Petrusevski_Mirko_2021.pdf RAZ_Petrusevski_Mirko_2021.pdf 1 8ACCBDB8E0D81E505AF352DA89552B76 d7885263b790c8228bac9ead22174a85a9b3fbad424e56388fb51ecc47ea82fd 38da1642-8a55-11ec-abdb-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=153609 https://www.mdpi.com/2227-7390/9/2/182 0 0ea7c7ca-8a55-11ec-abdb-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=153608 Fakulteta za matematiko in fiziko 0 0 0