A characterization of circle graphs in terms of multimatroid representations. (English) Zbl 1431.05032
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.
MSC:
| 05B35 | Combinatorial aspects of matroids and geometric lattices |
| 52B40 | Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) |
Keywords:
circle graph; multimatroid; delta-matroid; isotropic system; local equivalence; matroid; regularity; representation; unimodular orientationReferences:
| [1] | B.Bollob´as,ModernGraphTheory,Springer-Verlag,NewYork,1998. doi:10.1007/978-1-4612-0619-4 |
| [2] | A. Bouchet,Unimodularity and circle graphs, Discrete Math.66(1987), 203-208. doi:10.1016/0012-365X(87)90132-4 · Zbl 0647.05039 |
| [3] | A. Bouchet,Circle graph obstructions, J. Combin. Theory Ser. B60(1994), 107-144. doi:10.1006/jctb.1994.1008 · Zbl 0793.05116 |
| [4] | A. Bouchet,Multimatroids. I. Coverings by independent sets, SIAM J. Discrete Math. 10(1997), 626-646.doi:10.1137/S0895480193242591 · Zbl 0886.05042 |
| [5] | A. Bouchet,Multimatroids. II. Orthogonality, minors and connectivity, Electron. J. Combin.5(1998), #R8.doi:10.37236/1346 · Zbl 0885.05050 |
| [6] | A. Bouchet,Multimatroids III. Tightness and fundamental graphs,European J. Combin.22(2001), 657-677.doi:10.1006/eujc.2000.0486 · Zbl 0982.05034 |
| [7] | A. Bouchet,Multimatroids. IV. Chain-group representations, Linear Algebra Appl. 277(1998), 271-289.doi:10.1016/S0024-3795(97)10041-6 · Zbl 0932.05019 |
| [8] | R. Brijder,Orienting transversals and transition polynomials for multimatroids, Adv. in Appl. Math.94(2018), 120-155.doi:10.1016/j.aam.2017.07.001 · Zbl 1386.05025 |
| [9] | R.BrijderandH.J.Hoogeboom,Interlacepolynomialsformultimatroidsanddelta-matroids,EuropeanJ.Combin.40(2014),142-167. doi:10.1016/j.ejc.2014.03.005 · Zbl 1300.05051 |
| [10] | R. Brijder and L. Traldi,Isotropic matroids I: Multimatroids and neighborhoods, Electron. J. Combin.23(4) (2016), #P4.1.doi:10.37236/5222 · Zbl 1351.05043 |
| [11] | R. Brijder and L. Traldi,Isotropic matroids II: Circle graphs, Electron. J. Combin. 23(4) (2016), #P4.2.doi:10.37236/5223 · Zbl 1351.05044 |
| [12] | R. Brijder and L. Traldi,Isotropic matroids III: Connectivity, Electron. J. Combin. 24(2) (2017), #P2.49.doi:10.37236/5937 · Zbl 1366.05062 |
| [13] | S. Even and A. Itai,Queues, stacks, and graphs, in:Theory of Machines and Computations(Proc. Internat. Sympos., Technion, Haifa, 1971), pp. 71-86. Academic Press, New York, 1971.doi:10.1016/B978-0-12-417750-5.50011-7 |
| [14] | H. de Fraysseix,A characterization of circle graphs, European J. Combin.5(1984), 223-238.doi:10.1016/S0195-6698(84)80005-0 · Zbl 0551.05056 |
| [15] | E. Gasse,A proof of a circle graph characterization, Discrete Math.173(1997), 223-238.doi:10.1016/S0012-365X(97)00068-X · Zbl 0882.05111 |
| [16] | J. F. Geelen,Matchings, matroids, and unimodular matrices, PhD thesis, University of Waterloo, 1995.https://www.math.uwaterloo.ca/ jfgeelen/Publications/ th.pdf |
| [17] | J. Geelen and E. Lee,Naji’s characterization of circle graphs, J. Graph Theory93 (2020), 21-33.doi:10.1002/jgt.22466 · Zbl 1495.05194 |
| [18] | E. Gioan, C. Paul, M. Tedder and D. Corneil,Practical and efficient circle graph recognition, Algorithmica69(2014), 759-788.doi:10.1007/s00453-013-9745-8 · Zbl 1303.05190 |
| [19] | J. Jonsson,On the number of Euler trails in directed graphs, Math. Scand.90(2002), 191-214.doi:10.7146/math.scand.a-14370 · Zbl 1017.05067 |
| [20] | A. Kotzig,Eulerian lines in finite 4-valent graphs and their transformations, in: Theory of Graphs(Proc. Colloq., Tihany, 1966), Academic Press, New York, 1968, pp. 219-230. · Zbl 0159.54201 |
| [21] | J. Lauri,On a formula for the number of Euler trails for a class of digraphs, Discrete Math.163(1997), 307-312.doi:10.1016/0012-365X(95)00345-W · Zbl 0870.05049 |
| [22] | N. Macris and J. V. Pul´e,An alternative formula for the number of Euler trails for a class of digraphs,DiscreteMath.154(1996),301-305. doi:10.1016/0012-365X(94)00333-E · Zbl 0862.05079 |
| [23] | W. Naji,Graphes de cordes: une caracterisation et ses applications(Th‘ese), Grenoble, 1985. |
| [24] | W. Naji,Reconnaissance des graphes de cordes, Discrete Math.54(1985), 329-337. doi:10.1016/0012-365X(85)90117-7 · Zbl 0567.05033 |
| [25] | J. G. Oxley,Matroid Theory, Second Edition, Oxford Univ. Press, Oxford, 2011. doi:10.1093/acprof:oso/9780198566946.001.0001 · Zbl 1254.05002 |
| [26] | R. C. Read and P. Rosenstiehl,On the Gauss crossing problem, in:Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II, Colloq. Math. Soc. J´anos Bolyai, 18, North-Holland, Amsterdam-New York, 1978, pp. 843-876. · Zbl 0391.05017 |
| [27] | J. Spinrad,Recognition of circle graphs, J. Algorithms16(1994), 264-282. doi:10.1006/jagm.1994.1012 · Zbl 0797.68130 |
| [28] | L. Traldi,Interlacement in 4-regular graphs: a new approach using nonsymmetric matrices, Contrib. Discrete Math.9(2014), 85-97.doi:10.11575/cdm.v9i1.62166. · Zbl 1317.05092 |
| [29] | L. Traldi,Binary matroids and local complementation, European J. Combin.45 (2015), 21-40.doi:10.1016/j.ejc.2014.10.001 · Zbl 1304.05015 |
| [30] | L. Traldi,The transition matroid of a 4-regular graph: an introduction, European J. Combin.50(2015), 180-207.doi:10.1016/j.ejc.2015.03.016 · Zbl 1319.05034 |
| [31] | L. Traldi,Notes on a theorem of Naji, Discrete Math.340(2017), 3217-3234. doi:10.1016/j.disc.2016.07.019 · Zbl 1347.05096 |
| [32] | L. Traldi,Circuit partitions and signed interlacement in 4-regular graphs, [arXiv:1607.04233], 2016. |
| [33] | B. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
