TY - JOUR
T1 - Tight Descriptions of 3-Paths in Normal Plane Maps
T2 - Dedicated to Andre Raspaud on the occasion of his 70th birthday
AU - Borodin, O. V.
AU - Ivanova, A. O.
AU - Kostochka, A. V.
N1 - Publisher Copyright:
© 2016 Wiley Periodicals, Inc.
PY - 2017/5/1
Y1 - 2017/5/1
N2 - We prove that every normal plane map (NPM) has a path on three vertices (3-path) whose degree sequence is bounded from above by one of the following triplets: (3, 3, ∞), (3,15,3), (3,10,4), (3,8,5), (4,7,4), (5,5,7), (6,5,6), (3,4,11), (4,4,9), and (6,4,7). This description is tight in the sense that no its parameter can be improved and no term dropped. We also pose a problem of describing all tight descriptions of 3-paths in NPMs and make a modest contribution to it by showing that there exist precisely three one-term descriptions: (5, ∞, 6), (5, 10, ∞), and (10, 5, ∞).
AB - We prove that every normal plane map (NPM) has a path on three vertices (3-path) whose degree sequence is bounded from above by one of the following triplets: (3, 3, ∞), (3,15,3), (3,10,4), (3,8,5), (4,7,4), (5,5,7), (6,5,6), (3,4,11), (4,4,9), and (6,4,7). This description is tight in the sense that no its parameter can be improved and no term dropped. We also pose a problem of describing all tight descriptions of 3-paths in NPMs and make a modest contribution to it by showing that there exist precisely three one-term descriptions: (5, ∞, 6), (5, 10, ∞), and (10, 5, ∞).
KW - 3-path
KW - normal plane map
KW - plane graph
KW - structural property
UR - http://www.scopus.com/inward/record.url?scp=84978237208&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84978237208&partnerID=8YFLogxK
U2 - 10.1002/jgt.22051
DO - 10.1002/jgt.22051
M3 - Article
AN - SCOPUS:84978237208
SN - 0364-9024
VL - 85
SP - 115
EP - 132
JO - Journal of Graph Theory
JF - Journal of Graph Theory
IS - 1
ER -