Distance Hereditary Graphs and the Interlace Polynomial

DOI10.1017/S0963548307008723zbMath1129.05051arXivmath/0604088OpenAlexW2110055721MaRDI QIDQ5428369

Joanna A. Ellis-Monaghan, Irasema Sarmiento

Publication date: 22 November 2007

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

Tutte polynomialplanar graphdistance-hereditary graphseries-parallel graphmedial graphcircle graphinterlace polynomial

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (05C99)

Related Items (9)

A tight relation between series-parallel graphs and bipartite distance hereditary graphs ⋮ The adjacency matroid of a graph ⋮ Interlace polynomials of 4n-snowflake graphs ⋮ Fast evaluation of interlace polynomials on graphs of bounded treewidth ⋮ Weighted Interlace Polynomials ⋮ On graphs and codes preserved by edge local complementation ⋮ Isotropic matroids. I: Multimatroids and neighborhoods ⋮ A Graph Integral Formulation of the Circuit Partition Polynomial ⋮ On the interlace polynomials of forests

Cites Work

• A two-variable interlace polynomial
• Chordality properties on graphs and minimal conceptual connections in semantic data models
• Tutte polynomials computable in polynomial time
• A polynomial of graphs on surfaces
• The interlace polynomial of a graph
• A characterization of circle graphs
• Distance-hereditary graphs
• Isotropic systems
• Unimodularity and circle graphs
• Graphic presentations of isotropic systems
• Reducing prime graphs and recognizing circle graphs
• On the evaluation at (3,3) of the Tutte polynomial of a graph
• Tutte-Martin polynomials and orienting vectors of isotropic systems
• Remarkable valuation of the dichromatic polynomial of planar multigraphs
• Compatible Euler tours and supplementary Eulerian vectors
• Circle graph obstructions
• Connectivity and \(\beta\)-invariants of isotropic systems and 4-regular graphs
• A proof of a circle graph characterization
• Interlace polynomials
• Identities for circuit partition polynomials, with applications to the Tutte polynomial
• New results for the Martin polynomial
• Euler circuits and DNA sequencing by hybridization
• Exploring the Tutte-Martin connection
• Alternating knot diagrams, Euler circuits and the interlace polynomial
• Evaluations of the circuit partition polynomial
• The interlace polynomial of graphs at \(-1\)
• Topology of series-parallel networks
• Approximating clique-width and branch-width
• Rank-width and vertex-minors
• Graph polynomials derived from Tutte-Martin polynomials
• A Polynomial Invariant of Graphs On Orientable Surfaces
• On Crapo's Beta Invariant for Matroids
• A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
• Graph colorings with local constraints -- a survey
• Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width
• A Combinatorial Model for Series-Parallel Networks
• A Contribution to the Theory of Chromatic Polynomials

This page was built for publication: Distance Hereditary Graphs and the Interlace Polynomial