Email this article A circle criterion for a generalized cross graph in terms of minimal excluded minors
- Authors: Ilyutko V.P.1, Ilyutko D.P.2
-
Affiliations:
- Lomonosov Moscow State University, Faculty of Computational Mathematics and Cybernetics
- Lomonosov Moscow State University, Faculty of Mechanics and Mathematics
- Issue: Vol 213, No 12 (2022)
- Pages: 53-67
- Section: Articles
- URL: https://journals.rcsi.science/0368-8666/article/view/133484
- DOI: https://doi.org/10.4213/sm9670
- ID: 133484
Cite item
Open Access
Access granted
Subscription Access
Abstract
Geelen and Oum described classes of minimal excluded pivot-minors for a simple graph to be a circle graphand for a delta-matroid to be Eulerian. Pivot-equivalence classes of circle simple graphs and delta-matroids arise in the investigation of Eulerian cycles on cross graphs (4-valent graphs with cross structure). The results established by Geelen and Oum rely on some lemmas in their work, which are shown below to be not quite correct.We consider generalized cross graphs, which arise in the description of rotating circuits on cross graphs. For such graphs we derive a circle criterion: we reproduce and augment the arguments due to Geelen and Oum, and we improve some incorrectly formulated statements. As a result, we obtain the same list of 166 inequivalent graphs, the minimal excluded minors for a generalized cross graph to be a circle graph.Bibliography: 14 titles.
About the authors
Viktor Petrovich Ilyutko
Lomonosov Moscow State University, Faculty of Computational Mathematics and Cybernetics
Denis Petrovich Ilyutko
Lomonosov Moscow State University, Faculty of Mechanics and Mathematics
Email: ilyutko@yandex.ru
Candidate of physico-mathematical sciences, Associate professor
References
- N. Robertson, P. D. Seymour, “Graph minors. XX. Wagner's conjecture”, J. Combin. Theory Ser. B, 92:2 (2004), 325–357
- A. Bouchet, “Circle graph obstructions”, J. Combin. Theory Ser. B, 60:1 (1994), 107–144
- V. O. Manturov, “Framed 4-valent graph minor theory. I. Introduction. A planarity criterion and linkless embeddability”, J. Knot Theory Ramifications, 23:7 (2014), 1460002, 8 pp.
- V. O. Manturov, “Framed 4-valent graph minor theory. II. Special minors and new examples”, J. Knot Theory Ramifications, 24:13 (2015), 1541004, 12 pp.
- Д. П. Ильютко, “Оснащенные 4-графы: эйлеровы циклы, гауссовы циклы и поворачивающие обходы”, Матем. сб., 202:9 (2011), 53–76
- D. P. Ilyutko, V. O. Manturov, “Introduction to graph-link theory”, J. Knot Theory Ramifications, 18:6 (2009), 791–823
- I. Nikonov, “A new proof of Vassiliev's conjecture”, J. Knot Theory Ramifications, 23:7 (2014), 1460005, 28 pp.
- В. О. Мантуров, “Доказательство гипотезы В. А. Васильева о планарности сингулярных зацеплений”, Изв. РАН. Сер. матем., 69:5 (2005), 169–178
- R. C. Read, P. Rosenstiehl, “On the Gauss crossing problem”, Combinatorics (Keszthely, 1976), v. II, Colloq. Math. Soc. Janos Bolyai, 18, North-Holland, Amsterdam–New York, 1978, 843–876
- J. Geelen, S. Oum, “Circle graph obstructions under pivoting”, J. Graph Theory, 61:1 (2009), 1–11
- A. Kotzig, “Eulerian lines in finite $4$-valent graphs and their transformations”, Theory of graphs (Tihany, 1966), Academic Press, New York, 1968, 219–230
- V. O. Manturov, D. P. Ilyutko, Virtual knots. The state of the art, Ser. Knots Everything, 51, World Sci. Publ., Hackensack, NJ, 2013, xxvi+521 pp.
- Д. П. Ильютко, В. С. Сафина, “Граф-зацепления: нереализуемость, ориентация и полином Джонса”, Топология, СМФН, 51, РУДН, М., 2013, 33–63
- A. Bouchet, “Graphic presentations of isotropic systems”, J. Combin. Theory Ser. B, 45:1 (1988), 58–76
Supplementary files
