Source author record

András Gyárfás

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

11works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

Covering 2-colored complete digraphs by monochromatic $d$ -dominating digraphs

A digraph is {\em $d$ -dominating} if every set of at most $d$ vertices has a common out-neighbor. For all integers $d\geq 2$ , let $f(d)$ be the smallest integer such that the vertices of every 2-edge-colored (finite or infinite) complete digraph (including loops) can be covered by the vertices of at most $f(d)$ monochromatic $d$ -dominating subgraphs. Note that the existence of $f(d)$ is not obvious -- indeed, the question which motivated this paper was simply to determine whether $f(d)$ is bounded, even for $d=2$ . We answer this question affirmatively for all $d\geq 2$ , proving $4\leq f(2)\le 8$ and $2d\leq f(d)\le 2d\left(\frac{d^{d}-1}{d-1}\right)$ for all $d\ge 3$ . We also give an example to show that there is no analogous bound for more than two colors. Our result provides a positive answer to a question regarding an infinite analogue of the Burr-Erdős conjecture on the Ramsey numbers of $d$ -degenerate graphs. Moreover, a special case of our result is related to properties of $d$ -paradoxical tournaments.

preprint2019arXiv

Distribution of colors in Gallai colorings

A Gallai coloring is an edge coloring that avoids triangles colored with three different colors. Given integers $e_1\ge e_2 \ge \dots \ge e_k$ with $\sum_{i=1}^ke_i={n \choose 2}$ for some $n$ , does there exist a Gallai $k$ -coloring of $K_n$ with $e_i$ edges in color $i$ ? In this paper, we give several sufficient conditions and one necessary condition to guarantee a positive answer to the above question. In particular, we prove the existence of a Gallai-coloring if $e_1-e_k\le 1$ and $k \le \lfloor n/2\rfloor$ . We prove that for any integer $k\ge 3$ there is a (unique) integer $g(k)$ with the following property: there exists a Gallai $k$ -coloring of $K_n$ with $e_i$ edges in color $i$ for every $e_1\le\dots \le e_k$ satisfying $\sum_{i=1}^ke_i={n\choose 2}$ , if and only if $n\ge g(k)$ . We show that $g(3)=5$ , $g(4)=8$ , and $2k-2\le g(k)\le 8k^2+1$ for every $k\ge 3$ .

preprint2016arXiv

Covering complete partite hypergraphs by monochromatic components

A well-known special case of a conjecture attributed to Ryser states that k-partite intersecting hypergraphs have transversals of at most k-1 vertices. An equivalent form was formulated by Gyárfás: if the edges of a complete graph K are colored with k colors then the vertex set of K can be covered by at most k-1 sets, each connected in some color. It turned out that the analogue of the conjecture for hypergraphs can be answered: Z. Király proved that in every k-coloring of the edges of the r-uniform complete hypergraph K^r (r >= 3), the vertex set of K^r can be covered by at most $\lceil k/r \rceil$ sets, each connected in some color. Here we investigate the analogue problem for complete r-uniform r-partite hypergraphs. An edge coloring of a hypergraph is called spanning if every vertex is incident to edges of any color used in the coloring. We propose the following analogue of Ryser conjecture. In every spanning (r+t)-coloring of the edges of a complete r-uniform r-partite hypergraph, the vertex set can be covered by at most t+1 sets, each connected in some color. Our main result is that the conjecture is true for 1 <= t <= r-1. We also prove a slightly weaker result for t >= r, namely that t+2 sets, each connected in some color, are enough to cover the vertex set. To build a bridge between complete r-uniform and complete r-uniform r-partite hypergraphs, we introduce a new notion. A hypergraph is complete r-uniform (r,l)-partite if it has all r-sets that intersect each partite class in at most l vertices. Extending our results achieved for l=1, we prove that for any r >= 3, 2 <= l <= r, k >= 1+r-l, in every spanning k-coloring of the edges of a complete r-uniform (r,l)-partite hypergraph, the vertex set can be covered by at most 1+\lfloor \frac{k-r+\ell-1}{\ell}\rfloor sets, each connected in some color.

