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.