The even cycle problem for directed graphs

Author:
Carsten Thomassen

Journal:
J. Amer. Math. Soc. **5** (1992), 217-229

MSC:
Primary 05C20; Secondary 05C38

MathSciNet review:
1135027

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

**[1]**Noga Alon and N. Linial,*Cycles of length 0 modulo 𝑘 in directed graphs*, J. Combin. Theory Ser. B**47**(1989), no. 1, 114–119. MR**1007720**, 10.1016/0095-8956(89)90071-3**[2]**Shmuel Friedland,*Every 7-regular digraph contains an even cycle*, J. Combin. Theory Ser. B**46**(1989), no. 2, 249–252. MR**992995**, 10.1016/0095-8956(89)90047-6**[3]**P. W. Kasteleyn,*Graph theory and crystal physics*, Graph Theory and Theoretical Physics, Academic Press, London, 1967, pp. 43–110. MR**0253689****[4]**Victor Klee, Richard Ladner, and Rachel Manber,*Signsolvability revisited*, Linear Algebra Appl.**59**(1984), 131–157. MR**743051**, 10.1016/0024-3795(84)90164-2**[5]**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) Springer, Berlin, 1974, pp. 63–72. Lecture Notes in Math., Vol. 403. MR**0382062****[6]**L. Lovász,*Problem*2, Recent Advances in Graph Theory (M. Friedler, ed.), Proceedings Symposium Prague, 1974, Academia Praha, Prague, 1975.**[7]**László Lovász,*Matching structure and the matching lattice*, J. Combin. Theory Ser. B**43**(1987), no. 2, 187–222. MR**904405**, 10.1016/0095-8956(87)90021-9**[8]**G. Polya,*Aufgabe*424, Arch. Math. Phys. Ser. (3)**20**(1913), 271.**[9]**L. Pyber,*Regular subgraphs of dense graphs*, Combinatorica**5**(1985), no. 4, 347–349. MR**845145**, 10.1007/BF02579250**[10]**Horst Sachs,*Perfect matchings in hexagonal systems*, Combinatorica**4**(1984), no. 1, 89–99. MR**739417**, 10.1007/BF02579161**[11]**P. D. Seymour,*On the two-colouring of hypergraphs*, Quart. J. Math. Oxford Ser. (2)**25**(1974), 303–312. MR**0371710****[12]**Paul Seymour and Carsten Thomassen,*Characterization of even directed graphs*, J. Combin. Theory Ser. B**42**(1987), no. 1, 36–45. MR**872406**, 10.1016/0095-8956(87)90061-X**[13]**Carsten Thomassen,*Even cycles in directed graphs*, European J. Combin.**6**(1985), no. 1, 85–89. MR**793491**, 10.1016/S0195-6698(85)80025-1**[14]**Carsten Thomassen,*Sign-nonsingular matrices and even cycles in directed graphs*, Linear Algebra Appl.**75**(1986), 27–41. MR**825397**, 10.1016/0024-3795(86)90179-5**[15]**Carsten Thomassen,*Paths, circuits and subdivisions*, Selected topics in graph theory, 3, Academic Press, San Diego, CA, 1988, pp. 97–131. MR**1205398****[16]**-,*The even cycle problem for planar digraphs*(to appear).**[17]**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**, 10.1016/0166-218X(89)90053-X

Retrieve articles in *Journal of the American Mathematical Society*
with MSC:
05C20,
05C38

Retrieve articles in all journals with MSC: 05C20, 05C38

Additional Information

DOI:
http://dx.doi.org/10.1090/S0894-0347-1992-1135027-1

Article copyright:
© Copyright 1992
American Mathematical Society