A characterization of circle graphs in terms of multimatroid representations

DOI10.37236/6992zbMATH Open1431.05032OpenAlexW3002760791MaRDI QIDQ2290352FDOQ2290352

Authors: Robert Brijder, L. Traldi 

Publication date: 27 January 2020

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: The isotropic matroid $M[IAS(G)]$ of a looped simple graph $G$ is a binary matroid equivalent to the isotropic system of $G$. In general, $M[IAS(G)]$ is not regular, so it cannot be represented over fields of characteristic $eq2$. The ground set of $M[IAS(G)]$ is denoted $W(G)$; it is partitioned into 3-element subsets corresponding to the vertices of $G$. When the rank function of $M[IAS(G)]$ is restricted to subtransversals of this partition, the resulting structure is a multimatroid denoted $mathcal{Z}_3(G)$. In this paper we prove that $G$ is a circle graph if and only if for every field $mathbbF$, there is an $mathbbF$-representable matroid with ground set $W(G)$, which defines $mathcal{Z}_3(G)$ by restriction. We connect this characterization with several other circle graph characterizations that have appeared in the literature.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• A characterization of circle graphs in terms of total unimodularity
• Isotropic matroids. I: Multimatroids and neighborhoods
• Isotropic matroids. II: Circle graphs
• Graphs for \(n\)-circular matroids
• Representations of bicircular matroids

zbMATH Keywords

regularitymatroidrepresentationcircle graphdelta-matroidisotropic systemlocal equivalencemultimatroidunimodular orientation

Mathematics Subject Classification ID

Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Combinatorial aspects of matroids and geometric lattices (05B35)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A characterization of circle graphs
• A proof of a circle graph characterization
• An alternative formula for the number of Euler trails for a class of digraphs
• Binary matroids and local complementation
• Circle graph obstructions
• Interlace polynomials for multimatroids and delta-matroids
• Interlacement in 4-regular graphs: a new approach using nonsymmetric matrices
• Isotropic matroids. I: Multimatroids and neighborhoods
• Isotropic matroids. II: Circle graphs
• Isotropic matroids. III: Connectivity
• Multimatroids I. Coverings by Independent Sets
• Multimatroids. II: Orthogonality, minors and connectivity
• Multimatroids. III: Tightness and fundamental graphs
• Multimatroids. IV: Chain-group representations
• Naji's characterization of circle graphs
• Notes on a theorem of Naji
• On a formula for the number of Euler trails for a class of digraphs
• On the number of Euler trails in directed graphs
• Orienting transversals and transition polynomials of multimatroids
• Practical and efficient circle graph recognition
• Recognition of Circle Graphs
• Reconnaissance des graphes de cordes
• The transition matroid of a 4-regular graph: an introduction
• Unimodularity and circle graphs

Cited In (7)

• Naji's characterization of circle graphs
• A characterization of circle graphs in terms of total unimodularity
• Title not available (Why is that?)
• A circle criterion for a generalized cross graph in terms of minimal excluded minors
• 2-nested matrices: towards understanding the structure of circle graphs
• Isotropic matroids. II: Circle graphs
• Isotropic matroids. I: Multimatroids and neighborhoods

This page was built for publication: A characterization of circle graphs in terms of multimatroid representations

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