A characterization of circle graphs in terms of multimatroid representations

DOI10.37236/6992MaRDI QIDQ2290352zbMATH OpenOpenAlexFDO

Authors Robert Brijder, L. Traldi

Publication date 27 January 2020

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

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1703.05960, https://www.combinatorics.org/ojs/index.php/eljc/article/view/v27i1p25

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

zbMATH Keywords

circle graphdelta-matroidisotropic systemlocal equivalencematroidmultimatroidregularityrepresentationunimodular orientation

Mathematics Subject Classification ID

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

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.

Review text

Summary: 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 \(\neq 2\). 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 \(\mathbb{F} \), there is an \(\mathbb{F} \)-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.

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

Cites work

• 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
• scientific article; zbMATH DE number 3606473 (Why is no real title available?)
• scientific article; zbMATH DE number 5873618 (Why is no real title available?)
• scientific article; zbMATH DE number 3257167 (Why is no real title available?)
• 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

(8)

• A characterization of circle graphs in terms of total unimodularity
• 2-nested matrices: towards understanding the structure of circle graphs
• Naji's characterization of circle graphs
• scientific article; zbMATH DE number 2211935 (Why is no real title available?)
• A circle criterion for a generalized cross graph in terms of minimal excluded minors
• Circuit partitions and signed interlacement in 4-regular graphs
• Isotropic matroids. I: Multimatroids and neighborhoods
• Isotropic matroids. II: Circle graphs

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)