Tomasz Dzido

Prof. Tomasz Dzido

orcid

Research Focus & Metrics

Academic Career Length

22Years (2005-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
2 January 2015 in The Electronic Journal of Combinatorics
Verified
Journal Article
Open access
PDF file
JCJoanna Cyman
Joanna Cyman
TDTomasz Dzido
Tomasz Dzido
JLJohn Lapinskas
John Lapinskas
ALAllan Lo
Allan Lo
Consider a game played on the edge set of the infinite clique by two players, Builder and Painter. In each round, Builder chooses an edge and Painter colours it red or blue. Builder wins by creating either a red copy of $G$ or a blue copy of $H$ for some fixed graphs $G$ and $H$. The minimum number of rounds within which Builder can win, assuming both players play perfectly, is the on-line Ramsey number $\tilde{r}(G,H)$. In this paper, we consider the case where $G$ is a path $P_k$. We prove that $\tilde{r}(P_3,P_{\ell+1}) = \lceil 5\ell/4\rceil = \tilde{r}(P_3,C_{\ell})$ for all $\ell \ge 5$, and determine $\tilde{r}(P_4,P_{\ell+1})$ up to an additive constant for all $\ell \ge 3$. We also prove some general lower bounds for on-line Ramsey numbers of the form $\tilde{r}(P_{k+1},H)$.

1 April 2018 in Discrete Mathematics
Verified
Journal Article
Closed access
TDTomasz Dzido
Tomasz Dzido
AJAndrzej Jastrzȩbski
Andrzej Jastrzȩbski

8 August 2012 in Graphs and Combinatorics
Verified
Journal Article
Open access
PDF file
TDTomasz Dzido
Tomasz Dzido
The Turán number ex(n, G) is the maximum number of edges in any n-vertex graph that does not contain a subgraph isomorphic to G. We consider a very special case of the Simonovits’s theorem (Simonovits in: Theory of graphs, Academic Press, New York, 1968) which determine an asymptotic result for Turán numbers for graphs with some properties. In the paper we present a more precise result for even wheels. We provide the exact value for Turán number ex(n, W 2k ) for n ≥ 6k − 10 and k ≥ 3. In addition, we show that ${ex(n,W_6)= \lfloor\frac{n^2}{3}\rfloor}$ for all n ≥ 6. These numbers can be useful to calculate some Ramsey numbers.

1 January 2014 in Opuscula Mathematica
Verified
Journal Article
Closed access
JCJoanna Cyman
Joanna Cyman
TDTomasz Dzido
Tomasz Dzido
We consider on-line Ramsey numbers defined by a game played between two players, Builder and Painter. In each round Builder draws an the edge and Painter colors it either red or blue, as it appears. Builder's goal is to force Painter to create a monochromatic copy of a fixed graph \(H\) in as few rounds as possible. The minimum number of rounds (assuming both players play perfectly) is the on-line Ramsey number \(\widetilde{r}(H)\) of the graph \(H\). An asymmetric version of the on-line Ramsey numbers \(\widetilde{r}(G,H)\) is defined accordingly. In 2005, Kurek and Ruciński computed \(\widetilde{r}(C_3)\). In this paper, we compute \(\widetilde{r}(C_4,C_k)\) for \(3 \le k \le 7\). Most of the results are based on computer algorithms but we obtain the exact value \(\widetilde{r}(C_4)\) and do so without the help of computer algorithms.

7 January 2006 in The Electronic Journal of Combinatorics
Verified
Journal Article
Open access
PDF file
TDTomasz Dzido
Tomasz Dzido
MKMarek Kubale
Marek Kubale
KPKonrad Piwakowski
Konrad Piwakowski
For given graphs $G_{1}, G_{2}, ... , G_{k}$, where $k \geq 2$, the multicolor Ramsey number $R(G_{1}, G_{2}, ... , G_{k})$ is the smallest integer $n$ such that if we arbitrarily color the edges of the complete graph on $n$ vertices with $k$ colors, there is always a monochromatic copy of $G_{i}$ colored with $i$, for some $1 \leq i \leq k$. Let $P_k$ (resp. $C_k$) be the path (resp. cycle) on $k$ vertices. In the paper we show that $R(P_3,C_k,C_k)=R(C_k,C_k)=2k-1$ for odd $k$. In addition, we provide the exact values for Ramsey numbers $R(P_{4}, P_{4}, C_{k})=k+2$ and $R(P_{3}, P_{5}, C_{k})=k+1$.

28 February 2013 in Graphs and Combinatorics
Verified
Journal Article
Open access
PDF file
JDJanusz Dybizbański
Janusz Dybizbański
TDTomasz Dzido
Tomasz Dzido
For given graphs G 1 and G 2, the Ramsey number R(G 1, G 2) is the least integer n such that every 2-coloring of the edges of K n contains a subgraph isomorphic to G 1 in the first color or a subgraph isomorphic to G 2 in the second color. Surahmat et al. proved that the Ramsey number \({R(C_4, W_n) \leq n + \lceil (n-1)/3\rceil}\). By using asymptotic methods one can obtain the following property: \({R(C_4, W_n) \leq n + \sqrt{n}+o(1)}\). In this paper we show that in fact \({R(C_4, W_n) \leq n + \sqrt{n-2}+1}\) for n ≥ 11. Moreover, by modification of the Erdős-Rényi graph we obtain an exact value \({R(C_4, W_{q^2+1}) = q^2 + q + 1}\) with q ≥ 4 being a prime power. In addition, we provide exact values for Ramsey numbers R(C 4, W n ) for 14 ≤ n ≤ 17.