preprint2016arXiv

Rainbow matchings in bipartite multigraphs

Suppose that $k$ is a non-negative integer and a bipartite multigraph $G$ is the union of $N=\left\lfloor \frac{k+2}{k+1}n\right\rfloor -(k+1)$ matchings $M_1,\dots,M_N$ , each of size $n$ . We show that $G$ has a rainbow matching of size $n-k$ , i.e. a matching of size $n-k$ with all edges coming from different $M_i$ 's. Several choices of parameters relate to known results and conjectures.

preprint2015arXiv

Chromatic Ramsey number of acyclic hypergraphs

Suppose that $T$ is an acyclic $r$ -uniform hypergraph, with $r\ge 2$ . We define the ( $t$ -color) chromatic Ramsey number $χ(T,t)$ as the smallest $m$ with the following property: if the edges of any $m$ -chromatic $r$ -uniform hypergraph are colored with $t$ colors in any manner, there is a monochromatic copy of $T$ . We observe that $χ(T,t)$ is well defined and $\left\lceil {R^r(T,t)-1\over r-1}\right \rceil +1 \le χ(T,t)\le |E(T)|^t+1$ where $R^r(T,t)$ is the $t$ -color Ramsey number of $H$ . We give linear upper bounds for $χ(T,t)$ when T is a matching or star, proving that for $r\ge 2, k\ge 1, t\ge 1$ , $χ(M_k^r,t)\le (t-1)(k-1)+2k$ and $χ(S_k^r,t)\le t(k-1)+2$ where $M_k^r$ and $S_k^r$ are, respectively, the $r$ -uniform matching and star with $k$ edges. The general bounds are improved for $3$ -uniform hypergraphs. We prove that $χ(M_k^3,2)=2k$ , extending a special case of Alon-Frankl-Lovász' theorem. We also prove that $χ(S_2^3,t)\le t+1$ , which is sharp for $t=2,3$ . This is a corollary of a more general result. We define $H^{[1]}$ as the 1-intersection graph of $H$ , whose vertices represent hyperedges and whose edges represent intersections of hyperedges in exactly one vertex. We prove that $χ(H)\le χ(H^{[1]})$ for any $3$ -uniform hypergraph $H$ (assuming $χ(H^{[1]})\ge 2$ ). The proof uses the list coloring version of Brooks' theorem.

preprint2014arXiv

Domination in transitive colorings of tournaments

An edge coloring of a tournament $T$ with colors $1,2,\dots,k$ is called \it $k$ -transitive \rm if the digraph $T(i)$ defined by the edges of color $i$ is transitively oriented for each $1\le i \le k$ . We explore a conjecture of the second author: For each positive integer $k$ there exists a (least) $p(k)$ such that every $k$ -transitive tournament has a dominating set of at most $p(k)$ vertices. We show how this conjecture relates to other conjectures and results. For example, it is a special case of a well-known conjecture of Erd\H os, Sands, Sauer and Woodrow (so the conjecture is interesting even if false). We show that the conjecture implies a stronger conjecture, a possible extension of a result of Bárány and Lehel on covering point sets by boxes. The principle used leads also to an upper bound $O(2^{2^{d-1}}d\log d)$ on the $d$ -dimensional box-cover number that is better than all previous bounds, in a sense close to best possible. We also improve the best bound known in 3-dimensions from $3^{14}$ to 64 and propose possible further improvements through finding the maximum domination number over parity tournaments.

preprint2014arXiv

On $3$ -uniform hypergraphs without linear cycles

We explore properties of $3$ -uniform hypergraphs $H$ without linear cycles. Our main results are that these hypergraphs must contain a vertex of strong degree at most two and must have independent sets of size at least ${2|V(H)|\over 5}$ .

