Mirko Petruševski: Coverability of graphs by parity regular subgraphs
Vir: Seminar za diskretno matematiko
Povezava do seminarja:
two types of graphs are `parity regular', that is, have all their
vertex degrees of the same parity. Namely, these are the `even graphs'
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.