## 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, - 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, - 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**
—, - 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

*Problem*2, Recent Advances in Graph Theory (M. Friedler, ed.), Proceedings Symposium Prague, 1974, Academia Praha, Prague, 1975.

*Aufgabe*424, Arch. Math. Phys. Ser. (3)

**20**(1913), 271.

*The even cycle problem for planar digraphs*(to appear).

## 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