Source author record

Daniel Gerbner

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

Catalog footprint

Research overview

3works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

Partitioning 2-edge-colored graphs by monochromatic paths and cycles

We present results on partitioning the vertices of $2$ -edge-colored graphs into monochromatic paths and cycles. We prove asymptotically the two-color case of a conjecture of Sárközy: the vertex set of every $2$ -edge-colored graph can be partitioned into at most $2α(G)$ monochromatic cycles, where $α(G)$ denotes the independence number of $G$ . Another direction, emerged recently from a conjecture of Schelp, is to consider colorings of graphs with given minimum degree. We prove that apart from $o(|V(G)|)$ vertices, the vertex set of any $2$ -edge-colored graph $G$ with minimum degree at least $(1+\eps){3|V(G)|\over 4}$ can be covered by the vertices of two vertex disjoint monochromatic cycles of distinct colors. Finally, under the assumption that $\overline{G}$ does not contain a fixed bipartite graph $H$ , we show that in every $2$ -edge-coloring of $G$ , $|V(G)|-c(H)$ vertices can be covered by two vertex disjoint paths of different colors, where $c(H)$ is a constant depending only on $H$ . In particular, we prove that $c(C_4)=1$ , which is best possible.

preprint2013arXiv

Covering Paths for Planar Point Sets

Given $n$ points in the plane, a \emph{covering path} is a polygonal path that visits all the points. If no three points are collinear, every covering path requires at least $n/2$ segments, and $n-1$ straight line segments obviously suffice even if the covering path is required to be noncrossing. We show that every set of $n$ points in the plane admits a (possibly self-crossi ng) covering path consisting of $n/2 +O(n/\log{n})$ straight line segments. If the path is required to be noncrossing, we prove that $(1-\eps)n$ straight line segments suffice for a small constant $\eps>0$, and we exhibit $n$ -element point sets that require at least $5n/9 -O(1)$ segments in every such path. Further, the analogous question for noncrossing \emph{covering trees} is considered and similar bounds are obtained. Finally, it is shown that computing a noncrossing covering path for $n$ points in the plane requires $Ω(n \log{n})$ time in the worst case.

preprint2012arXiv

2-Colored Matchings in a 3-Colored K^{3}_{12}

Let $K_{n}^{r}$ denote the complete $r$ -uniform hypergraph on $n$ vertices. A matching $M$ in a hypergraph is a set of pairwise vertex disjoint edges. Recent Ramsey-type results rely on lemmas about the size of monochromatic matchings. A starting point for this study comes from a well-known result of Alon, Frankl, and Lovász (1986). Our motivation is to find the smallest $n$ such that every $t$ -coloring of $K_{n}^{r}$ contains an $s$ -colored matching of size $k$ . It has been conjectured that in every coloring of the edges of $K_n^r$ with 3 colors there is a 2-colored matching of size at least $k$ provided that $n \geq kr + \lfloor \frac{k-1}{r+1} \rfloor$ . The smallest test case is when $r=3$ and $k=4$ . We prove that in every 3-coloring of the edges of $K_{12}^3$ there is a 2-colored matching of size 4.

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.