Even cycles in directed graphs

DOI10.1016/S0195-6698(85)80025-1zbMath0606.05039MaRDI QIDQ1084409

Carsten Thomassen

Publication date: 1985

Published in: European Journal of Combinatorics (Search for Journal in Brave)

zbMATH Keywords

NP completenesseven cycles in digraphs

Mathematics Subject Classification ID

Paths and cycles (05C38) Directed graphs (digraphs), tournaments (05C20)

Related Items

Strong complete minors in digraphs, Finding good 2-partitions of digraphs. II. Enumerable properties, Immersion of transitive tournaments in digraphs with large minimum outdegree, Cycles of length 0 modulo k in directed graphs, Regularity of matrices in min-algebra and its time-complexity, Hamilton-connectivity of line graphs with application to their detour index, Existence of vertices of local connectivity \(k\) in digraphs of large outdegree, A note on odd/even cycles, Disjoint Cycles with Length Constraints in Digraphs of Large Connectivity or Large Minimum Degree, Every 7-regular digraph contains an even cycle, Low chromatic spanning sub(di)graphs with prescribed degree or connectivity properties, On spanning galaxies in digraphs, Equilibria of graphical games with symmetries, Immersing complete digraphs, Out-degree reducing partitions of digraphs, Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs, Pseudo and strongly pseudo 2-factor isomorphic regular graphs and digraphs, A note on complete subdivisions in digraphs of large outdegree, Subdivisions of digraphs in tournaments, Finding even cycles even faster, Existence of openly disjoint circuits through a vertex, On splitting digraphs, The Even Cycle Problem for Directed Graphs, The Hoàng-Reed conjecture for \(\delta ^{+}=3\), Even dicycles, What is on his mind?, Openly disjoint circuits through a vertex in regular digraphs, Directed path-width and monotonicity in digraph searching, Corrigendum to ``Graphs and digraphs with all 2-factors isomorphic [J. Combin. Theory Ser. B 92 (2) (2004) 395-404], A remark on ranks of sign patterns, Dichromatic number and forced subdivisions, Square critically 3-chromatic hypergraphs, Strong orientations without even directed circuits, Note on alternating directed cycles, Spanning galaxies in digraphs, Rank decompositions and signed bigraphs, Highly linked tournaments with large minimum out-degree, Signsolvability revisited, Degree and local connectivity in digraphs, Sign-nonsingular matrices and even cycles in directed graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Signsolvability revisited
• The directed subgraph homeomorphism problem
• An application of connectivity theory in graphs to factorizations of elements in groups
• Homomorphieeigenschaften und mittlere Kantendichte von Graphen
• Eine Verallgemeinerung des \(n\)-fachen Zusammenhangs für Graphen
• Grad und lokaler Zusammenhang in endlichen Graphen
• Graph decomposition with applications to subdivisions and path systems modulo k
• Cycles in digraphs– a survey
• ON THE TWO-COLOURING OF HYPERGRAPHS
• Paths, Trees, and Flowers
• On the Existence of Certain Configurations within Graphs and the 1-Skeletons of Polytopes
• On minimal regular digraphs with given girth