Currently displaying 1 – 11 of 11

Showing per page

Order by Relevance | Title | Year of publication

Short cycles of low weight in normal plane maps with minimum degree 5

Oleg V. BorodinDouglas R. Woodall — 1998

Discussiones Mathematicae Graph Theory

In this note, precise upper bounds are determined for the minimum degree-sum of the vertices of a 4-cycle and a 5-cycle in a plane triangulation with minimum degree 5: w(C₄) ≤ 25 and w(C₅) ≤ 30. These hold because a normal plane map with minimum degree 5 must contain a 4-star with w ( K 1 , 4 ) 30 . These results answer a question posed by Kotzig in 1979 and recent questions of Jendrol’ and Madaras.

2-distance 4-colorability of planar subcubic graphs with girth at least 22

Oleg V. BorodinAnna O. Ivanova — 2012

Discussiones Mathematicae Graph Theory

The trivial lower bound for the 2-distance chromatic number χ₂(G) of any graph G with maximum degree Δ is Δ+1. It is known that χ₂ = Δ+1 if the girth g of G is at least 7 and Δ is large enough. There are graphs with arbitrarily large Δ and g ≤ 6 having χ₂(G) ≥ Δ+2. We prove the 2-distance 4-colorability of planar subcubic graphs with g ≥ 22.

All Tight Descriptions of 3-Stars in 3-Polytopes with Girth 5

Oleg V. BorodinAnna O. Ivanova — 2017

Discussiones Mathematicae Graph Theory

Lebesgue (1940) proved that every 3-polytope P5 of girth 5 has a path of three vertices of degree 3. Madaras (2004) refined this by showing that every P5 has a 3-vertex with two 3-neighbors and the third neighbor of degree at most 4. This description of 3-stars in P5s is tight in the sense that no its parameter can be strengthened due to the dodecahedron combined with the existence of a P5 in which every 3-vertex has a 4-neighbor. We give another tight description of 3-stars in P5s: there is a vertex...

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

Oleg V. BorodinAnna O. Ivanova — 2016

Discussiones Mathematicae Graph Theory

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.

5-Stars of Low Weight in Normal Plane Maps with Minimum Degree 5

Oleg V. BorodinAnna O. IvanovaTommy R. Jensen — 2014

Discussiones Mathematicae Graph Theory

It is known that there are normal plane maps M5 with minimum degree 5 such that the minimum degree-sum w(S5) of 5-stars at 5-vertices is arbitrarily large. In 1940, Lebesgue showed that if an M5 has no 4-stars of cyclic type (5, 6, 6, 5) centered at 5-vertices, then w(S5) ≤ 68. We improve this bound of 68 to 55 and give a construction of a (5, 6, 6, 5)-free M5 with w(S5) = 48

An Extension of Kotzig’s Theorem

Valerii A. AksenovOleg V. BorodinAnna O. Ivanova — 2016

Discussiones Mathematicae Graph Theory

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...

Page 1

Download Results (CSV)