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

Date of publication: 22. 11. 2020
Discrete mathematics seminar
Torek, 24. 11. 2020, ob 10:15, na daljavo

Povezava do seminarja:

Topic: Seminar iz diskretne matematike - Mirko Petruševski
Time: Nov 24, 2020 10:15 AM Budapest

Join Zoom Meeting

Meeting ID: 961 8852 7185
Passcode: 893782


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.