EUDML

Currently displaying 1 – 12 of 12

Order by Relevance | Title | Year of publication

A theorem on nonexistence of a certain type of nearly regular cell-decompositions of the sphere

Mirko Horňák — 1978

Časopis pro pěstování matematiky

Unavoidable set of face types for planar maps

Mirko Horňák; Stanislav 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.

Localization of jumps of the point-distinguishing chromatic index of $K_{n, n}$

Mirko Horňák; Roman Soták — 1997

Discussiones Mathematicae Graph Theory

The point-distinguishing chromatic index of a graph represents the minimum number of colours in its edge colouring such that each vertex is distinguished by the set of colours of edges incident with it. Asymptotic information on jumps of the point-distinguishing chromatic index of $K_{n, n}$ is found.

On-line ranking number for cycles and paths

Erik Bruoth; Mirko 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} \times 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 \leq 24$ .

Decomposition of complete bipartite even graphs into closed trails

Mirko Horňák; Mariusz Woźniak — 2003

Czechoslovak Mathematical Journal

We prove that any complete bipartite graph $K_{a, b}$ , where $a, b$ are even integers, can be decomposed into closed trails with prescribed even lengths.

Nearly regular cell-decompositions of orientable 2-manifolds with at most two exceptional cells

Mirko Horňák; Ernest Jucovič — 1977

Mathematica Slovaca

Životné jubileum profesora Ernesta Jucoviča

Mirko Horňák; Stanislav Jendroľ — 1986

Mathematica Slovaca

Decomposition of bipartite graphs into closed trails

Sylwia Cichacz; Mirko 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}, \dots, t_{p})$ of elements of $Lct (G)$ adding up to $| E (G) |$ is $G$ -realisable provided there is a sequence $(T_{1}, \dots, T_{p})$ of pairwise edge-disjoint closed trails in $G$ such that $T_{i}$ is of length $t_{i}$ for $i = 1, \dots, 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 \geq 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ňák; Stanislav 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...