z-logo
open-access-imgOpen Access
All tight descriptions of $3$-paths in plane graphs with girth at least $8$
Author(s) -
O. V. Borodin,
A. O. Ivanova
Publication year - 2020
Publication title -
sibirskie elektronnye matematicheskie izvestiya
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.468
H-Index - 11
ISSN - 1813-3304
DOI - 10.33048/semi.2020.17.030
Subject(s) - girth (graph theory) , combinatorics , plane (geometry) , mathematics , discrete mathematics , computer science , geometry
Lebesgue (1940) proved that every plane graph with minimum degree δ at least 3 and girth g (the length of a shortest cycle) 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 δ ≥ 3 and g ≥ 3, and another tight description was given by Borodin, Ivanova and Kostochka in 2017. In 2015, we gave seven tight descriptions of 3-paths when δ ≥ 3 and g ≥ 4. Furthermore, we 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, we characterized (2018) all one-term tight descriptions if δ ≥ 3 and g ≥ 3. The problem of producing all tight descriptions for g ≥ 3 remains widely open even for δ ≥ 3. Recently, eleven tight descriptions of 3-paths were obtained for plane graphs with δ = 2 and g ≥ 4 by Jendrol’, Maceková, Montassier, and Soták, four of which descriptions are for g ≥ 9. In 2018, Aksenov, Borodin and Ivanova proved nine new tight descriptions of 3-paths for δ = 2 and g ≥ 9 and showed that no other tight descriptions exist. The purpose of this note is to give a complete list of tight descriptions of 3-paths in the plane graphs with δ = 2 and g ≥ 8.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here
Accelerating Research

Address

John Eccles House
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom