Open Problem Garden

Definitions: A graft consists of a graph together with a distinguished set of even cardinality. A -cut is an edge-cut of with the property that is odd. A -join is a set with the property that a vertex of has odd degree if and only if it is in . A -join packing is a set of pairwise disjoint T-joins.

It is an easy fact that every -join and every -cut intersect in an odd number of elements. It follows easily from this that the maximum size of a -join packing is always less than or equal to the minimum size of a -cut. There is a simple example of a graft with with minimum -cut size which contains only disjoint T-joins. The above conjecture asserts that this is essentially the worst case. DeVos and Seymour [DS] have obtained a partial result toward the above conjecture, proving that every graft with minimum -cut size contains a -join packing of size at least the floor of .

Definition: We say that a graft is an -graph if is -regular, , and every -cut of G has size at least .

Conjecture  (Rizzi)   If is an -graph, then contains a -join packing of size at least .

In an -graph, every perfect matching is a -join, so the above conjecture is true with room to spare for -graphs which are -edge-colorable. Indeed, Seymour had earlier conjectured that every -graph contains disjoint perfect matchings. This however was disproved by Rizzi [R] who constructed for every an -graph in which every two perfect matchings intersect. Rizzi suggested the above problem as a possible fix for Seymour's conjecture. DeVos and Seymour have proved that every -graph has a -join packing of size at least the floor of .

Definition: Let be a graph and let be the set of vertices of of odd degree. A -join of is defined to be a postman set.

Note that when is the set of vertices of odd degree, a cocycle of is a -cut if and only if it has odd size. Rizzi has shown that the following conjecture is equivalent to the above conjecture in the special case when is odd.

Conjecture  (The packing postman sets conjecture (Rizzi))   If every odd edge-cut of has size then the edges of may be partitioned into postman sets.

The Petersen graph (or more generally any non -edge-colorable -graph) shows that the above conjecture would be false with the weaker assumption that every odd edge-cut has size . The following conjecture asserts that odd edge-cut size is enough (for the same conclusion) if we assume in addition that G has no Petersen minor.

Conjecture  (Conforti, Johnson)   If has no Petersen minor and every odd edge-cut of has size then the edges of may be partitioned into postman sets.

Gerard Cornuejols [C] has kindly offered $5000 for a solution to this conjecture. However, it will be tough to find a quick proof since this conjecture does imply the 4-color theorem. Robertson, Seymour, Sanders, and Thomas [RSST] have proved the above conjecture for cubic graphs. Conforti and Johnson [CJ] proved it under the added hypothesis that G has no 4-wheel minor.