Geodesic
The even cycle problem for directed graphs
Journal of the American Mathematical Society, Tome 05 (1992) no. 2, pp. 217-229

Voir la notice de l'article provenant de la source American Mathematical Society

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. 
@article{10_1090_S0894_0347_1992_1135027_1,
     author = {Thomassen, Carsten},
     title = {The even cycle problem for directed graphs},
     journal = {Journal of the American Mathematical Society},
     pages = {217--229},
     publisher = {mathdoc},
     volume = {05},
     number = {2},
     year = {1992},
     doi = {10.1090/S0894-0347-1992-1135027-1},
     url = {http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-1992-1135027-1/}
}
TY  - JOUR
AU  - Thomassen, Carsten
TI  - The even cycle problem for directed graphs
JO  - Journal of the American Mathematical Society
PY  - 1992
SP  - 217
EP  - 229
VL  - 05
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-1992-1135027-1/
DO  - 10.1090/S0894-0347-1992-1135027-1
ID  - 10_1090_S0894_0347_1992_1135027_1
ER  - 
%0 Journal Article
%A Thomassen, Carsten
%T The even cycle problem for directed graphs
%J Journal of the American Mathematical Society
%D 1992
%P 217-229
%V 05
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-1992-1135027-1/
%R 10.1090/S0894-0347-1992-1135027-1
%F 10_1090_S0894_0347_1992_1135027_1
Thomassen, Carsten. The even cycle problem for directed graphs. Journal of the American Mathematical Society, Tome 05 (1992) no. 2, pp. 217-229. doi: 10.1090/S0894-0347-1992-1135027-1

[1] Alon, Noga, Linial, N. Cycles of length 0 modulo 𝑘 in directed graphs J. Combin. Theory Ser. B 1989 114 119

[2] Friedland, Shmuel Every 7-regular digraph contains an even cycle J. Combin. Theory Ser. B 1989 249 252

[3] Kasteleyn, P. W. Graph theory and crystal physics 1967 43 110

[4] Klee, Victor, Ladner, Richard, Manber, Rachel Signsolvability revisited Linear Algebra Appl. 1984 131 157

[5] Little, Charles H. C. An extension of Kasteleyn’s method of enumerating the 1-factors of planar graphs 1974 63 72

[6] Lovã¡Sz, Lã¡Szlã³ Matching structure and the matching lattice J. Combin. Theory Ser. B 1987 187 222

[7] Pyber, L. Regular subgraphs of dense graphs Combinatorica 1985 347 349

[8] Sachs, Horst Perfect matchings in hexagonal systems Combinatorica 1984 89 99

[9] Seymour, P. D. On the two-colouring of hypergraphs Quart. J. Math. Oxford Ser. (2) 1974 303 312

[10] Seymour, Paul, Thomassen, Carsten Characterization of even directed graphs J. Combin. Theory Ser. B 1987 36 45

[11] Thomassen, Carsten Even cycles in directed graphs European J. Combin. 1985 85 89

[12] Thomassen, Carsten Sign-nonsingular matrices and even cycles in directed graphs Linear Algebra Appl. 1986 27 41

[13] Thomassen, Carsten Paths, circuits and subdivisions 1988 97 131

[14] Vazirani, Vijay V., Yannakakis, Milhalis Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs Discrete Appl. Math. 1989 179 190

Cité par Sources :