|
The even cycle problem for directed graphs
Author(s):
Carsten
Thomassen
Journal:
J. Amer. Math. Soc.
5
(1992),
217-229.
MSC:
Primary 05C20;
Secondary 05C38
MathSciNet review:
1135027
Retrieve article in:
PDF
This article is available free of charge
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.
References:
-
- [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)
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:
10.1090/S0894-0347-1992-1135027-1
PII:
S0894-0347-1992-1135027-1
Copyright of article:
Copyright
1992,
American Mathematical Society
|
