Zobrazeno 1 - 10
of 150
pro vyhledávání: '"Przybylo, Jakub"'
Autor:
Kamyczura, Mateusz, Przybyło, Jakub
Let $G$ be a graph of maximum degree $\Delta$ which does not contain isolated vertices. An edge coloring $c$ of $G$ is called conflict-free if each edge's closed neighborhood includes a uniquely colored element. The least number of colors admitting s
Externí odkaz:
http://arxiv.org/abs/2409.00759
We show that every cubic graph on $n$ vertices contains a spanning subgraph in which the number of vertices of each degree deviates from $\frac{n}{4}$ by at most $\frac{1}{2}$, up to three exceptions. This resolves the conjecture of Alon and Wei (Irr
Externí odkaz:
http://arxiv.org/abs/2408.16121
Autor:
Dębski, Michał, Grytczuk, Jarosław, Pawlik, Bartłomiej, Przybyło, Jakub, Śleszyńska-Nowak, Małgorzata
A \emph{tangram} is a word in which every letter occurs an even number of times. Such word can be cut into parts that can be arranged into two identical words. The minimum number of cuts needed is called the \emph{cut number} of a tangram. For exampl
Externí odkaz:
http://arxiv.org/abs/2407.03819
Autor:
Przybyło, Jakub
The irregularity strength of a graph $G$, $s(G)$, is the least $k$ such that there exists a $\{1,2,\ldots,k\}$-weighting of the edges of $G$ attributing distinct weighted degrees to all vertices, or equivalently the least $k$ enabling obtaining a mul
Externí odkaz:
http://arxiv.org/abs/2406.09584
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:
Przybyło, Jakub
A locally irregular graph is a graph whose adjacent vertices have distinct degrees. It was conjectured that every connected graph is edge decomposable to $3$ locally irregular subgraphs, unless it belongs to a certain family of exceptions, including
Externí odkaz:
http://arxiv.org/abs/2402.18739
Autor:
Pękała, Paweł, Przybyło, Jakub
A $\frac{1}{k}$-majority $l$-edge-colouring of a graph $G$ is a colouring of its edges with $l$ colours such that for every colour $i$ and each vertex $v$ of $G$, at most $\frac{1}{k}$'th of the edges incident with $v$ have colour $i$. We conjecture
Externí odkaz:
http://arxiv.org/abs/2309.16624
Autor:
Kamyczura, Mateusz, Przybyło, Jakub
A proper vertex colouring of a graph $G$ is referred to as conflict-free if in the neighbourhood of every vertex some colour appears exactly once, while it is called $h$-conflict-free if there are at least $h$ such colours for each vertex of $G$. The
Externí odkaz:
http://arxiv.org/abs/2212.08936
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
