Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLarge complete minors in expanding graphs
81
0
0.0
(
0
)
Authors
Younjin Kim
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
The Hadwiger number $h(G)$ is the order of the largest complete minor in $G$. Does sufficient Hadwiger number imply a minor with additional properties? In [2], Geelen et al showed $h(G)geq (1+o(1))ctsqrt{ln t}$ implies $G$ has a bipartite subgraph with Hadwiger number at least $t$, for some explicit $csim 1.276dotsc$. We improve this to $h(G) geq (1+o(1))tsqrt{log_2 t}$, and provide a construction showing this is tight. We also derive improved bounds for the topological minor variant of this problem.
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.
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).
The cut-rank of a set $X$ in a graph $G$ is the rank of the $Xtimes (V(G)-X)$ submatrix of the adjacency matrix over the binary field. A split is a partition of the vertex set into two sets $(X,Y)$ such that the cut-rank of $X$ is less than $2$ and both $X$ and $Y$ have at least two vertices. A graph is prime (with respect to the split decomposition) if it is connected and has no splits. A graph $G$ is $k^{+ell}$-rank-connected if for every set $X$ of vertices with the cut-rank less than $k$, $lvert Xrvert$ or $lvert V(G)-Xrvert $ is less than $k+ell$. We prove that every prime $3^{+2}$-rank-connected graph $G$ with at least $10$ vertices has a prime $3^{+3}$-rank-connected pivot-minor $H$ such that $lvert V(H)rvert =lvert V(G)rvert -1$. As a corollary, we show that every excluded pivot-minor for the class of graphs of rank-width at most $k$ has at most $(3.5 cdot 6^{k}-1)/5$ vertices for $kge 2$. We also show that the excluded pivot-minors for the class of graphs of rank-width at most $2$ have at most $16$ vertices.
Total dominator total coloring of a graph is a total coloring of the graph such that each object of the graph is adjacent or incident to every object of some color class. The minimum namber of the color classes of a total dominator total coloring of a graph is called the total dominator total chromatic number of the graph. Here, we will find the total dominator chromatic numbers of wheels, complete bipartite graphs and complete graphs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
