Currently displaying 1 – 20 of 37

Showing per page

Order by Relevance | Title | Year of publication

Paths with restricted degrees of their vertices in planar graphs

Stanislav Jendroľ — 1999

Czechoslovak Mathematical Journal

In this paper it is proved that every 3 -connected planar graph contains a path on 3 vertices each of which is of degree at most 15 and a path on 4 vertices each of which has degree at most 23 . Analogous results are stated for 3 -connected planar graphs of minimum degree 4 and 5 . Moreover, for every pair of integers n 3 , k 4 there is a 2 -connected planar graph such that every path on n vertices in it has a vertex of degree k .

A note on face coloring entire weightings of plane graphs

Stanislav JendrolPeter Šugerek — 2014

Discussiones Mathematicae Graph Theory

Given a weighting of all elements of a 2-connected plane graph G = (V,E, F), let f(α) denote the sum of the weights of the edges and vertices incident with the face _ and also the weight of _. Such an entire weighting is a proper face colouring provided that f(α) ≠ f(β) for every two faces α and _ sharing an edge. We show that for every 2-connected plane graph there is a proper face-colouring entire weighting with weights 1 through 4. For some families we improved 4 to 3

Unavoidable set of face types for planar maps

Mirko HorňákStanislav Jendrol — 1996

Discussiones Mathematicae Graph Theory

The type of a face f of a planar map is a sequence of degrees of vertices of f as they are encountered when traversing the boundary of f. A set 𝒯 of face types is found such that in any normal planar map there is a face with type from 𝒯. The set 𝒯 has four infinite series of types as, in a certain sense, the minimum possible number. An analogous result is applied to obtain new upper bounds for the cyclic chromatic number of 3-connected planar maps.

On light subgraphs in plane graphs of minimum degree five

Stanislav Jendrol'Tomáš Madaras — 1996

Discussiones Mathematicae Graph Theory

A subgraph of a plane graph is light if the sum of the degrees of the vertices of the subgraph in the graph is small. It is well known that a plane graph of minimum degree five contains light edges and light triangles. In this paper we show that every plane graph of minimum degree five contains also light stars K 1 , 3 and K 1 , 4 and a light 4-path P₄. The results obtained for K 1 , 3 and P₄ are best possible.

An inequality concerning edges of minor weight in convex 3-polytopes

Igor FabriciStanislav Jendrol' — 1996

Discussiones Mathematicae Graph Theory

Let e i j be the number of edges in a convex 3-polytope joining the vertices of degree i with the vertices of degree j. We prove that for every convex 3-polytope there is 20 e 3 , 3 + 25 e 3 , 4 + 16 e 3 , 5 + 10 e 3 , 6 + 6 [ 2 / 3 ] e 3 , 7 + 5 e 3 , 8 + 2 [ 1 / 2 ] e 3 , 9 + 2 e 3 , 10 + 16 [ 2 / 3 ] e 4 , 4 + 11 e 4 , 5 + 5 e 4 , 6 + 1 [ 2 / 3 ] e 4 , 7 + 5 [ 1 / 3 ] e 5 , 5 + 2 e 5 , 6 120 ; moreover, each coefficient is the best possible. This result brings a final answer to the conjecture raised by B. Grünbaum in 1973.

Colouring vertices of plane graphs under restrictions given by faces

Július CzapStanislav Jendrol' — 2009

Discussiones Mathematicae Graph Theory

We consider a vertex colouring of a connected plane graph G. A colour c is used k times by a face α of G if it appears k times along the facial walk of α. We prove that every connected plane graph with minimum face degree at least 3 has a vertex colouring with four colours such that every face uses some colour an odd number of times. We conjecture that such a colouring can be done using three colours. We prove that this conjecture is true for 2-connected cubic plane graphs. Next we consider other...

Distance coloring of the hexagonal lattice

Peter JackoStanislav Jendrol' — 2005

Discussiones Mathematicae Graph Theory

Motivated by the frequency assignment problem we study the d-distant coloring of the vertices of an infinite plane hexagonal lattice H. Let d be a positive integer. A d-distant coloring of the lattice H is a coloring of the vertices of H such that each pair of vertices distance at most d apart have different colors. The d-distant chromatic number of H, denoted χ d ( H ) , is the minimum number of colors needed for a d-distant coloring of H. We give the exact value of χ d ( H ) for any d odd and estimations for any...

Total edge irregularity strength of trees

Jaroslav IvančoStanislav Jendrol' — 2006

Discussiones Mathematicae Graph Theory

A total edge-irregular k-labelling ξ:V(G)∪ E(G) → {1,2,...,k} of a graph G is a labelling of vertices and edges of G in such a way that for any different edges e and f their weights wt(e) and wt(f) are distinct. The weight wt(e) of an edge e = xy is the sum of the labels of vertices x and y and the label of the edge e. The minimum k for which a graph G has a total edge-irregular k-labelling is called the total edge irregularity strength of G, tes(G). In this paper we prove that for every...

Maximum Edge-Colorings Of Graphs

Stanislav JendrolMichaela Vrbjarová — 2016

Discussiones Mathematicae Graph Theory

An r-maximum k-edge-coloring of G is a k-edge-coloring of G having a property that for every vertex v of degree dG(v) = d, d ≥ r, the maximum color, that is present at vertex v, occurs at v exactly r times. The r-maximum index [...] χr′(G) χ r ' ( G ) is defined to be the minimum number k of colors needed for an r-maximum k-edge-coloring of graph G. In this paper we show that [...] χr′(G)≤3 χ r ' ( G ) 3 for any nontrivial connected graph G and r = 1 or 2. The bound 3 is tight. All graphs G with [...] χ1′(G)=i χ 1 ' ( G ) = i , i...

On rainbowness of semiregular polyhedra

Stanislav JendroľŠtefan Schrötter — 2008

Czechoslovak Mathematical Journal

We introduce the rainbowness of a polyhedron as the minimum number k such that any colouring of vertices of the polyhedron using at least k colours involves a face all vertices of which have different colours. We determine the rainbowness of Platonic solids, prisms, antiprisms and ten Archimedean solids. For the remaining three Archimedean solids this parameter is estimated.

Page 1 Next

Download Results (CSV)