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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom