On circuit decomposition of planar Eulerian graphs (Q1814589)

A special case of Seymour's Sum of Circuits theorem asserts that the edges of a planar Eulerian graph can be partitioned into circuits (of length at least three) if and only if no cut has more than half of its edges in a parallel `bundle' joining the same two vertices. Suppose we are given at each vertex of a graph disjoint pairs of incident edges; these are called forbidden transitions. A good circuit does not include a forbidden transition. A result of Fleischner asserts that the edges of a planar Eulerian graph can be partitioned into good circuits if and only if no cut is a forbidden transition. This paper presents a common generalization of the above two results. Suppose we are given at each vertex a partition of the incident edges; each part is called a forbidden part, and each non-singleton subset of a forbidden part is called a forbidden set. A good circuit does not include a forbidden set. A bad cut has more than half of its edges in one forbidden part. The general theorem simply states that the edges of a planar Eulerian graph can be partitioned into good circuits if and only if there are no bad cuts. The above result of Seymour is obtained by letting the forbidden parts be the sets of parallel edges (`the parallel bundles'); the result of Fleischner follows by letting the forbidden parts be the forbidden transitions or singletons.