The even cycle problem for directed graphs
HTML articles powered by AMS MathViewer
- by Carsten Thomassen
- J. Amer. Math. Soc. 5 (1992), 217-229
- DOI: https://doi.org/10.1090/S0894-0347-1992-1135027-1
- PDF | Request permission
Abstract:
If each arc in a strongly connected directed graph of minimum indegree and outdegree at least 3 is assigned a weight 0 or 1, then the resulting weighted directed graph has a directed cycle of even total weight. This proves a conjecture made by L. Lovász in 1975 and has applications to colour-critical hypergraphs, sign-nonsingular matrices, and permanents of matrices.References
- Noga Alon and N. Linial, Cycles of length $0$ modulo $k$ in directed graphs, J. Combin. Theory Ser. B 47 (1989), no. 1, 114–119. MR 1007720, DOI 10.1016/0095-8956(89)90071-3
- Shmuel Friedland, Every $7$-regular digraph contains an even cycle, J. Combin. Theory Ser. B 46 (1989), no. 2, 249–252. MR 992995, DOI 10.1016/0095-8956(89)90047-6
- P. W. Kasteleyn, Graph theory and crystal physics, Graph Theory and Theoretical Physics, Academic Press, London, 1967, pp. 43–110. MR 0253689
- Victor Klee, Richard Ladner, and Rachel Manber, Signsolvability revisited, Linear Algebra Appl. 59 (1984), 131–157. MR 743051, DOI 10.1016/0024-3795(84)90164-2
- Charles H. C. Little, An extension of Kasteleyn’s method of enumerating the $1$-factors of planar graphs, Combinatorial mathematics (Proc. Second Australian Conf., Univ. Melbourne, Melbourne, 1973) Lecture Notes in Math., Vol. 403, Springer, Berlin, 1974, pp. 63–72. MR 0382062 L. Lovász, Problem 2, Recent Advances in Graph Theory (M. Friedler, ed.), Proceedings Symposium Prague, 1974, Academia Praha, Prague, 1975.
- László Lovász, Matching structure and the matching lattice, J. Combin. Theory Ser. B 43 (1987), no. 2, 187–222. MR 904405, DOI 10.1016/0095-8956(87)90021-9 G. Polya, Aufgabe 424, Arch. Math. Phys. Ser. (3) 20 (1913), 271.
- L. Pyber, Regular subgraphs of dense graphs, Combinatorica 5 (1985), no. 4, 347–349. MR 845145, DOI 10.1007/BF02579250
- Horst Sachs, Perfect matchings in hexagonal systems, Combinatorica 4 (1984), no. 1, 89–99. MR 739417, DOI 10.1007/BF02579161
- P. D. Seymour, On the two-colouring of hypergraphs, Quart. J. Math. Oxford Ser. (2) 25 (1974), 303–312. MR 371710, DOI 10.1093/qmath/25.1.303
- Paul Seymour and Carsten Thomassen, Characterization of even directed graphs, J. Combin. Theory Ser. B 42 (1987), no. 1, 36–45. MR 872406, DOI 10.1016/0095-8956(87)90061-X
- Carsten Thomassen, Even cycles in directed graphs, European J. Combin. 6 (1985), no. 1, 85–89. MR 793491, DOI 10.1016/S0195-6698(85)80025-1
- Carsten Thomassen, Sign-nonsingular matrices and even cycles in directed graphs, Linear Algebra Appl. 75 (1986), 27–41. MR 825397, DOI 10.1016/0024-3795(86)90179-5
- Carsten Thomassen, Paths, circuits and subdivisions, Selected topics in graph theory, 3, Academic Press, San Diego, CA, 1988, pp. 97–131. MR 1205398 —, The even cycle problem for planar digraphs (to appear).
- Vijay V. Vazirani and Milhalis Yannakakis, Pfaffian orientations, $0$-$1$ permanents, and even cycles in directed graphs, Discrete Appl. Math. 25 (1989), no. 1-2, 179–190. Combinatorics and complexity (Chicago, IL, 1987). MR 1031270, DOI 10.1016/0166-218X(89)90053-X
Bibliographic Information
- © Copyright 1992 American Mathematical Society
- Journal: J. Amer. Math. Soc. 5 (1992), 217-229
- MSC: Primary 05C20; Secondary 05C38
- DOI: https://doi.org/10.1090/S0894-0347-1992-1135027-1
- MathSciNet review: 1135027