Home » Subject » Graph Theory » Coloring » Edge coloring

Packing T-joins

Importance: Medium ✭✭
Author(s): DeVos, Matt
Subject: Graph Theory
» Coloring
» » Edge coloring
Keywords: packing
T-join
Recomm. for undergrads: no
Prize: bottle of wine (DeVos)
Posted by: mdevos
on: March 7th, 2007
Conjecture   There exists a fixed constant $ c $ (probably $ c=1 $ suffices) so that every graft with minimum $ T $-cut size at least $ k $ contains a $ T $-join packing of size at least $ (2/3)k-c $.

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.

Bibliography

[CJ] M. Conforti and E.L. Johnson, Two min-max theorems for graphs noncontractible to a four wheel, preprint.

[C] G. Cornuejols, Combinatorial Optimization, packing and covering, SIAM, Philadelphia (2001).

[R] R. Rizzi, Indecomposable r-Graphs and Some Other Counterexamples, J. Graph Theory 32 (1999) 1-15. MathSciNet

[RSST] N. Robertson, D.P. Sanders, P.D. Seymour, and R. Thomas, A New Proof of the Four-Color Theorem, Electron. Res. Announc., Am. Math. Soc. 02, no 1 (1996) 17-25.

[S] P.D. Seymour, Some Unsolved Problems on One-Factorizations of Graphs, in Graph Theory and Related Topics, edited by J.A. Bondy and U.S.R. Murty, Academic Press, New York 1979) 367-368.


* indicates original appearance(s) of problem.
add new comment