Wyniki wyszukiwania

1

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

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

100%

Borodin O., Woodall D.

Discussiones Mathematicae Graph Theory

|

1998

|

tom 18

|

nr 2

159-164

EN

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

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

100%

Borodin O., Ivanova A.

Discussiones Mathematicae Graph Theory

|

2012

|

tom 32

|

nr 1

141-151

EN

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.

3

Decompositions of quadrangle-free planar graphs

81%

Borodin O., Ivanova A., Kostochka A., Sheikh N.

Discussiones Mathematicae Graph Theory

|

2009

|

tom 29

|

nr 1

87-99

EN

W. He et al. showed that a planar graph not containing 4-cycles can be decomposed into a forest and a graph with maximum degree at most 7. This degree restriction was improved to 6 by Borodin et al. We further lower this bound to 5 and show that it cannot be improved to 3.

Ograniczanie wyników

3 Discussiones Mathematicae Graph Theory

3 Borodin O.

2 Ivanova A.

1 Kostochka A.

1 Sheikh N.

1 Woodall D.

1 2012

1 2009

1 1998

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

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

Decompositions of quadrangle-free planar graphs