Packing T-joins

Discussion

Definitions: A graft consists of a graph $ G=(V,E) $ together with a distinguished set $ T \subseteq V $ of even cardinality. A $ T $ - cut is an edge-cut $ \delta(X) $ of $ G $ with the property that $ |X \cap T| $ is odd. A $ T $ - join is a set $ S \subseteq E $ with the property that a vertex of $ (V,S) $ has odd degree if and only if it is in $ T $ . A $ T $ -join packing is a set of pairwise disjoint T-joins. It is an easy fact that every $ T $ -join and every $ T $ -cut intersect in an odd number of elements. It follows easily from this that the maximum size of a $ T $ -join packing is always less than or equal to the minimum size of a $ T $ -cut. There is a simple example of a graft with $ |T|=4 $ with minimum $ T $ -cut size $ k $ which contains only $ (2/3)k $ 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 $ T $ -cut size $ k $ contains a $ T $ -join packing of size at least the floor of $ (1/3)k $ . Definition: We say that a graft $ G $ is an $ r $ - graph if $ G $ is $ r $ -regular, $ T=V $ , and every $ T $ -cut of G has size at least $ r $ . Conjecture (Rizzi) If $ G $ is an $ r $ -graph, then $ G $ contains a $ T $ -join packing of size at least $ r-2 $ . In an $ r $ -graph, every perfect matching is a $ T $ -join, so the above conjecture is true with room to spare for $ r $ -graphs which are $ r $ -edge-colorable. Indeed, Seymour had earlier conjectured that every $ r $ -graph contains $ r-2 $ disjoint perfect matchings. This however was disproved by Rizzi [R] who constructed for every $ r>2 $ an $ r $ -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 $ r $ -graph has a $ T $ -join packing of size at least the floor of $ r/2 $ . Definition: Let $ G $ be a graph and let $ T $ be the set of vertices of $ G $ of odd degree. A $ T $ -join of $ (G,T) $ is defined to be a postman set . Note that when $ T $ is the set of vertices of odd degree, a cocycle of $ G $ is a $ T $ -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 $ r $ is odd. Conjecture (The packing postman sets conjecture (Rizzi)) If every odd edge-cut of $ G $ has size $ >2k+1 $ then the edges of $ G $ may be partitioned into $ 2k+1 $ postman sets. The Petersen graph (or more generally any non $ (2k+1) $ -edge-colorable $ (2k+1) $ -graph) shows that the above conjecture would be false with the weaker assumption that every odd edge-cut has size $ >2k $ . The following conjecture asserts that odd edge-cut size $ >2k $ is enough (for the same conclusion) if we assume in addition that G has no Petersen minor. Conjecture (Conforti, Johnson) If $ G $ has no Petersen minor and every odd edge-cut of $ G $ has size $ >2k $ then the edges of $ G $ may be partitioned into $ 2k+1 $ 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.