Zobrazeno 1 - 10
of 122
pro vyhledávání: '"Lonc, Zbigniew"'
For graphs $G$ and $H$, an $H$-coloring of $G$ is an edge-preserving mapping from $V(G)$ to $V(H)$. In the $H$-Coloring problem the graph $H$ is fixed and we ask whether an instance graph $G$ admits an $H$-coloring. A generalization of this problem i
Externí odkaz:
http://arxiv.org/abs/2205.13270
A famous theorem of Dilworth asserts that any finite poset of width $k$ can be decomposed into $k$ chains. We study the following problem: given a Borel poset $P$ of finite width $k$, is it true that it can be decomposed into $k$ Borel chains? We giv
Externí odkaz:
http://arxiv.org/abs/2004.02162
Autor:
Lonc, Zbigniew, Truszczynski, Miroslaw
The problem of fair division of indivisible goods is a fundamental problem of social choice. Recently, the problem was extended to the case when goods form a graph and the goal is to allocate goods to agents so that each agent's bundle forms a connec
Externí odkaz:
http://arxiv.org/abs/1905.03038
Autor:
Lonc, Zbigniew, Petryshyn, Nataliya
Publikováno v:
In Discrete Mathematics December 2022 345(12)
Publikováno v:
Discrete Applied Mathematics 225, pp. 51--63. 2017
A \emph{$k$-radius sequence} for a graph $G$ is a sequence of vertices of $G$ (typically with repetitions) such that for every edge $uv$ of $G$ vertices $u$ and $v$ appear at least once within distance $k$ in the sequence. The length of a shortest $k
Externí odkaz:
http://arxiv.org/abs/1711.05091
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol. 19 no. 3, Analysis of Algorithms (September 26, 2017) dmtcs:3755
By a tight tour in a $k$-uniform hypergraph $H$ we mean any sequence of its vertices $(w_0,w_1,\ldots,w_{s-1})$ such that for all $i=0,\ldots,s-1$ the set $e_i=\{w_i,w_{i+1}\ldots,w_{i+k-1}\}$ is an edge of $H$ (where operations on indices are comput
Externí odkaz:
http://arxiv.org/abs/1706.09356
Publikováno v:
In Discrete Applied Mathematics 30 April 2020 277:82-91
Let k be a positive integer. A sequence s over an n-element alphabet A is called a k-radius sequence if every two symbols from A occur in s at distance of at most k. Let f_k(n) denote the length of a shortest k-radius sequence over A. We provide cons
Externí odkaz:
http://arxiv.org/abs/1105.0654
Autor:
Lonc, Zbigniew, Truszczynski, Miroslaw
Let R be an equivalence relation on graphs. By the strengthening of R we mean the relation R' such that graphs G and H are in the relation R' if for every graph F, the union of the graphs G and F is in the relation R with the union of the graphs H an
Externí odkaz:
http://arxiv.org/abs/1002.1749