Premium
Coverability of graph by three odd subgraphs
Author(s) -
Petruševski Mirko,
Škrekovski Riste
Publication year - 2019
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22455
Subject(s) - combinatorics , mathematics , distance hereditary graph , discrete mathematics , graph , vertex (graph theory) , line graph , voltage graph
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 cov o ( G ) . Answering a question raised by Pyber, Mátrai proved in 2006 that cov o ( G ) ≤ 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 edge‐covering 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.