The even cycle problem for directed graphs

Author:
Carsten Thomassen

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

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]**N. Alon and N. Lineal,*Cycles of length**modulo**in directed graphs*, J. Combin. Theory Ser. B**47**(1989), 114-119. MR**1007720 (90g:05089)****[2]**S. Friedland,*Every**-regular digraph contains an even cycle*, J. Combin. Theory Ser. B**46**(1989), 249-252. MR**992995 (90c:05126)****[3]**P. W. Kasteleyn,*Graph theory and crystal physics*, Graph Theory and Theoretical Physics (F. Harary, ed.), Academic Press, New York, 1967, pp. 43-110. MR**0253689 (40:6903)****[4]**V. Klee, R. Ladner, and R. Manber,*Sign-solvability revisited*, Linear Algebra Appl.**59**(1984), 131-158. MR**743051 (86a:15004)****[5]**C. H. C. Little,*An extension of Kasteleyn's method of enumerating the**-factors of planar graphs*, Combinatorial Mathematics, Proceedings 2nd Australian Conference (D. Holton, ed.), Lecture Notes in Math., vol. 403, Springer, Berlin, 1974, pp. 63-72. MR**0382062 (52:2950)****[6]**L. Lovász,*Problem*2, Recent Advances in Graph Theory (M. Friedler, ed.), Proceedings Symposium Prague, 1974, Academia Praha, Prague, 1975.**[7]**-,*Matching structure and the matching lattice*, J. Combin. Theory Ser. B**43**(1987), 187-222. MR**904405 (88m:05060)****[8]**G. Polya,*Aufgabe*424, Arch. Math. Phys. Ser. (3)**20**(1913), 271.**[9]**L. Pyber,*Regular subgraphs of dense graphs*, Combinatorica**5**(1985), 347-349. MR**845145 (87j:05099)****[10]**H. Sachs,*Perfect matchings in hexagonal systems*, Combinatorica**4**(1984), 89-99. MR**739417 (85d:05075)****[11]**P. D. Seymour,*On the two coloring of hypergraphs*, Quart. J. Math. Oxford Ser. (3)**25**(1974), 303-312. MR**0371710 (51:7927)****[12]**P. Seymour and C. Thomassen,*Characterization of even directed graphs*, J. Combin. Theory Ser. B**42**(1987), 36-45. MR**872406 (88c:05089)****[13]**C. Thomassen,*Even cycles in directed graphs*, European J. Combin.**6**(1985), 85-89. MR**793491 (86i:05098)****[14]**-,*Sign-nonsingular matrices and even cycles in directed graphs*, Linear Algebra Appl.**75**(1986), 27-41. MR**825397 (87k:05120)****[15]**-,*Paths, circuits and subdivisions*, Selected Topics in Graph Theory (L. W. Beineke and R. L. Wilson, eds.), vol. 3, Academic Press, 1988, pp. 97-131. MR**1205398****[16]**-,*The even cycle problem for planar digraphs*(to appear).**[17]**V. V. Vazirani and M. Yannakakis,*Pfaffian orientations, 0 - 1 permanents, and even cycles in directed graphs*, Discrete Appl. Math.**25**(1989), 179-190. MR**1031270 (91e:05080)**

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:
https://doi.org/10.1090/S0894-0347-1992-1135027-1

Article copyright:
© Copyright 1992
American Mathematical Society