A characterization of circle graphs in terms of multimatroid representations

Abstract: The isotropic matroid

M [I A S (G)]

of a looped simple graph

G

is a binary matroid equivalent to the isotropic system of

G

. In general,

M [I A S (G)]

is not regular, so it cannot be represented over fields of characteristic

e q 2

. The ground set of

M [I A S (G)]

is denoted

W (G)

; it is partitioned into 3-element subsets corresponding to the vertices of

G

. When the rank function of

M [I A S (G)]

is restricted to subtransversals of this partition, the resulting structure is a multimatroid denoted

m a t h c a l Z_{3} (G)

. In this paper we prove that

G

is a circle graph if and only if for every field

m a t h b b F

, there is an

m a t h b b F

-representable matroid with ground set

W (G)

, which defines

m a t h c a l 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.)

Cites Work

Cited In (5)

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