Transforming trees by successive local complementations

DOI10.1002/jgt.3190120210zbMath0645.05059OpenAlexW2052159979MaRDI QIDQ3788053

André Bouchet

Publication date: 1988

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/jgt.3190120210

zbMATH Keywords

decompositioncomplementationgraph transformationlocal equivalencetotally decomposable graphs

Mathematics Subject Classification ID

Trees (05C05) Structural characterization of families of graphs (05C75)

Related Items (23)

Isotropic systems ⋮ Vertex-minors, monadic second-order logic, and a conjecture by Seese ⋮ Rank-width: algorithmic and structural results ⋮ Linear rank-width of distance-hereditary graphs II. vertex-minor obstructions ⋮ A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion ⋮ Polynomial-time recognition of clique-width \(\leq 3\) graphs ⋮ Graphs of small rank-width are pivot-minors of graphs of small tree-width ⋮ Matroids that classify forests ⋮ Transitivity of local complementation and switching on graphs. ⋮ The average cut-rank of graphs ⋮ Recognizing locally equivalent graphs ⋮ Linear rank-width of distance-hereditary graphs. I. A polynomial-time algorithm ⋮ Graphs with bounded induced distance ⋮ Distance-hereditary comparability graphs ⋮ Isotropic matroids. I: Multimatroids and neighborhoods ⋮ A polynomial kernel for distance-hereditary vertex deletion ⋮ Excluded vertex-minors for graphs of linear rank-width at most \(k\) ⋮ From graph states to two-graph states ⋮ Treelike comparability graphs ⋮ Distance-Hereditary Comparability Graphs ⋮ Rank-width and vertex-minors ⋮ Linear rank-width and linear clique-width of trees ⋮ Tree Pivot-Minors and Linear Rank-Width

Cites Work

• Isotropic systems
• Unnamed Item

This page was built for publication: Transforming trees by successive local complementations