Tight Descriptions of 3-Paths in Normal Plane Maps: Dedicated to Andre Raspaud on the occasion of his 70th birthday.

被引：11

作者：

Borodin, O. V. ^{[1
]}

Ivanova, A. O. ^{[2
]}

Kostochka, A. V. ^{[3
]}

机构：

[1] Sobolev Inst Math, Novosibirsk, Russia

[2] Ammosov North Eastern Fed Univ, Yakutsk, Russia

[3] Univ Illinois, Urbana, IL USA

来源：

JOURNAL OF GRAPH THEORY | 2017年 / 85卷 / 01期

基金：

俄罗斯基础研究基金会;

关键词：

plane graph; structural property; normal plane map; 3-path; GRAPHS; VERTICES; GIRTH; PATHS;

D O I：

10.1002/jgt.22051

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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, ). (C) 2016 Wiley Periodicals, Inc.

引用

页码：115 / 132

页数：18

共 23 条

[1] Aksenov V. A., 2015, ELECTRON J COMB, V22, P3
[2] Ando K., 1993, ANN M MATH SOC JAP
[3] JOINT EXTENSION OF 2 THEOREMS OF KOTZIG ON 3-POLYTOPES
BORODIN, O
[J]. COMBINATORICA, 1993, 13 (01) : 121 - 125
[4] Describing tight descriptions of 3-paths in triangle-free normal plane maps
Borodin, O. V.
Ivanova, A. O.
[J]. DISCRETE MATHEMATICS, 2015, 338 (11) : 1947 - 1952
[5] Describing faces in plane triangulations
Borodin, O. V.
Ivanova, A. O.
Kostochka, A. V.
[J]. DISCRETE MATHEMATICS, 2014, 319 : 47 - 61
[6] Describing 3-paths in normal plane maps
Borodin, O. V.
Ivanova, A. O.
Jensen, T. R.
Kostochka, A. V.
Yancey, M. P.
[J]. DISCRETE MATHEMATICS, 2013, 313 (23) : 2702 - 2711
[7] Colorings of plane graphs: A survey
Borodin, O. V.
[J]. DISCRETE MATHEMATICS, 2013, 313 (04) : 517 - 539
[8] Borodin O.V., 1992, MATH SLOVACA, V42, P129
[9] Borodin O.V., 1993, METEM ZAMETKI, V53, P35
[10] Describing (d-2)-stars at d-vertices, d ≤ 5, in normal plane maps
Borodin, Oleg V.
Ivanova, Anna O.
[J]. DISCRETE MATHEMATICS, 2013, 313 (17) : 1700 - 1709

← 1 2 3 →