Local 2-separators

DOI10.1016/J.JCTB.2022.04.005MaRDI QIDQ2673481zbMATH OpenOpenAlexFDO

Authors Johannes Carmesin

Publication date 10 June 2022

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

Full work available at URL https://arxiv.org/abs/2008.03032

zbMATH Keywords

localitystructural graph theory2-separator theoremcharacterisations of graphslocal cutverticeslocal separators

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Density (toughness, etc.) (05C42) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph minors (05C83)

Abstract: How can sparse graph theory be extended to large networks, where algorithms whose running time is estimated using the number of vertices are not good enough? I address this question by introducing 'Local Separators' of graphs. Applications include: 1. A unique decomposition theorem for graphs along their local 2-separators analogous to the 2-separator theorem; 2. an exact characterisation of graphs with no bounded subdivision of a wheel; 3. an analogue of the tangle-tree theorem of Robertson and Seymour, where the decomposition-tree is replaced by a general graph.

Recommendations

• SEPARABILITY IN LOCALES
• Local separation in distributive semilattices
• scientific article; zbMATH DE number 3977293
• Generalized local separation properties
• scientific article; zbMATH DE number 4111557
• On 2-locally Seidel graphs
• Local Brunella's Alternative II. Partial Separatrices
• scientific article; zbMATH DE number 1241915
• Local duality
• Two local inequalities

Cites work

• scientific article; zbMATH DE number 3873585 (Why is no real title available?)
• scientific article; zbMATH DE number 2103273 (Why is no real title available?)
• scientific article; zbMATH DE number 5873618 (Why is no real title available?)
• 3-connected reduction for regular graph covers
• A Combinatorial Decomposition Theory
• Canonical tree-decompositions of a graph that display its k-blocks
• Covering theory for graphs of groups
• Deciding first-order properties of locally tree-decomposable structures
• Decomposition of regular matroids
• Every minor-closed property of sparse graphs is testable
• Graph clustering
• Graph minor hierarchies
• Graph minors. X: Obstructions to tree-decomposition
• Graph minors. XX: Wagner's conjecture
• Large networks and graph limits
• Limits of dense graph sequences
• Local 2-separators
• Local tree-width, excluded minors, and approximation algorithms
• ON THE STRUCTURE OF GRAPHS WHICH ARE LOCALLY INDISTINGUISHABLE FROM A LATTICE
• On covers of graphs by Cayley graphs
• Quasi-4-Connected Components
• Rank-width and vertex-minors
• Recurrence of distributional limits of finite planar graphs
• Recurrence of planar graph limits
• Sparse exchangeable graphs and their limits via graphon processes
• Sparse graphs using exchangeable random measures
• Sparsity. Graphs, structures, and algorithms
• The classification of connected-homogeneous digraphs with more than one end
• The classification of finite and locally finite connected-homogeneous digraphs
• The strong perfect graph theorem
• Topological cycle matroids of infinite graphs
• Topological graph theory.
• Tree decompositions and social graphs

Cited in

(5)

• scientific article; zbMATH DE number 4111557 (Why is no real title available?)
• Entanglements
• Small hitting sets for longest paths and cycles
• Characterising graphs with no subdivision of a wheel of bounded diameter
• Local 2-separators

This page was built for publication: Local 2-separators

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