Mirko Petruševski: Coverability of graphs by parity regular subgraphs

Povezava do seminarja:

 

Povzetek. Only two types of graphs are `parity regular', that is, have all their vertex degrees of the same parity. Namely, these are the `even graphs' and the `odd graphs', where a graph is said to be even (resp. odd) if all its vertex degrees are even (resp. odd). An old result of Matthews from 1978 establishes a connection between nowhere-zero 2^k - flows in graphs and coverability by k even subgraphs, which in view of Jaeger's 8-flow and 4-flow theorems, respectively, implies that every bridgeless graph admits a cover by three even subgraphs and that every 4-edge-connected graph is coverable by two even subgraphs.  Pyber observed in 1991 that every simple graph admits a decomposition into (at most) four odd subgraphs, and Matrai proved in 2006 that every simple graph is coverable by three odd subgraphs.

In this talk, we present some new results that complement or generalize the aforementioned. In particular, we characterize coverability by three odd subgraphs, decomposability into four odd subgraphs, and discuss coverability by every other possible combination of three or more parity regular subgraphs. We shall also share some thoughts on coverability by one even and one odd subgraphs and conclude with a conjecture.

This is  joint work with Riste Škrekovski.