Source author record

János Barát

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

ResearcherUnclaimed source record

math.CO Computational Geometry Discrete Mathematics

Catalog footprint

Research overview

10works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

The horizon of 2-dichromatic oriented graphs

The dichromatic number of a directed graph is at most 2, if we can 2-color the vertices such that each monochromatic part is acyclic. An oriented graph arises from a graph by orienting its edges in one of the two possible directions. We study oriented graphs, which have dichromatic number more than 2. Such a graph $D$ is $3$ -dicritical if the removal of any arc of $D$ reduces the dichromatic number to 2. We construct infinitely many $3$ -dicritical oriented graphs. Neumann-Lara found the four $7$ -vertex $3$ -dichromatic tournaments. We determine the $8$ -vertex $3$ -dichromatic tournaments, which do not contain any of these, there are $64$ of them. We also find all $3$ -dicritical oriented graphs on $8$ vertices, there are $159$ of them. We determine the smallest number of arcs that a $3$ -dicritical oriented graph can have. There is a unique oriented graph with $7$ vertices and $20$ arcs.

preprint2020arXiv

Improvement on the crossing number of crossing-critical graphs

The crossing number of a graph $G$ is the minimum number of edge crossings over all drawings of $G$ in the plane. A graph $G$ is $k$ -crossing-critical if its crossing number is at least $k$ , but if we remove any edge of $G$ , its crossing number drops below $k$ . There are examples of $k$ -crossing-critical graphs that do not have drawings with exactly $k$ crossings. Richter and Thomassen proved in 1993 that if $G$ is $k$ -crossing-critical, then its crossing number is at most $2.5k+16$ . We improve this bound to $2k+6\sqrt{k}+44$ .

preprint2020arXiv

Intersecting and $2$ -intersecting hypergraphs with maximal covering number: the Erdős-Lovász theme revisited

Erdős and Lovász noticed that an $r$ -uniform intersecting hypergraph $H$ with maximal covering number, that is $τ(H)=r$ , must have at least $\frac{8}{3}r-3$ edges. There has been no improvement on this lower bound for 45 years. We try to understand the reason by studying some small cases to see whether the truth lies very close to this simple bound. Let $q(r)$ denote the minimum number of edges in an intersecting $r$ -uniform hypergraph. It was known that $q(3)=6$ and $q(4)=9$ . We obtain the following new results: The extremal example for uniformity 4 is unique. Somewhat surprisingly it is not symmetric by any means. For uniformity 5, $q(5)=13$ , and we found 3 examples, none of them being some known graph. We use both theoretical arguments and computer searches. In the footsteps of Erdős and Lovász, we also consider the special case, when the hypergraph is part of a finite projective plane. We determine the exact answer for $r\in \{3,4,5,6\}$ . For uniformity 6, there is a unique extremal example. In a related question, we try to find $2$ -intersecting $r$ -uniform hypergraphs with maximal covering number, that is $τ(H)=r-1$ . An infinite family of examples is to take all possible $r$ -sets of a $(2r-2)$ -vertex set. There is also a geometric candidate: biplanes. These are symmetric 2-designs with $λ=2$ . We determined that only 3 biplanes of the 18 known examples are extremal.

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

Improvements on the density of maximal 1-planar graphs

A graph is 1-planar if it can be drawn in the plane such that each edge is crossed at most once. A graph, together with a 1-planar drawing is called 1-plane. Brandenburg et al. showed that there are maximal 1-planar graphs with only $\frac{45}{17}n + O(1)\approx 2.647n$ edges and maximal 1-plane graphs with only $\frac{7}{3}n+O(1)\approx 2.33n$ edges. On the other hand, they showed that a maximal 1-planar graph has at least $\frac{28}{13}n-O(1)\approx 2.15n-O(1)$ edges, and a maximal 1-plane graph has at least $2.1n-O(1)$ edges. We improve both lower bounds to $\frac{20n}{9}\approx 2.22n$ .

preprint2015arXiv

Multipartite hypergraphs achieving equality in Ryser's conjecture

A famous conjecture of Ryser is that in an $r$ -partite hypergraph the covering number is at most $r-1$ times the matching number. If true, this is known to be sharp for $r$ for which there exists a projective plane of order $r-1$ . We show that the conjecture, if true, is also sharp for the smallest previously open value, namely $r=7$ . For $r\in\{6,7\}$ , we find the minimal number $f(r)$ of edges in an intersecting $r$ -partite hypergraph that has covering number at least $r-1$ . We find that $f(r)$ is achieved only by linear hypergraphs for $r\le5$ , but that this is not the case for $r\in\{6,7\}$ . We also improve the general lower bound on $f(r)$ , showing that $f(r)\ge 3.052r+O(1)$ . We show that a stronger form of Ryser's conjecture that was used to prove the $r=3$ case fails for all $r>3$ . We also prove a fractional version of the following stronger form of Ryser's conjecture: in an $r$ -partite hypergraph there exists a set $S$ of size at most $r-1$ , contained either in one side of the hypergraph or in an edge, whose removal reduces the matching number by 1.

