Zobrazeno 1 - 10
of 96
pro vyhledávání: '"Bosek, Bartłomiej"'
Autor:
Bosek, Bartłomiej, Katan, Aleksander
A majority coloring of an undirected graph is a vertex coloring in which for each vertex there are at least as many bi-chromatic edges containing that vertex as monochromatic ones. It is known that for every countable graph a majority 3-coloring alwa
Externí odkaz:
http://arxiv.org/abs/2406.04189
We consider a graph coloring algorithm that processes vertices in order taken uniformly at random and assigns colors to them using First-Fit strategy. We show that this algorithm uses, in expectation, at most $(1 + o(1))\cdot \ln n \,/\, \ln\ln n$ di
Externí odkaz:
http://arxiv.org/abs/2404.17011
Autor:
Anholcer, Marcin, Bosek, Bartłomiej, Grytczuk, Jarosław, Gutowski, Grzegorz, Przybyło, Jakub, Zając, Mariusz
A majority coloring of a directed graph is a vertex coloring in which each vertex has the same color as at most half of its out-neighbors. In this note we simplify some proof techniques and generalize previously known results on various generalizatio
Externí odkaz:
http://arxiv.org/abs/2207.09739
Publikováno v:
In International Review of Financial Analysis October 2024 95 Part B
In this paper we study the problem of coloring a unit interval graph which changes dynamically. In our model the unit intervals are added or removed one at the time, and have to be colored immediately, so that no two overlapping intervals share the s
Externí odkaz:
http://arxiv.org/abs/2202.08006
Autor:
Anholcer, Marcin, Bosek, Bartłomiej, Grytczuk, Jarosław, Gutowski, Grzegorz, Przybyło, Jakub, Pyzik, Rafał, Zając, Mariusz
Let $N$ be a positive integer. A sequence $X=(x_1,x_2,\ldots,x_N)$ of points in the unit interval $[0,1)$ is piercing if $\{x_1,x_2,\ldots,x_n\}\cap \left[\frac{i}{n},\frac{i+1}{n} \right) \neq\emptyset$ holds for every $n=1,2,\ldots, N$ and every $i
Externí odkaz:
http://arxiv.org/abs/2111.01887
Publikováno v:
In European Journal of Combinatorics March 2024 117
Let $\Gamma$ be an Abelian group and let $G$ be a simple graph. We say that $G$ is $\Gamma$-colorable if for some fixed orientation of $G$ and every edge labeling $\ell:E(G)\rightarrow \Gamma$, there exists a vertex coloring $c$ by the elements of $\
Externí odkaz:
http://arxiv.org/abs/2012.03230
Autor:
Bosek, Bartłomiej, Grytczuk, Jarosław
We consider some coloring issues related to the famous Erd\H {o}s Discrepancy Problem. A set of the form $A_{s,k}=\{s,2s,\dots,ks\}$, with $s,k\in \mathbb{N}$, is called a \emph{homogeneous arithmetic progression}. We prove that for every fixed $k$ t
Externí odkaz:
http://arxiv.org/abs/2005.14283
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