The even cycle problem for directed graphs
Author:
Carsten Thomassen
Journal:
J. Amer. Math. Soc. 5 (1992), 217229
MSC:
Primary 05C20; Secondary 05C38
MathSciNet review:
1135027
Fulltext 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 colourcritical hypergraphs, signnonsingular 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
(90g:05089), http://dx.doi.org/10.1016/00958956(89)900713
 [2]
Shmuel
Friedland, Every 7regular digraph contains an even cycle, J.
Combin. Theory Ser. B 46 (1989), no. 2,
249–252. MR
992995 (90c:05126), http://dx.doi.org/10.1016/00958956(89)900476
 [3]
P.
W. Kasteleyn, Graph theory and crystal physics, Graph Theory
and Theoretical Physics, Academic Press, London, 1967,
pp. 43–110. MR 0253689
(40 #6903)
 [4]
Victor
Klee, Richard
Ladner, and Rachel
Manber, Signsolvability revisited, Linear Algebra Appl.
59 (1984), 131–157. MR 743051
(86a:15004), http://dx.doi.org/10.1016/00243795(84)901642
 [5]
Charles
H. C. Little, An extension of Kasteleyn’s method of
enumerating the 1factors 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 (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]
László
Lovász, Matching structure and the matching lattice, J.
Combin. Theory Ser. B 43 (1987), no. 2,
187–222. MR
904405 (88m:05060), http://dx.doi.org/10.1016/00958956(87)900219
 [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
(87j:05099), http://dx.doi.org/10.1007/BF02579250
 [10]
Horst
Sachs, Perfect matchings in hexagonal systems, Combinatorica
4 (1984), no. 1, 89–99. MR 739417
(85d:05075), http://dx.doi.org/10.1007/BF02579161
 [11]
P.
D. Seymour, On the twocolouring of hypergraphs, Quart. J.
Math. Oxford Ser. (2) 25 (1974), 303–312. MR 0371710
(51 #7927)
 [12]
Paul
Seymour and Carsten
Thomassen, Characterization of even directed graphs, J.
Combin. Theory Ser. B 42 (1987), no. 1, 36–45.
MR 872406
(88c:05089), http://dx.doi.org/10.1016/00958956(87)90061X
 [13]
Carsten
Thomassen, Even cycles in directed graphs, European J. Combin.
6 (1985), no. 1, 85–89. MR 793491
(86i:05098), http://dx.doi.org/10.1016/S01956698(85)800251
 [14]
Carsten
Thomassen, Signnonsingular matrices and even cycles in directed
graphs, Linear Algebra Appl. 75 (1986), 27–41.
MR 825397
(87k:05120), http://dx.doi.org/10.1016/00243795(86)901795
 [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, 01 permanents, and even cycles
in directed graphs, Discrete Appl. Math. 25 (1989),
no. 12, 179–190. Combinatorics and complexity (Chicago, IL,
1987). MR
1031270 (91e:05080), http://dx.doi.org/10.1016/0166218X(89)90053X
 [1]
 N. Alon and N. Lineal, Cycles of length modulo in directed graphs, J. Combin. Theory Ser. B 47 (1989), 114119. MR 1007720 (90g:05089)
 [2]
 S. Friedland, Every regular digraph contains an even cycle, J. Combin. Theory Ser. B 46 (1989), 249252. 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. 43110. MR 0253689 (40:6903)
 [4]
 V. Klee, R. Ladner, and R. Manber, Signsolvability revisited, Linear Algebra Appl. 59 (1984), 131158. 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. 6372. 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), 187222. 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), 347349. MR 845145 (87j:05099)
 [10]
 H. Sachs, Perfect matchings in hexagonal systems, Combinatorica 4 (1984), 8999. MR 739417 (85d:05075)
 [11]
 P. D. Seymour, On the two coloring of hypergraphs, Quart. J. Math. Oxford Ser. (3) 25 (1974), 303312. MR 0371710 (51:7927)
 [12]
 P. Seymour and C. Thomassen, Characterization of even directed graphs, J. Combin. Theory Ser. B 42 (1987), 3645. MR 872406 (88c:05089)
 [13]
 C. Thomassen, Even cycles in directed graphs, European J. Combin. 6 (1985), 8589. MR 793491 (86i:05098)
 [14]
 , Signnonsingular matrices and even cycles in directed graphs, Linear Algebra Appl. 75 (1986), 2741. 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. 97131. 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), 179190. MR 1031270 (91e:05080)
Similar Articles
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/S08940347199211350271
PII:
S 08940347(1992)11350271
Article copyright:
© Copyright 1992
American Mathematical Society