preprint2012arXiv

Edge-decomposition of graphs into copies of a tree with four edges

We study edge-decompositions of highly connected graphs into copies of a given tree. In particular we attack the following conjecture by Barát and Thomassen: for each tree $T$ , there exists a natural number $k_T$ such that if $G$ is a $k_T$ -edge-connected graph, and $|E(T)|$ divides $|E(G)|$ , then $E(G)$ has a decomposition into copies of $T$ . As one of our main results it is sufficient to prove the conjecture for bipartite graphs. Let $Y$ be the unique tree with degree sequence $(1,1,1,2,3)$ . We prove that if $G$ is a 191-edge-connected graph of size divisible by 4, then $G$ has a $Y$ -decomposition. This is the first instance of such a theorem, in which the tree is different from a path or a star.

preprint2012arXiv

Empty pentagons in point sets with collinearities

An empty pentagon in a point set P in the plane is a set of five points in P in strictly convex position with no other point of P in their convex hull. We prove that every finite set of at least 328k^2 points in the plane contains an empty pentagon or k collinear points. This is optimal up to a constant factor since the (k-1)x(k-1) grid contains no empty pentagon and no k collinear points. The previous best known bound was doubly exponential.

preprint2011arXiv

Vertex coloring of plane graphs with nonrepetitive boundary paths

A sequence $s_1,s_2,...,s_k,s_1,s_2,...,s_k$ is a repetition. A sequence $S$ is nonrepetitive, if no subsequence of consecutive terms of $S$ form a repetition. Let $G$ be a vertex colored graph. A path of $G$ is nonrepetitive, if the sequence of colors on its vertices is nonrepetitive. If $G$ is a plane graph, then a facial nonrepetitive vertex coloring of $G$ is a vertex coloring such that any facial path is nonrepetitive. Let $π_f(G)$ denote the minimum number of colors of a facial nonrepetitive vertex coloring of $G$ . Jendro\vl and Harant posed a conjecture that $π_f(G)$ can be bounded from above by a constant. We prove that $π_f(G)\le 24$ for any plane graph $G$ .

preprint2010arXiv

Large B_d-free and union-free subfamilies

For a property $Γ$ and a family of sets $\cF$, let $f(\cF,Γ)$ be the size of the largest subfamily of $\cF$ having property $Γ$ . For a positive integer $m$ , let $f(m,Γ)$ be the minimum of $f(\cF,Γ)$ over all families of size $m$ . A family $\cF$ is said to be $B_d$ -free if it has no subfamily $\cF'=\{F_I: I \subseteq [d]\}$ of $2^d$ distinct sets such that for every $I,J \subseteq [d]$ , both $F_I \cup F_J=F_{I \cup J}$ and $F_I \cap F_J = F_{I \cap J}$ hold. A family $\cF$ is $a$ -union free if $F_1\cup ... F_a \neq F_{a+1}$ whenever $F_1,..,F_{a+1}$ are distinct sets in $\FF$. We verify a conjecture of Erd\H os and Shelah that $f(m, B_2\text{\rm -free})=Θ(m^{2/3})$ . We also obtain lower and upper bounds for $f(m, B_d\text{\rm -free})$ and $f(m,a\text{\rm -union free})$ .

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.

János Barát

Research overview

Is this your work?

10 publications

The horizon of 2-dichromatic oriented graphs

Improvement on the crossing number of crossing-critical graphs

Intersecting and $2$ -intersecting hypergraphs with maximal covering number: the Erdős-Lovász theme revisited

Rainbow matchings in bipartite multigraphs

Improvements on the density of maximal 1-planar graphs

Multipartite hypergraphs achieving equality in Ryser's conjecture

Edge-decomposition of graphs into copies of a tree with four edges

Empty pentagons in point sets with collinearities

Vertex coloring of plane graphs with nonrepetitive boundary paths

Large B_d-free and union-free subfamilies

See the researcher in context

Building this map preview

János Barát

Research overview

Is this your work?

10 publications

The horizon of 2-dichromatic oriented graphs

Improvement on the crossing number of crossing-critical graphs

Intersecting and 222-intersecting hypergraphs with maximal covering number: the Erdős-Lovász theme revisited

Rainbow matchings in bipartite multigraphs

Improvements on the density of maximal 1-planar graphs

Multipartite hypergraphs achieving equality in Ryser's conjecture

Edge-decomposition of graphs into copies of a tree with four edges

Empty pentagons in point sets with collinearities

Vertex coloring of plane graphs with nonrepetitive boundary paths

Large B_d-free and union-free subfamilies

See the researcher in context

Building this map preview

Intersecting and $2$ -intersecting hypergraphs with maximal covering number: the Erdős-Lovász theme revisited