Lovász–Woodall conjecture
In graph theory, the Lovász–Woodall conjecture is a long-standing problem on cycles in graphs. It says:
- If G is a k-connected graph and L is a set of k independent edges in G, then G has a cycle containing L, unless k is odd and L is an edge cut.
It was proposed independently by László Lovász[1] in 1974 and by D. R. Woodall[2] in 1977.
Background and motivation[edit]
Many results in graph theory, starting with Menger's theorem, guarantee the existence of paths or cycles in a k-connected graph. For 2-connected graphs, Menger's theorem is equivalent to the statement that any two vertices lie on a common cycle. A theorem of G. A. Dirac generalizes this claim: if a graph is k-connected for k ≥ 2, then for every set of k vertices in the graph there is a cycle that passes through all the vertices in the set.[3]
Another corollary of Menger's theorem is that in 2-connected graphs, any two edges lie on a common cycle. The proof, however, does not generalize to the corresponding statement for k edges in a k-connected graph; rather, Menger's theorem can be used to show that in a k-connected graph, given any 2 edges and k-2 vertices, there is a cycle passing through all of them.[4]
There is one obstacle to the stronger claim that in a k-connected graph G, given any set L of k edges, there should be a cycle containing L. Suppose that the edges in L form an edge cut: the vertices of G can be separated into two sets A and B such that the edges in L all join a vertex in A to a vertex in B, and are the only edges to do so. Then any cycle in G can only use an even number of edges of L: it must cross from A to B and from B back to A an equal number of times. If k is odd, this means that no cycle can contain all of L.
The Lovász–Woodall conjecture states that this is the only obstacle: given any set L of k edges, there is a cycle containing L, except in the case that k is odd and L is an edge cut.
Woodall proposed the conjecture as one of several possible statements[2] that would imply a conjecture made by Claude Berge: given a k-connected graph G with independence number α(G), and any subgraph F of G with at most k-α(G) edges whose components are all paths, G has a Hamiltonian cycle containing F.[5] In 1982, Roland Häggkvist and Carsten Thomassen proved Berge's conjecture by proving one of the weaker statements proposed by Woodall.[6]
Partial results[edit]
As mentioned above, the k = 2 case of the Lovász–Woodall conjecture follows from Menger's theorem. The k = 3 case was given as an exercise by Lovász.[7] After the conjecture was made, it was proven for k = 4 by Péter L. Erdős and E. Győri[8] and independently by Michael V. Lomonosov.[9], and for k = 5 by Daniel P. Sanders.[10]
Other partial progress toward the conjecture has included versions of the result with a stronger assumption on connectivity. Woodall's paper[2] included a proof that the conclusion of the conjecture holds if G is (2k-2)-connected, and in 1977, Thomassen proved that the conjecture holds if G is (3k-1)/2-connected.[11] In 1982, Häggkvist and Thomassen proved that the conjecture holds if G is (k+1)-connected.[6]
In 2002, Ken-ichi Kawarabayashi proved that under the hypotheses of the conjecture, L is either contained in a cycle of G or in two disjoint cycles.[7]
Current status[edit]
In two publications in 2002[7] and 2008,[12] Kawarabayashi claimed to have a proof on the conjecture, giving an outline for the proof and leaving several steps to future publications, but the full proof has not been published since.
References[edit]
- ^ Lovász, László (1974), "Problem 5", Period. Math. Hungar., 4: 82
- ^ a b c Woodall, D. R. (1977), "Circuits containing specified edges", J. Comb. Theory Ser. B, 22 (3): 274–278, doi:10.1016/0095-8956(77)90072-7
- ^ Dirac, Gabriel Andrew (1960). "In abstrakten Graphen vorhandene vollständige 4-Graphen und ihre Unterteilungen". Mathematische Nachrichten. 22 (1–2): 61–85. doi:10.1002/mana.19600220107. MR 0121311..
- ^ Berge, Claude (1973). Graphs and Hypergraphs. North-Holland Publishing Company. pp. 169–170. ISBN 0-444-10399-6.
- ^ Berge, p. 214
- ^ a b Häggkvist, Roland; Thomassen, Carsten (1982), "Circuits through specified edges", Discrete Mathematics, 41 (1): 29–34, doi:10.1016/0012-365X(82)90078-4
- ^ a b c Kawarabayashi, Ken-ichi (2002), "One or two disjoint circuits cover independent edges. Lovász-Woodall conjecture", Journal of Combinatorial Theory, Series B, 84 (1): 1–44, doi:10.1006/jctb.2001.2059, MR 1877899
- ^ Erdős, Péter L.; Győri, E. (1985), "Any four independent edges of a 4-connected graph are contained in a circuit", Acta Mathematica Hungarica, 46 (3–4): 311–313, doi:10.1007/BF01955745, MR 0832725, S2CID 122211600
- ^ Lomonosov, Michael V. (1990), "Cycles through prescribed elements in a graph", in Korte, Bernhard; Lovász, László; Prömel, Hans Jürgen; Schrijver, Alexander (eds.), Paths, flows, and VLSI-layout: Papers from the meeting held at the University of Bonn, Bonn, June 20–July 1, 1988, Algorithms and Combinatorics, vol. 9, Berlin: Springer-Verlag, pp. 215–234, ISBN 3-540-52685-4, MR 1083381
- ^ Sanders, Daniel P. (1996), "On circuits through five edges", Discrete Mathematics, 159 (1–3): 199–215, doi:10.1016/0012-365X(95)00079-C, MR 1415294
- ^ Thomassen, Carsten (1977), "Note on circuits containing specified edges", Journal of Combinatorial Theory, Series B, 22 (3): 279–280, doi:10.1016/0095-8956(77)90073-9
- ^ Kawarabayashi, Ken-ichi (2008), "An improved algorithm for finding cycles through elements", in Lodi, Andrea; Panconesi, Alessandro; Rinaldi, Giovanni (eds.), Integer Programming and Combinatorial Optimization, 13th International Conference, IPCO 2008, Bertinoro, Italy, May 26-28, 2008, Proceedings, Lecture Notes in Computer Science, vol. 5035, Springer, pp. 374–384, doi:10.1007/978-3-540-68891-4_26, ISBN 978-3-540-68886-0