All tight descriptions of 3-paths in plane graphs with girth at least 9. / Aksenov, Valerii Anatol evich; Borodin, Oleg Veniaminovich; Ivanova, Anna Olegovna.
In: Siberian Electronic Mathematical Reports, Vol. 15, 2018, p. 1174-1181.Research output: Contribution to journal › Article › peer-review
}
TY - JOUR
T1 - All tight descriptions of 3-paths in plane graphs with girth at least 9
AU - Aksenov, Valerii Anatol evich
AU - Borodin, Oleg Veniaminovich
AU - Ivanova, Anna Olegovna
N1 - Publisher Copyright: © 2018 Aksenov V.A., Borodin O.V., Ivanova A.O.
PY - 2018
Y1 - 2018
N2 - Lebesgue (1940) proved that every plane graph with minimum degree δ 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 δ ≥ 3 and g ≥ 3, 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 δ ≥ 3 and g ≥ 4. 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 oneterm tight descriptions if δ ≥ 3 and g ≥ 3. The problem of producing all tight descriptions for g ≥ 3 remains widely open even for δ ≥ 3. Recently, several 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 this paper, we prove ten new tight descriptions of 3-paths for δ = 2 and g ≥ 9 and show that no other tight descriptions exist.
AB - Lebesgue (1940) proved that every plane graph with minimum degree δ 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 δ ≥ 3 and g ≥ 3, 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 δ ≥ 3 and g ≥ 4. 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 oneterm tight descriptions if δ ≥ 3 and g ≥ 3. The problem of producing all tight descriptions for g ≥ 3 remains widely open even for δ ≥ 3. Recently, several 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 this paper, we prove ten new tight descriptions of 3-paths for δ = 2 and g ≥ 9 and show that no other tight descriptions exist.
KW - 3-path
KW - Girth
KW - Minimum degree
KW - Plane graph
KW - Structure properties
KW - Tight description
UR - http://www.scopus.com/inward/record.url?scp=85060142113&partnerID=8YFLogxK
UR - https://elibrary.ru/item.asp?id=36998735
U2 - 10.17377/semi.2018.15.095
DO - 10.17377/semi.2018.15.095
M3 - Article
AN - SCOPUS:85060142113
VL - 15
SP - 1174
EP - 1181
JO - Сибирские электронные математические известия
JF - Сибирские электронные математические известия
SN - 1813-3304
ER -
ID: 41223230