![](/files/happy5.png)
![$ c $](/files/tex/dccee841f3f498c2c58fa6ae1c1403c5a88c5b8d.png)
![$ c=1 $](/files/tex/7a8b9609d823e7ffb81159e3dfcbd5cb2599e11d.png)
![$ T $](/files/tex/79f55d2e1d83a7726c807a70cbe756713b0437b6.png)
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
![$ T $](/files/tex/79f55d2e1d83a7726c807a70cbe756713b0437b6.png)
![$ (2/3)k-c $](/files/tex/da50fbb1472ce7fd6fa00876af3022e1be50d2ec.png)
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
.
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ r $](/files/tex/535dee6c3b72bcc4d571239ed00be162ee1e6fbe.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ T $](/files/tex/79f55d2e1d83a7726c807a70cbe756713b0437b6.png)
![$ r-2 $](/files/tex/f37daf1c8757f9dcd110a62570c3a73054a4fc96.png)
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.
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ >2k+1 $](/files/tex/b25c4d0677d1f8ff5eb9cd4e7fe782d7c63601f3.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ 2k+1 $](/files/tex/2642e9bd0dbf7ce13ccc3ecdc069c9c955335fb6.png)
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.
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ >2k $](/files/tex/44c96e9d319a40662c84dca622257fc6f4cadccc.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ 2k+1 $](/files/tex/2642e9bd0dbf7ce13ccc3ecdc069c9c955335fb6.png)
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.