Every 3-polytope with minimum degree 5 has a 6-cycle with maximum degree at most 11

O. V. Borodin; A. O. Ivanova; A. V. Kostochka

doi:10.1016/j.disc.2013.10.021

Every 3-polytope with minimum degree 5 has a 6-cycle with maximum degree at most 11

O. V. Borodin, A. O. Ivanova, A. V. Kostochka

Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

Let ^φP(^C6) (respectively, ^φT( ^C6)) be the minimum integer k with the property that every 3-polytope (respectively, every plane triangulation) with minimum degree 5 has a 6-cycle with all vertices of degree at most k. In 1999, S. Jendrol' and T. Madaras proved that 10≤^φT(^C6)≤11. It is also known, due to B. Mohar, R. Škrekovski and H.-J. Voss (2003), that ^φP(^C6)≤107. We prove that ^φP( ^C6)=^φT(^C6)=11.

Original language	English (US)
Pages (from-to)	128-134
Number of pages	7
Journal	Discrete Mathematics
Volume	315-316
Issue number	1
DOIs	https://doi.org/10.1016/j.disc.2013.10.021
State	Published - 2014

Keywords

3-polytope
Planar graph
Plane map
Structure properties
Weight

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Online availability

10.1016/j.disc.2013.10.021

Library availability

Discover UIUC Full Text

Cite this

@article{aaacedc466d24820a72a2187955708c2,

title = "Every 3-polytope with minimum degree 5 has a 6-cycle with maximum degree at most 11",

abstract = "Let φP(C6) (respectively, φT( C6)) be the minimum integer k with the property that every 3-polytope (respectively, every plane triangulation) with minimum degree 5 has a 6-cycle with all vertices of degree at most k. In 1999, S. Jendrol' and T. Madaras proved that 10≤φT(C6)≤11. It is also known, due to B. Mohar, R. {\v S}krekovski and H.-J. Voss (2003), that φP(C6)≤107. We prove that φP( C6)=φT(C6)=11.",

keywords = "3-polytope, Planar graph, Plane map, Structure properties, Weight",

author = "Borodin, {O. V.} and Ivanova, {A. O.} and Kostochka, {A. V.}",

note = "Funding Information: The first author{\textquoteright}s work was supported by grants 12-01-00631 and 12-01-00448 from the Russian Foundation for Basic Research . The second author was supported by grants 12-01-00448 and 12-01-98510 from the Russian Foundation for Basic Research. The research of the third author was supported in part by NSF grant DMS-1266016 . ",

year = "2014",

doi = "10.1016/j.disc.2013.10.021",

language = "English (US)",

volume = "315-316",

pages = "128--134",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - Every 3-polytope with minimum degree 5 has a 6-cycle with maximum degree at most 11

AU - Borodin, O. V.

AU - Ivanova, A. O.

AU - Kostochka, A. V.

N1 - Funding Information: The first author’s work was supported by grants 12-01-00631 and 12-01-00448 from the Russian Foundation for Basic Research . The second author was supported by grants 12-01-00448 and 12-01-98510 from the Russian Foundation for Basic Research. The research of the third author was supported in part by NSF grant DMS-1266016 .

PY - 2014

Y1 - 2014

N2 - Let φP(C6) (respectively, φT( C6)) be the minimum integer k with the property that every 3-polytope (respectively, every plane triangulation) with minimum degree 5 has a 6-cycle with all vertices of degree at most k. In 1999, S. Jendrol' and T. Madaras proved that 10≤φT(C6)≤11. It is also known, due to B. Mohar, R. Škrekovski and H.-J. Voss (2003), that φP(C6)≤107. We prove that φP( C6)=φT(C6)=11.

AB - Let φP(C6) (respectively, φT( C6)) be the minimum integer k with the property that every 3-polytope (respectively, every plane triangulation) with minimum degree 5 has a 6-cycle with all vertices of degree at most k. In 1999, S. Jendrol' and T. Madaras proved that 10≤φT(C6)≤11. It is also known, due to B. Mohar, R. Škrekovski and H.-J. Voss (2003), that φP(C6)≤107. We prove that φP( C6)=φT(C6)=11.

KW - 3-polytope

KW - Planar graph

KW - Plane map

KW - Structure properties

KW - Weight

UR - http://www.scopus.com/inward/record.url?scp=84887843276&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84887843276&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2013.10.021

DO - 10.1016/j.disc.2013.10.021

M3 - Article

AN - SCOPUS:84887843276

SN - 0012-365X

VL - 315-316

SP - 128

EP - 134

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1

ER -

Every 3-polytope with minimum degree 5 has a 6-cycle with maximum degree at most 11

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this