Source author record

Andrzej Czygrinow

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

ResearcherUnclaimed source record

math.CO Data Structures and Algorithms Distributed, Parallel, and Cluster Computing

Catalog footprint

Research overview

9works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Distributed distance domination in graphs with no $K_{2,t}$ -minor

We prove that a simple distributed algorithm finds a constant approximation of an optimal distance- $k$ dominating set in graphs with no $K_{2,t}$ -minor. The algorithm runs in a constant number of rounds. We further show how this procedure can be used to give a distributed algorithm which given $ε>0$ and $k,t\in \mathbb{Z}^+$ finds in a graph $G=(V,E)$ with no $K_{2,t}$ -minor a distance- $k$ dominating set of size at most $(1+ε)$ of the optimum. The algorithm runs in $O(\log^*{|V|})$ rounds in the Local model. In particular, both algorithms work in outerplanar graphs.

preprint2021arXiv

On Odd Rainbow Cycles in Edge-Colored Graphs

Let $G = (V, E)$ be an $n$ -vertex edge-colored graph. In 2013, H. Li proved that if every vertex $v \in V$ is incident to at least $(n+1)/2$ distinctly colored edges, then $G$ admits a rainbow triangle. We prove that the same hypothesis ensures a rainbow $\ell$ -cycle $C_{\ell}$ whenever $n \ge 432 \ell$ . This result is sharp for all odd integers $\ell \geq 3$ , and extends earlier work of the authors for when $\ell$ is even.

preprint2016arXiv

Tiling directed graphs with tournaments

The Hajnal--Szemerédi theorem states that for any integer $r \ge 1$ and any multiple $n$ of $r$ , if $G$ is a graph on $n$ vertices and $δ(G) \ge (1 - 1/r)n$ , then $G$ can be partitioned into $n/r$ vertex-disjoint copies of the complete graph on $r$ vertices. We prove a very general analogue of this result for directed graphs: for any integer $r \ge 4$ and any sufficiently large multiple $n$ of $r$ , if $G$ is a directed graph on $n$ vertices and every vertex is incident to at least $2(1 - 1/r)n - 1$ directed edges, then $G$ can be partitioned into $n/r$ vertex-disjoint subgraphs of size $r$ each of which contain every tournament on $r$ vertices. A related Turán-type result is also proven.

preprint2013arXiv

An extension of the Hajnal-Szemeredi theorem to directed graphs

Hajnal and Szemeredi proved that every graph G with |G|=ks and minimum degree at least k(s-1) contains k vertex disjoint s-cliques; moreover this degree bound is optimal. We extend their theorem to directed graphs by showing that every directed graph D with |D|=ks and minimum (total) degree at least 2k(s-1)-1 contains k vertex disjoint transitive tournaments on s vertices. Our result implies the Hajnal-Szemeredi Theorem, and the degree bound is optimal. We also make some conjectures regarding even more general results for multigraphs and partitioning into other tournaments. One of these conjectures is supported by an asymptotic result.

preprint2013arXiv

On directed versions of the Corrádi-Hajnal Corollary

For $k \in \mathbb N$ , Corrádi and Hajnal proved that every graph $G$ on $3k$ vertices with minimum degree $δ(G) \ge 2k$ has a $C_3$ -factor, i.e., a partitioning of the vertex set so that each part induces the 3-cycle $C_3$ . Wang proved that every directed graph $\overrightarrow G$ on $3k$ vertices with minimum total degree $δ_t(\overrightarrow G):=\min_{v\in V}(deg^-(v)+deg^+(v)) \ge 3(3k-1)/2$ has a $\overrightarrow C_3$ -factor, where $\overrightarrow C_3$ is the directed 3-cycle. The degree bound in Wang's result is tight. However, our main result implies that for all integers $a \ge 1$ and $b \ge 0$ with $a+b=k$ , every directed graph $\overrightarrow G$ on $3k$ vertices with minimum total degree $δ_t(\overrightarrow G)\ge 4k-1$ has a factor consisting of $a$ copies of $\overrightarrow T_3$ and $b$ copies of $\overrightarrow C_3$ , where $\overrightarrow T_3$ is the transitive tournament on three vertices. In particular, using $b=0$ , there is a $\overrightarrow T_3$ -factor of $\overrightarrow G$ , and using $a=1$ , it is possible to obtain a $\overrightarrow C_3$ -factor of $\overrightarrow G$ by reversing just one edge of $\overrightarrow G$ . All these results are phrased and proved more generally in terms of undirected multigraphs. We conjecture that every directed graph $\overrightarrow G$ on $3k$ vertices with minimum semidegree $δ_0(\overrightarrow G):=\min_{v\in V}\min(deg^-(v),deg^+(v)) \ge 2k$ has a $\overrightarrow C_3$ -factor, and prove that this is asymptotically correct.

