Wyniki wyszukiwania

1

An Extension of Kotzig’s Theorem

100%

Aksenov V. A., Borodin O. V., Ivanova A. O.

Discussiones Mathematicae Graph Theory

|

2016

|

tom 36

|

nr 4

889-897

EN

In 1955, Kotzig proved that every 3-connected planar graph has an edge with the degree sum of its end vertices at most 13, which is tight. An edge uv is of type (i, j) if d(u) ≤ i and d(v) ≤ j. Borodin (1991) proved that every normal plane map contains an edge of one of the types (3, 10), (4, 7), or (5, 6), which is tight. Cole, Kowalik, and Škrekovski (2007) deduced from this result by Borodin that Kotzig’s bound of 13 is valid for all planar graphs with minimum degree δ at least 2 in which every d-vertex, d ≥ 12, has at most d − 11 neighbors of degree 2. We give a common extension of the three above results by proving for any integer t ≥ 1 that every plane graph with δ ≥ 2 and no d-vertex, d ≥ 11+t, having more than d − 11 neighbors of degree 2 has an edge of one of the following types: (2, 10+t), (3, 10), (4, 7), or (5, 6), where all parameters are tight.

2

3-Paths in Graphs with Bounded Average Degree

100%

Jendrol′ S., Maceková M., Montassier M., Soták R.

Discussiones Mathematicae Graph Theory

|

2016

|

tom 36

|

nr 2

339-353

EN

In this paper we study the existence of unavoidable paths on three vertices in sparse graphs. A path uvw on three vertices u, v, and w is of type (i, j, k) if the degree of u (respectively v, w) is at most i (respectively j, k). We prove that every graph with minimum degree at least 2 and average degree strictly less than m contains a path of one of the types [...] Moreover, no parameter of this description can be improved.

3

On the Weight of Minor Faces in Triangle-Free 3-Polytopes

88%

Borodin O. V., Ivanova A. O.

Discussiones Mathematicae Graph Theory

|

2016

|

tom 36

|

nr 3

603-619

EN

The weight w(f) of a face f in a 3-polytope is the degree-sum of vertices incident with f. It follows from Lebesgue’s results of 1940 that every triangle-free 3-polytope without 4-faces incident with at least three 3-vertices has a 4-face with w ≤ 21 or a 5-face with w ≤ 17. Here, the bound 17 is sharp, but it was still unknown whether 21 is sharp. The purpose of this paper is to improve this 21 to 20, which is best possible.

Ograniczanie wyników

3 Discussiones Mathematicae Graph Theory

2 Borodin O. V.

2 Ivanova A. O.

1 Aksenov V. A.

1 Jendrol′ S.

1 Maceková M.

1 Montassier M.

1 Soták R.

3 2016

An Extension of Kotzig’s Theorem

3-Paths in Graphs with Bounded Average Degree

On the Weight of Minor Faces in Triangle-Free 3-Polytopes