Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports]
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
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






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports], 2018, Volume 15, Pages 1174–1181
DOI: https://doi.org/10.17377/semi.2018.15.095
(Mi semr986)
 

This article is cited in 2 scientific papers (total in 2 papers)

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
Full-text PDF (147 kB) Citations (2)
References:
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', Maceková, Montassier, and Sotá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_a
16-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).
Received September 5, 2018, published October 16, 2018
Bibliographic databases:
Document Type: Article
UDC: 519.172.2
MSC: 05C75
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. È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}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000454860200037}
Linking options:
  • https://www.mathnet.ru/eng/semr986
  • https://www.mathnet.ru/eng/semr/v15/p1174
  • This publication is cited in the following 2 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Statistics & downloads:
    Abstract page:214
    Full-text PDF :35
    References:31
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024