Source author record

Bartłomiej Bosek

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics Data Structures and Algorithms

Catalog footprint

Research overview

7works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Recoloring Unit Interval Graphs with Logarithmic Recourse Budget

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 same color. After each update only a limited number of intervals is allowed to be recolored. The limit on the number of recolorings per update is called the recourse budget. In this paper we show, that if the graph remains $k$ -colorable at all times, and the updates consist of insertions only, then we can achieve the amortized recourse budget of $O(k^7 \log n)$ while maintaining a proper coloring with $k$ colors. This is an exponential improvement over the result in [Bosek et al., Recoloring Interval Graphs with Limited Recourse Budget. SWAT 2020] in terms of both $k$ and $n$ . We complement this result by showing the lower bound of $Ω(n)$ on the amortized recourse budget in the fully dynamic setting. Our incremental algorithm can be efficiently implemented. As a byproduct of independent interest we include a new result on coloring proper circular arc graphs. Let $L$ be the maximum number of arcs intersecting in one point for some set of unit circular arcs $\mathcal{A}$ . We show that if there is a set $\mathcal{A}'$ of non-intersecting unit arcs of size $L^2-1$ such that $\mathcal{A} \cup \mathcal{A}'$ does not contain $L+1$ arcs intersecting in one point, then it is possible to color $\mathcal{A}$ with $L$ colors. This complements the work on unit circular arc coloring, which specifies sufficient conditions needed to color $\mathcal{A}$ with $L+1$ colors or more.

preprint2020arXiv

Dilworth's Theorem for Borel Posets

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 give a positive answer in a special case of Borel posets embeddable into the real line. We also prove a dual theorem for posets whose comparability graphs are locally countable.

preprint2020arXiv

Majority choosability of countable graphs

In any vertex coloring of a graph some edges have differently colored ends (\emph{good} edges) and some are monochromatic (\emph{bad} edges). In a proper coloring all edges are good. In a \emph{majority coloring} it is enough that for every vertex $v$ , the number of bad edges incident to $v$ does not exceed the number of good edges incident to $v$ . A well known result of Lovász \cite{Lovasz} asserts that every finite graph has a majority $2$ -coloring. A similar statement for countably infinite graphs is a challenging open problem, known as the \emph{Unfriendly Partition Conjecture}. We consider a natural list variant of majority coloring. A graph is \emph{majority $k$ -choosable} if it has a majority coloring from any lists of size $k$ assigned arbitrarily to the vertices. We prove that every countable graph is majority $4$ -choosable. We also consider a natural analog of majority coloring for directed graphs. We prove that every countable digraph is also majority $4$ -choosable. We pose list and directed analogs of the Unfriendly Partition Conjecture, stating that every countable graph is majority $2$ -choosable and every countable digraph is majority $3$ -choosable.

preprint2020arXiv

On-line partitioning of width w posets into w^O(log log w) chains

An on-line chain partitioning algorithm receives the elements of a poset one at a time, and when an element is received, irrevocably assigns it to one of the chains. In this paper, we present an on-line algorithm that partitions posets of width $w$ into $w^{O(\log{\log{w}})}$ chains. This improves over previously best known algorithms using $w^{O(\log{w})}$ chains by Bosek and Krawczyk and by Bosek, Kierstead, Krawczyk, Matecki, and Smith. Our algorithm runs in $w^{O(\sqrt{w})}n$ time, where $w$ is the width and $n$ is the size of a presented poset.

preprint2020arXiv

Reflections on the Erd\H {o}s Discrepancy Problem

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$ there exists a $2$ -coloring of $\mathbb N$ such that every set $A_{s,k}$ is \emph{perfectly balanced} (the numbers of red and blue elements in the set $A_{s,k}$ differ by at most one). This prompts reflection on various restricted versions of Erd\H {o}s' problem, obtained by imposing diverse confinements on parameters $s,k$ . In a slightly different direction, we discuss a \emph{majority} variant of the problem, in which each set $A_{s,k}$ should have an excess of elements colored differently than the first element in the set. This problem leads, unexpectedly, to some deep questions concerning completely multiplicative functions with values in $\{+1,-1\}$ . In particular, whether there is such a function with partial sums bounded from above.

preprint2014arXiv

On the Duality of Semiantichains and Unichain Coverings

We study a min-max relation conjectured by Saks and West: For any two posets $P$ and $Q$ the size of a maximum semiantichain and the size of a minimum unichain covering in the product $P\times Q$ are equal. For positive we state conditions on $P$ and $Q$ that imply the min-max relation. Based on these conditions we identify some new families of posets where the conjecture holds and get easy proofs for several instances where the conjecture had been verified before. However, we also have examples showing that in general the min-max relation is false, i.e., we disprove the Saks-West conjecture.

preprint2012arXiv

Additive colorings of planar graphs

An \emph{additive coloring} of a graph $G$ is an assignment of positive integers $\{1,2,...,k\}$ to the vertices of $G$ such that for every two adjacent vertices the sums of numbers assigned to their neighbors are different. The minimum number $k$ for which there exists an additive coloring of $G$ is denoted by $η(G)$ . We prove that $η(G)\leqslant 468$ for every planar graph $G$ . This improves a previous bound $η(G)\leqslant 5544$ due to Norin. The proof uses Combinatorial Nullstellensatz and coloring number of planar hypergrahs. We also demonstrate that $η(G)\leqslant 36$ for 3-colorable planar graphs, and $η(G)\leqslant 4$ for every planar graph of girth at least 13. In a group theoretic version of the problem we show that for each $r\geqslant 2$ there is an $r$ -chromatic graph $G_{r}$ with no additive coloring by elements of any Abelian group of order $r$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Bartłomiej Bosek

Research overview

Is this your work?

7 publications

Recoloring Unit Interval Graphs with Logarithmic Recourse Budget

Dilworth's Theorem for Borel Posets

Majority choosability of countable graphs

On-line partitioning of width w posets into w^O(log log w) chains

Reflections on the Erd\H {o}s Discrepancy Problem

On the Duality of Semiantichains and Unichain Coverings

Additive colorings of planar graphs

See the researcher in context

Building this map preview