Zobrazeno 1 - 10
of 86
pro vyhledávání: '"05C20, 05C35"'
Autor:
Stein, Maya, Trujillo-Negrete, Ana
We prove that if $D$ is a digraph of maximum outdegree and indegree at least $k$, and minimum semidegree at least $k/2$ that contains no oriented $4$-cycles, then $D$ contains each oriented tree $T$ with~$k$ arcs. This can be slightly improved if $T$
Externí odkaz:
http://arxiv.org/abs/2411.13483
Autor:
Cochran, Garner, Wang, Zhiyu
Erd\H{o}s, Pach, Pollack, and Tuza [J. Combin. Theory Ser. B, 47(1) (1989), 73--79] proved that the diameter of a connected $n$-vertex graph with minimum degree $\delta$ is at most $\frac{3n}{\delta+1}+O(1)$. The oriented diameter of an undirected gr
Externí odkaz:
http://arxiv.org/abs/2409.06587
Autor:
Stein, Maya, Trujillo-Negrete, Ana
We show that if $D$ is an $n$-vertex digraph with more than $(k-1)n$ arcs that does not contain any of three forbidden digraphs, then $D$ contains every antidirected tree on $k$ arcs. The forbidden digraphs are those orientations of $K_{2, \lceil k/1
Externí odkaz:
http://arxiv.org/abs/2404.10750
Autor:
Spiro, Sam
Given a digraph $D$, we say that a set of vertices $Q\subseteq V(D)$ is a $q$-kernel if $Q$ is an independent set and if every vertex of $D$ can be reached from $Q$ by a path of length at most $q$. In this paper, we initiate the study of several extr
Externí odkaz:
http://arxiv.org/abs/2404.07305
In a rainbow version of the classical Tur\'an problem one considers multiple graphs on a common vertex set, thinking of each graph as edges in a distinct color, and wants to determine the minimum number of edges in each color which guarantees existen
Externí odkaz:
http://arxiv.org/abs/2402.01028
Autor:
Yuster, Raphael
For every fixed $k \ge 4$, it is proved that if an $n$-vertex directed graph has at most $t$ pairwise arc-disjoint directed $k$-cycles, then there exists a set of at most $\frac{2}{3}kt+ o(n^2)$ arcs that meets all directed $k$-cycles and that the se
Externí odkaz:
http://arxiv.org/abs/2312.01901
One of the most fundamental results in graph theory is Mantel's theorem which determines the maximum number of edges in a triangle-free graph of order $n$. Recently a colorful variant of this problem has been solved. In such a variant we consider $c$
Externí odkaz:
http://arxiv.org/abs/2308.01461
Autor:
Grzesik, Andrzej, Jaworska, Justyna, Kielak, Bartłomiej, Novik, Aliaksandra, Ślusarczyk, Tomasz
A classical Tur\'an problem asks for the maximum possible number of edges in a graph of a given order that does not contain a particular graph $H$ as a subgraph. It is well-known that the chromatic number of $H$ is the graph parameter which describes
Externí odkaz:
http://arxiv.org/abs/2305.19959
Autor:
Chen, Bin, Hou, Xinmin
Let $\mathscr{H}$ be a family of digraphs. A digraph $D$ is \emph{$\mathscr{H}$-free} if it contains no isomorphic copy of any member of $\mathscr{H}$. For $k\geq2$, we set $C_{\leq k}=\{C_{2}, C_{3},\ldots,C_{k}\}$, where $C_{\ell}$ is a directed cy
Externí odkaz:
http://arxiv.org/abs/2211.03129
Autor:
Yuster, Raphael
Let $H$ be a directed acyclic graph other than a rooted star. It is known that there are constants $c(H)$ and $C(H)$ such that the following holds for the complete directed graph $D_n$. There are at most $C\log n$ directed acyclic subgraphs of $D_n$
Externí odkaz:
http://arxiv.org/abs/2205.10880