Characterization of even directed graphs

DOI10.1016/0095-8956(87)90061-XMaRDI QIDQ1085177zbMATH OpenOpenAlexFDO

Authors Paul Seymour, Carsten Thomassen

Publication date 1987

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0095-8956(87)90061-x

zbMATH Keywords

cycle basesdirected graphseven cycles

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Structural characterization of families of graphs (05C75)

Review text

The authors give a structural characterization of directed graphs D with the property that every subdivision of D contains a cycle of even length.

Cites work

• A Solution of the Shannon Switching Game
• Cycles in digraphs– a survey
• On digraphs with the odd cycle property
• ON THE TWO-COLOURING OF HYPERGRAPHS
• Sign-nonsingular matrices and even cycles in directed graphs
• Signsolvability revisited
• The 2-linkage problem for acyclic digraphs
• The directed subgraph homeomorphism problem

Cited in

(31)

• Sign-nonsingular matrices and even cycles in directed graphs
• A note on odd/even cycles
• When the sign pattern of a square matrix determines uniquely the sign pattern of its inverse
• The symbiotic relationship of combinatorics and matrix theory
• Matching theory -- a sampler: From Dénes König to the present
• On the permanent of certain (0,1) Toeplitz matrices
• On the digraphs of sign solvable linear systems
• Strong orientations without even directed circuits
• On digraphs and forbidden configurations of strong sign nonsingular matrices
• A new proof of a characterisation of Pfaffian bipartite graphs
• Nearly sign-nonsingular matrices
• Colouring non-even digraphs
• Subdivisions in digraphs of large out-degree or large dichromatic number
• Convertible, nearly decomposable, and nearly reducible matrices
• Classes of sign nonsingular matrices with a specified number of zero entries
• On maximal sign-nonsingular matrices
• The parity Hamiltonian cycle problem in directed graphs
• The Even Cycle Problem for Directed Graphs
• Even circuits in oriented matroids
• Matching structure of symmetric bipartite graphs and a generalization of Pólya's problem
• Excluding a planar matching minor in bipartite graphs
• Forward and line-based cycle bases for periodic timetabling
• Colouring non-even digraphs
• Packing directed circuits exactly
• Forcing, anti-forcing, global forcing and complete forcing on perfect matchings of graphs -- a survey
• Oriented cycles in digraphs of large outdegree
• When all directed cycles have length three
• A star-comb lemma for finite digraphs
• Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs
• Solving linear programs from sign patterns
• Sign-solvable linear complementarity problems

This page was built for publication: Characterization of even directed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1085177)