preprint2013arXiv

Tight co-degree condition for the existence of loose Hamilton cycles in 3-graphs

In 2006, Kühn and Osthus showed that if a 3-graph H on n vertices has minimum co-degree at least (1/4 +o(1))n and n is even then H has a loose Hamilton cycle. In this paper, we prove that the minimum co-degree of n/4 suffices. The result is tight.

preprint2013arXiv

Tiling in bipartite graphs with asymmetric minimum degrees

The problem of determining the optimal minimum degree condition for a balanced bipartite graph on 2ms vertices to contain m vertex disjoint copies of K_{s,s} was solved by Zhao. Later Hladký and Schacht, and Czygrinow and DeBiasio determined the optimal minimum degree condition for a balanced bipartite graph on 2m(s+t) vertices to contain m vertex disjoint copies of K_{s,t} for fixed positive integers s<t. For a balanced bipartite graph G[U,V], let δ_U be the minimum degree over all vertices in U and δ_V be the minimum degree over all vertices in V. We consider the problem of determining the optimal value of δ_U+δ_V which guarantees that G can be tiled with K_{s,s}. We show that the optimal value depends on D:=|δ_V-δ_U|. When D is small, we show that δ_U+δ_V\geq n+3s-5 is best possible. As D becomes larger, we show that δ_U+δ_V can be made smaller, but no smaller than n+2s-2s^{1/2}. However, when D=n-C for some constant C, we show that there exist graphs with δ_U+δ_V\geq n+s^{s^{1/3}} which cannot be tiled with K_{s,s}.

preprint2012arXiv

Tiling 3-uniform hypergraphs with K_4^3-2e

Let K_4^3-2e denote the hypergraph consisting of two triples on four points. For an integer n, let t(n, K_4^3-2e) denote the smallest integer d so that every 3-uniform hypergraph G of order n with minimum pair-degree δ_2(G) \geq d contains \floor{n/4} vertex-disjoint copies of K_4^3-2e. Kühn and Osthus proved that t(n, K_4^3-2e) = (1 + o(1))n/4 holds for large integers n. Here, we prove the exact counterpart, that for all sufficiently large integers n divisible by 4, t(n, K_4^3-2e) = n/4 when n/4 is odd, and t(n, K_4^3-2e) = n/4+1 when n/4 is even. A main ingredient in our proof is the recent `absorption technique' of Rödl, Ruciński and Szemerédi.

preprint2011arXiv

A note on bipartite graph tiling

Bipartite graph tiling was studied by Zhao who gave the best possible minimum degree conditions for a balanced bipartite graph on 2ms vertices to contain m vertex disjoint copies of K_{s,s}. Let s<t be fixed positive integers. Hladký and Schacht gave minimum degree conditions for a balanced bipartite graph on 2m(s+t) vertices to contain m vertex disjoint copies of K_{s,t}. Their results were best possible, except in the case when m is odd and t> 2s+1. We give the best possible minimum degree condition in this case.

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.

Andrzej Czygrinow

Research overview

Is this your work?

9 publications

Distributed distance domination in graphs with no $K_{2,t}$ -minor

On Odd Rainbow Cycles in Edge-Colored Graphs

Tiling directed graphs with tournaments

An extension of the Hajnal-Szemeredi theorem to directed graphs

On directed versions of the Corrádi-Hajnal Corollary

Tight co-degree condition for the existence of loose Hamilton cycles in 3-graphs

Tiling in bipartite graphs with asymmetric minimum degrees

Tiling 3-uniform hypergraphs with K_4^3-2e

A note on bipartite graph tiling

See the researcher in context

Building this map preview

Andrzej Czygrinow

Research overview

Is this your work?

9 publications

Distributed distance domination in graphs with no K2,tK_{2,t}K2,t​-minor

On Odd Rainbow Cycles in Edge-Colored Graphs

Tiling directed graphs with tournaments

An extension of the Hajnal-Szemeredi theorem to directed graphs

On directed versions of the Corrádi-Hajnal Corollary

Tight co-degree condition for the existence of loose Hamilton cycles in 3-graphs

Tiling in bipartite graphs with asymmetric minimum degrees

Tiling 3-uniform hypergraphs with K_4^3-2e

A note on bipartite graph tiling

See the researcher in context

Building this map preview

Distributed distance domination in graphs with no $K_{2,t}$ -minor