preprint2013arXiv

Coloring 2-intersecting hypergraphs

A hypergraph is 2-intersecting if any two edges intersect in at least two vertices. Blais, Weinstein and Yoshida asked (as a first step to a more general problem) whether every 2-intersecting hypergraph has a vertex coloring with a constant number of colors so that each hyperedge e has at least min{|e|,3} colors. We show that there is such a coloring with at most 5 colors (which is best possible).

preprint2013arXiv

Complements of nearly perfect graphs

A class of graphs closed under taking induced subgraphs is $χ$ -bounded if there exists a function $f$ such that for all graphs $G$ in the class, $χ(G) \leq f(ω(G))$ . We consider the following question initially studied in [A. Gy{á}rf{á}s, Problems from the world surrounding perfect graphs, {\em Zastowania Matematyki Applicationes Mathematicae}, 19:413--441, 1987]. For a $χ$ -bounded class $\cal C$ , is the class $\bar{C}$ $χ$ -bounded (where $\bar{\cal C}$ is the class of graphs formed by the complements of graphs from $\cal C$ )? We show that if $\cal C$ is $χ$ -bounded by the constant function $f(x)=3$ , then $\bar{\cal C}$ is $χ$ -bounded by $g(x)=\lfloor\frac{8}{5}x\rfloor$ and this is best possible. We show that for every constant $c>0$ , if $\cal C$ is $χ$ -bounded by a function $f$ such that $f(x)=x$ for $x \geq c$ , then $\bar{\cal C}$ is $χ$ -bounded. For every $j$ , we construct a class of graphs $χ$ -bounded by $f(x)=x+x/\log^j(x)$ whose complement is not $χ$ -bounded.

preprint2013arXiv

Problems and memories

I state some open problems coming from joint work with Paul Erdős

preprint2010arXiv

Gallai colorings and domination in multipartite digraphs

Assume that D is a digraph without cyclic triangles and its vertices are partitioned into classes A_1,...,A_t of independent vertices. A set $U=\cup_{i\in S} A_i$ is called a dominating set of size |S| if for any vertex $v\in \cup_{i\notin S} A_i$ there is a w in U such that (w,v) is in E(D). Let beta(D) be the cardinality of the largest independent set of D whose vertices are from different partite classes of D. Our main result says that there exists a h=h(beta(D)) such that D has a dominating set of size at most h. This result is applied to settle a problem related to generalized Gallai colorings, edge colorings of graphs without 3-colored triangles.

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.

András Gyárfás

Research overview

Is this your work?

11 publications

Covering 2-colored complete digraphs by monochromatic $d$ -dominating digraphs

Distribution of colors in Gallai colorings

Covering complete partite hypergraphs by monochromatic components

Rainbow matchings in bipartite multigraphs

Chromatic Ramsey number of acyclic hypergraphs

Domination in transitive colorings of tournaments

On $3$ -uniform hypergraphs without linear cycles

Coloring 2-intersecting hypergraphs

Complements of nearly perfect graphs

Problems and memories

Gallai colorings and domination in multipartite digraphs

See the researcher in context

Building this map preview

András Gyárfás

Research overview

Is this your work?

11 publications

Covering 2-colored complete digraphs by monochromatic ddd-dominating digraphs

Distribution of colors in Gallai colorings

Covering complete partite hypergraphs by monochromatic components

Rainbow matchings in bipartite multigraphs

Chromatic Ramsey number of acyclic hypergraphs

Domination in transitive colorings of tournaments

On 333-uniform hypergraphs without linear cycles

Coloring 2-intersecting hypergraphs

Complements of nearly perfect graphs

Problems and memories

Gallai colorings and domination in multipartite digraphs

See the researcher in context

Building this map preview

Covering 2-colored complete digraphs by monochromatic $d$ -dominating digraphs

On $3$ -uniform hypergraphs without linear cycles