RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
 General information Latest issue Archive Impact factor Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Sib. Èlektron. Mat. Izv.: Year: Volume: Issue: Page: Find

 Sib. Èlektron. Mat. Izv., 2018, Volume 15, Pages 1174–1181 (Mi semr986)

Discrete mathematics and mathematical cybernetics

All tight descriptions of $3$-paths in plane graphs with girth at least $9$

V. A. Aksenova, O. V. Borodinb, A. O. Ivanovac

a Novosibirsk National Research University, str. Pirogova, 1, 630090, Novosibirsk, Russia
b Sobolev Institute of Mathematics, pr. Koptyuga, 4, 630090, Novosibirsk, Russia
c Ammosov North-Eastern Federal University, str. Kulakovskogo, 48, 677000, Yakutsk, Russia

Abstract: Lebesgue (1940) proved that every plane graph with minimum degree $\delta$ at least $3$ and girth $g$ at least $5$ has a path on three vertices ($3$-path) of degree $3$ each. A description is tight if no its parameter can be strengthened, and no triplet dropped.
Borodin et al. (2013) gave a tight description of $3$-paths in plane graphs with $\delta\ge3$ and $g\ge3$, and another tight description was given by Borodin, Ivanova and Kostochka in 2017.
Borodin and Ivanova (2015) gave seven tight descriptions of $3$-paths when $\delta\ge3$ and $g\ge4$. Furthermore, they proved that this set of tight descriptions is complete, which was a result of a new type in the structural theory of plane graphs. Also, they characterized (2018) all one-term tight descriptions if $\delta\ge3$ and $g\ge3$. The problem of producing all tight descriptions for $g\ge3$ remains widely open even for $\delta\ge3$.
Recently, several tight descriptions of $3$-paths were obtained for plane graphs with $\delta=2$ and $g\ge4$ by Jendrol', Maceková, Montassier, and Soták, four of which descriptions are for $g\ge9$.
In this paper, we prove ten new tight descriptions of $3$-paths for $\delta=2$ and $g\ge9$ and show that no other tight descriptions exist.

Keywords: plane graph, structure properties, tight description, $3$-path, minimum degree, girth.

 Funding Agency Grant Number Russian Foundation for Basic Research 18-01-00353_a16-01-00499_a Ministry of Education and Science of the Russian Federation 1.7217.2017/6.7 The first author was supported by the Russian Foundation for Basic Research (grant 18-01-00353). The second author was supported by the Russian Foundation for Basic Research (grant 16-01-00499). The third author’s work was performed as a part of government work “Leading researchers on an ongoing basis” (1.7217.2017/6.7).

DOI: https://doi.org/10.17377/semi.2018.15.095

Full text: PDF file (147 kB)
References: PDF file   HTML file

Bibliographic databases:

Document Type: Article
UDC: 519.172.2
MSC: 05C75
Received September 5, 2018, published October 16, 2018
Language: English

Citation: V. A. Aksenov, O. V. Borodin, A. O. Ivanova, “All tight descriptions of $3$-paths in plane graphs with girth at least $9$”, Sib. Èlektron. Mat. Izv., 15 (2018), 1174–1181

Citation in format AMSBIB
\Bibitem{AksBorIva18}
\by V.~A.~Aksenov, O.~V.~Borodin, A.~O.~Ivanova
\paper All tight descriptions of $3$-paths in plane graphs with girth at least~$9$
\jour Sib. \`Elektron. Mat. Izv.
\yr 2018
\vol 15
\pages 1174--1181
\mathnet{http://mi.mathnet.ru/semr986}
\crossref{https://doi.org/10.17377/semi.2018.15.095}