Source author record

Gabor N. Sarkozy

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

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

7works

1topics

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.

preprint2015arXiv

Ramsey number of a connected triangle matching

We determine the $2$ -color Ramsey number of a {\em connected} triangle matching $c(nK_3)$ which is any connected graph containing $n$ vertex disjoint triangles. We obtain that $R(c(nK_3),c(nK_3))=7n-2$ , somewhat larger than in the classical result of Burr, Erd\H os and Spencer for a triangle matching, $R(nK_3,nK_3)=5n$ . The motivation is to determine the Ramsey number $R(C_n^2,C_n^2)$ of the square of a cycle $C_n^2$ . We apply our Ramsey result for connected triangle matchings to show that the Ramsey number of an "almost" square of a cycle $C_n^{2,c}$ (a cycle of length $n$ in which all but at most a constant number $c$ of short diagonals are present) is asymptotic to $7n/3$ .

preprint2014arXiv

A quantitative version of the Blow-up Lemma

In this paper we give a quantitative version of the Blow-up Lemma.

preprint2014arXiv

Monochromatic bounded degree subgraph partitions

Let ${\cal{F}}=\{F_1,F_2,\ldots\}$ be a sequence of graphs such that $F_n$ is a graph on $n$ vertices with maximum degree at most $Δ$ . We show that there exists an absolute constant $C$ such that the vertices of any 2-edge-colored complete graph can be partitioned into at most $2^{CΔ\logΔ}$ vertex disjoint monochromatic copies of graphs from ${\cal{F}}$ . If each $F_n$ is bipartite, then we can improve this bound to $2^{C Δ}$ ; this result is optimal up to the constant $C$ .

preprint2012arXiv

Rainbow matchings and partial transversals of Latin squares

In this paper we consider properly edge-colored graphs, i.e. two edges with the same color cannot share an endpoint, so each color class is a matching. A matching is called \it rainbow \rm if its edges have different colors. The minimum degree of a graph is denoted by $δ(G)$ . We show that properly edge colored graphs $G$ with $|V(G)|\ge 4δ(G)-3$ have rainbow matchings of size $δ(G)$ , this gives the best known estimate to a recent question of Wang. Since one obviously needs at least $2δ(G)$ vertices to guarantee a rainbow matching of size $δ(G)$ , we investigate what happens when $|V(G)|\ge 2δ(G)$ . We show that any properly edge colored graph $G$ with $|V(G)|\ge 2δ$ contains a rainbow matching of size at least $δ- 2δ(G)^{2/3}$ . This result extends (with a weaker error term) the well-known result that a factorization of the complete bipartite graph $K_{n,n}$ has a rainbow matching of size $n-o(n)$ , or equivalently that every Latin square of order $n$ has a partial transversal of size $n-o(n)$ (an asymptotic version of the Ryser - Brualdi conjecture). In this direction we also show that every Latin square of order $n$ has a {\em cycle-free partial transversal} of size $n-o(n)$ .

preprint1996arXiv

An Algorithmic Version of the Blow-up Lemma

Recently we have developed a new method in graph theory based on the Regularity Lemma. The method is applied to find certain spanning subgraphs in dense graphs. The other main general tool of the method, beside the Regularity Lemma, is the so-called Blow-up Lemma. This lemma helps to find bounded degree spanning subgraphs in $\varepsilon$ -regular graphs. Our original proof of the lemma is not algorithmic, it applies probabilistic methods. In this paper we provide an algorithmic version of the Blow-up Lemma. The desired subgraph, for an $n$ -vertex graph, can be found in time $O(nM(n))$ , where $M(n)=O(n^{2.376})$ is the time needed to multiply two $n$ by $n$ matrices with 0,1 entries over the integers. We show that the algorithm can be parallelized and implemented in $NC^5$ .

preprint1996arXiv

On $k$ -ordered Hamiltonian Graphs

A Hamiltonian graph $G$ of order $n$ is $k$ -ordered, $2\leq k \leq n$ , if for every sequence $v_1, v_2, \ldots ,v_k$ of $k$ distinct vertices of $G$ , there exists a Hamiltonian cycle that encounters $v_1, v_2, \ldots , v_k$ in this order. In this paper, answering a question of Ng and Schultz, we give a sharp bound for the minimum degree guaranteeing that a graph is a $k$ -ordered Hamiltonian graph under some mild restrictions. More precisely, we show that there are $\varepsilon, n_0> 0$ such that if $G$ is a graph of order $n\geq n_0$ with minimum degree at least $\lceil \frac{n}{2} \rceil + \lfloor \frac{k}{2} \rfloor - 1$ and $2\leq k \leq \eps n$, then $G$ is a $k$ -ordered Hamiltonian graph. It is also shown that this bound is sharp for every $2\leq k \leq \lfloor \frac{n}{2} \rfloor$ .

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.

Gabor N. Sarkozy

Research overview

Is this your work?

7 publications

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

Ramsey number of a connected triangle matching

A quantitative version of the Blow-up Lemma

Monochromatic bounded degree subgraph partitions

Rainbow matchings and partial transversals of Latin squares

An Algorithmic Version of the Blow-up Lemma

On $k$ -ordered Hamiltonian Graphs

See the researcher in context

Building this map preview

Gabor N. Sarkozy

Research overview

Is this your work?

7 publications

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

Ramsey number of a connected triangle matching

A quantitative version of the Blow-up Lemma

Monochromatic bounded degree subgraph partitions

Rainbow matchings and partial transversals of Latin squares

An Algorithmic Version of the Blow-up Lemma

On kkk-ordered Hamiltonian Graphs

See the researcher in context

Building this map preview

On $k$ -ordered Hamiltonian Graphs