Zobrazeno 1 - 10
of 60
pro vyhledávání: '"Bradač, Domagoj"'
Autor:
Bradač, Domagoj, Christoph, Micha
A folklore result attributed to P\'olya states that there are $(1 + o(1))2^{\binom{n}{2}}/n!$ non-isomorphic graphs on $n$ vertices. Given two graphs $G$ and $H$, we say that $G$ is a unique subgraph of $H$ if $H$ contains exactly one subgraph isomor
Externí odkaz:
http://arxiv.org/abs/2410.16233
A well-known theorem of Nikiforov asserts that any graph with a positive $K_{r}$-density contains a logarithmic blowup of $K_r$. In this paper, we explore variants of Nikiforov's result in the following form. Given $r,t\in\mathbb{N}$, when a positive
Externí odkaz:
http://arxiv.org/abs/2410.07098
Autor:
Bradač, Domagoj
Answering a question of Erd\H{o}s and Ne\v{s}et\v{r}il, we show that the maximum number of inclusion-wise minimal vertex cuts in a graph on $n$ vertices is at most $1.8899^n$ for large enough $n$.
Externí odkaz:
http://arxiv.org/abs/2409.02974
A graph $G$ is said to be $p$-locally dense if every induced subgraph of $G$ with linearly many vertices has edge density at least $p$. A famous conjecture of Kohayakawa, Nagle, R\"odl, and Schacht predicts that locally dense graphs have, asymptotica
Externí odkaz:
http://arxiv.org/abs/2406.12418
The $q$-color Ramsey number of a $k$-uniform hypergraph $G,$ denoted $r(G;q)$, is the minimum integer $N$ such that any coloring of the edges of the complete $k$-uniform hypergraph on $N$ vertices contains a monochromatic copy of $G$. The study of th
Externí odkaz:
http://arxiv.org/abs/2312.13965
In 1975, Erd\H{o}s asked the following natural question: What is the maximum number of edges that an $n$-vertex graph can have without containing a cycle with all diagonals? Erd\H{o}s observed that the upper bound $O(n^{5/3})$ holds since the complet
Externí odkaz:
http://arxiv.org/abs/2308.16163
The $q$-color Ramsey number of a $k$-uniform hypergraph $H$ is the minimum integer $N$ such that any $q$-coloring of the complete $k$-uniform hypergraph on $N$ vertices contains a monochromatic copy of $H$. The study of these numbers is one of the ce
Externí odkaz:
http://arxiv.org/abs/2308.10833
The well-known Erd\H{o}s-Hajnal conjecture states that for any graph $F$, there exists $\epsilon>0$ such that every $n$-vertex graph $G$ that contains no induced copy of $F$ has a homogeneous set of size at least $n^{\epsilon}$. We consider a variant
Externí odkaz:
http://arxiv.org/abs/2305.01531
Given a graph $H$, a perfect $H$-factor in a graph $G$ is a collection of vertex-disjoint copies of $H$ spanning $G$. K\"uhn and Osthus showed that the minimum degree threshold for a graph $G$ to contain a perfect $H$-factor is either given by $1-1/\
Externí odkaz:
http://arxiv.org/abs/2302.13780
We study extensions of Tur\'an Theorem in edge-weighted settings. A particular case of interest is when constraints on the weight of an edge come from the order of the largest clique containing it. These problems are motivated by Ramsey-Tur\'an type
Externí odkaz:
http://arxiv.org/abs/2302.07859