Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userStrong complete minors in digraphs
69
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Kostochka and Thomason independently showed that any graph with average degree $Omega(rsqrt{log r})$ contains a $K_r$ minor. In particular, any graph with chromatic number $Omega(rsqrt{log r})$ contains a $K_r$ minor, a partial result towards Hadwigers famous conjecture. In this paper, we investigate analogues of these results in the directed setting. There are several ways to define a minor in a digraph. One natural way is as follows. A strong $overrightarrow{K}_r$ minor is a digraph whose vertex set is partitioned into $r$ parts such that each part induces a strongly-connected subdigraph, and there is at least one edge in each direction between any two distinct parts. We investigate bounds on the dichromatic number and minimum out-degree of a digraph that force the existence of strong $overrightarrow{K}_r$ minors as subdigraphs. In particular, we show that any tournament with dichromatic number at least $2r$ contains a strong $overrightarrow{K}_r$ minor, and any tournament with minimum out-degree $Omega(rsqrt{log r})$ also contains a strong $overrightarrow{K}_r$ minor. The latter result is tight up to the implied constant, and may be viewed as a strong-minor analogue to the classical result of Kostochka and Thomason. Lastly, we show that there is no function $f: mathbb{N} rightarrow mathbb{N}$ such that any digraph with minimum out-degree at least $f(r)$ contains a strong $overrightarrow{K}_r$ minor, but such a function exists when considering dichromatic number.
rate research
Read More
In 2009, Krivelevich and Sudakov studied the existence of large complete minors in $(t,alpha)$-expanding graphs whenever the expansion factor $t$ becomes super-constant. In this paper, we give an extension of the results of Krivelevich and Sudakov by investigating a connection between the existence of large complete minors in graphs and good vertex expansion properties.
A digraph is {em $d$-dominating} if every set of at most $d$ vertices has a common out-neighbor. For all integers $dgeq 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 $dgeq 2$, proving $4leq f(2)le 8$ and $2dleq f(d)le 2dleft(frac{d^{d}-1}{d-1}right)$ for all $dge 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-ErdH{o}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.
We show that for pairs $(Q,R)$ and $(S,T)$ of disjoint subsets of vertices of a graph $G$, if $G$ is sufficiently large, then there exists a vertex $v$ in $V(G)-(Qcup Rcup Scup T)$ such that there are two ways to reduce $G$ by a vertex-minor operation while preserving the connectivity between $Q$ and $R$ and the connectivity between $S$ and $T$. Our theorem implies an analogous theorem of Chen and Whittle (2014) for matroids restricted to binary matroids.
We prove a conjecture of Fox, Huang, and Lee that characterizes directed graphs that have constant density in all tournaments: they are disjoint unions of trees that are each constructed in a certain recursive way.
A clique minor in a graph G can be thought of as a set of connected subgraphs in G that are pairwise disjoint and pairwise adjacent. The Hadwiger number h(G) is the maximum cardinality of a clique minor in G. This paper studies clique minors in the Cartesian product G*H. Our main result is a rough structural characterisation theorem for Cartesian products with bounded Hadwiger number. It implies that if the product of two sufficiently large graphs has bounded Hadwiger number then it is one of the following graphs: - a planar grid with a vortex of bounded width in the outerface, - a cylindrical grid with a vortex of bounded width in each of the two `big faces, or - a toroidal grid. Motivation for studying the Hadwiger number of a graph includes Hadwigers Conjecture, which states that the chromatic number chi(G) <= h(G). It is open whether Hadwigers Conjecture holds for every Cartesian product. We prove that if |V(H)|-1 >= chi(G) >= chi(H) then Hadwigers Conjecture holds for G*H. On the other hand, we prove that Hadwigers Conjecture holds for all Cartesian products if and only if it holds for all G * K_2. We then show that h(G * K_2) is tied to the treewidth of G. We also develop connections with pseudoachromatic colourings and connected dominating sets that imply near-tight bounds on the Hadwiger number of grid graphs (Cartesian products of paths) and Hamming graphs (Cartesian products of cliques).
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
