Menger's theorem for countable graphs

DOI10.1016/0095-8956(87)90006-2MaRDI QIDQ1094433zbMATH OpenOpenAlexFDO

Authors Ron Aharoni

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)90006-2

zbMATH Keywords

disjoint pathsinfinite graphsrelationseparating setwaves

Mathematics Subject Classification ID

Connectivity (05C40) Graph theory (05C99)

Review text

Let be G a graph with V(G) countable and A,B\(\subseteq V(G)\). The author defines a relation on the triple (G,A,B), e.g. a web or gammoid, using families of disjoint paths which separates A and B, called waves. Using this relation he proves the countable case of the following conjecture of Erdős [see, e.g. \textit{C. St. J. A. Nash-Williams}, J. Comb. Theory 3, 286-301 (1967; Zbl 0153.258)]. In any graph there exists a set \({\mathcal P}\) of disjoint A-B paths and an A-B separating set S, such that S consists of the choice of precisely one vertex from each path in \({\mathcal P}\).

Recommendations

• Menger's Theorem for a Countable Source Set
• scientific article; zbMATH DE number 970819
• Countable Menger's theorem with finitary matroid constraints on the ingoing edges
• Menger's theorem for infinite graphs
• The countable Erdős-Menger conjecture with ends

Cites work

• Hamiltonian Lines in Products of Infinite Trees
• scientific article; zbMATH DE number 3174052 (Why is no real title available?)
• scientific article; zbMATH DE number 3266615 (Why is no real title available?)
• scientific article; zbMATH DE number 3395951 (Why is no real title available?)
• scientific article; zbMATH DE number 3060538 (Why is no real title available?)
• König's Duality Theorem for Infinite Bipartite Graphs
• Menger's theorem for graphs containing no infinite paths
• Über Translationen und den Satz von Menger in unendlichen Graphen

Cited in

(22)

• Menger's theorem for infinite graphs
• A Mengerian theorem for infinite graphs with ideal points
• The Menger property for infinite ordered sets
• Infinite matching theory
• The countable Erdős-Menger conjecture with ends
• A Ramsey theorem for countable homogeneous directed graphs
• Countable Menger's theorem with finitary matroid constraints on the ingoing edges
• Topological infinite gammoids, and a new Menger-type theorem for infinite graphs
• Hadwiger's conjecture for uncountable graphs
• On packing and covering polyhedra in infinite dimensions
• Strongly maximal antichains in posets
• 2010 European Summer Meeting of the Association for Symbolic Logic. Logic Colloquium '10
• scientific article; zbMATH DE number 4181378 (Why is no real title available?)
• Menger's theorem in \(\Pi^1_1 \mathrm {-CA}_0\)
• Menger's Theorem for a Countable Source Set
• Metric dimensions of minor excluded graphs and minor exclusion in groups.
• scientific article; zbMATH DE number 6258250 (Why is no real title available?)
• The first Roe homology group of locally finite graphs
• The Erdős-Menger conjecture for source/sink sets with disjoint closures
• Locally finite graphs with ends: A topological approach. II: Applications
• A generalization of Tutte's 1-factor theorem to countable graphs
• LP duality in infinite hypergraphs

This page was built for publication: Menger's theorem for countable graphs

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