Premium
Tight Descriptions of 3‐Paths in Normal Plane Maps
Author(s) -
Borodin O. V.,
Ivanova A. O.,
Kostochka A. V.
Publication year - 2017
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22051
Subject(s) - mathematics , combinatorics , bounded function , plane (geometry) , term (time) , path (computing) , sequence (biology) , degree (music) , geometry , computer science , mathematical analysis , physics , quantum mechanics , biology , acoustics , genetics , programming language
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, ∞).