Currently displaying 1 – 12 of 12

Showing per page

Order by Relevance | Title | Year of publication

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-line ranking number for cycles and paths

Erik BruothMirko Horňák — 1999

Discussiones Mathematicae Graph Theory

A k-ranking of a graph G is a colouring φ:V(G) → 1,...,k such that any path in G with endvertices x,y fulfilling φ(x) = φ(y) contains an internal vertex z with φ(z) > φ(x). On-line ranking number χ * r ( G ) of a graph G is a minimum k such that G has a k-ranking constructed step by step if vertices of G are coming and coloured one by one in an arbitrary order; when colouring a vertex, only edges between already present vertices are known. Schiermeyer, Tuza and Voigt proved that χ * r ( P ) < 3 l o g n for n ≥ 2. Here we show...

Achromatic number of K 5 × K n for small n

Mirko HorňákŠtefan Pčola — 2003

Czechoslovak Mathematical Journal

The achromatic number of a graph G is the maximum number of colours in a proper vertex colouring of G such that for any two distinct colours there is an edge of G incident with vertices of those two colours. We determine the achromatic number of the Cartesian product of K 5 and K n for all n 24 .

Decomposition of bipartite graphs into closed trails

Sylwia CichaczMirko Horňák — 2009

Czechoslovak Mathematical Journal

Let Lct ( G ) denote the set of all lengths of closed trails that exist in an even graph G . A sequence ( t 1 , , t p ) of elements of Lct ( G ) adding up to | E ( G ) | is G -realisable provided there is a sequence ( T 1 , , T p ) of pairwise edge-disjoint closed trails in G such that T i is of length t i for i = 1 , , p . The graph G is arbitrarily decomposable into closed trails if all possible sequences are G -realisable. In the paper it is proved that if a 1 is an odd integer and M a , a is a perfect matching in K a , a , then the graph K a , a - M a , a is arbitrarily decomposable into closed...

On Maximum Weight of a Bipartite Graph of Given Order and Size

Mirko HorňákStanislav Jendrol’Ingo Schiermeyer — 2013

Discussiones Mathematicae Graph Theory

The weight of an edge xy of a graph is defined to be the sum of degrees of the vertices x and y. The weight of a graph G is the minimum of weights of edges of G. More than twenty years ago Erd˝os was interested in finding the maximum weight of a graph with n vertices and m edges. This paper presents a complete solution of a modification of the above problem in which a graph is required to be bipartite. It is shown that there is a function w*(n,m) such that the optimum weight is either w*(n,m) or...

Page 1

Download Results (CSV)