Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userBipartite clique minors in graphs of large Hadwiger number
247
0
0.0
(
0
)
Authors
Matthew Wales
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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).
A graph $G$ contains $H$ as an emph{immersion} if there is an injective mapping $phi: V(H)rightarrow V(G)$ such that for each edge $uvin E(H)$, there is a path $P_{uv}$ in $G$ joining vertices $phi(u)$ and $phi(v)$, and all the paths $P_{uv}$, $uvin E(H)$, are pairwise edge-disjoint. An analogue of Hadwigers conjecture for the clique immersions by Lescure and Meyniel states that every graph $G$ contains $K_{chi(G)}$ as an immersion. We consider the average degree condition and prove that for any bipartite graph $H$, every $H$-free graph $G$ with average degree $d$ contains a clique immersion of order $(1-o(1))d$, implying that Lescure and Meyniels conjecture holds asymptotically for graphs without fixed bipartite graph.
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.
Given a graph $G$, the strong clique number of $G$, denoted $omega_S(G)$, is the maximum size of a set $S$ of edges such that every pair of edges in $S$ has distance at most $2$ in the line graph of $G$. As a relaxation of the renowned ErdH{o}s--Nev{s}etv{r}il conjecture regarding the strong chromatic index, Faudree et al. suggested investigating the strong clique number, and conjectured a quadratic upper bound in terms of the maximum degree. Recently, Cames van Batenburg, Kang, and Pirot conjectured a linear upper bound in terms of the maximum degree for graphs without even cycles. Namely, if $G$ is a $C_{2k}$-free graph, then $omega_S(G)leq (2k-1)Delta(G)-{2k-1choose 2}$, and if $G$ is a $C_{2k}$-free bipartite graph, then $omega_S(G)leq kDelta(G)-(k-1)$. We prove the second conjecture in a stronger form, by showing that forbidding all odd cycles is not necessary. To be precise, we show that a ${C_5, C_{2k}}$-free graph $G$ with $Delta(G)ge 1$ satisfies $omega_S(G)leq kDelta(G)-(k-1)$, when either $kgeq 4$ or $kin {2,3}$ and $G$ is also $C_3$-free. Regarding the first conjecture, we prove an upper bound that is off by the constant term. Namely, for $kgeq 3$, we prove that a $C_{2k}$-free graph $G$ with $Delta(G)ge 1$ satisfies $omega_S(G)leq (2k-1)Delta(G)+(2k-1)^2$. This improves some results of Cames van Batenburg, Kang, and Pirot.
Let $q_{min}(G)$ stand for the smallest eigenvalue of the signless Laplacian of a graph $G$ of order $n.$ This paper gives some results on the following extremal problem: How large can $q_minleft( Gright) $ be if $G$ is a graph of order $n,$ with no complete subgraph of order $r+1?$ It is shown that this problem is related to the well-known topic of making graphs bipartite. Using known classical results, several bounds on $q_{min}$ are obtained, thus extending previous work of Brandt for regular graphs. In addition, using graph blowups, a general asymptotic result about the maximum $q_{min}$ is established. As a supporting tool, the spectra of the Laplacian and the signless Laplacian of blowups of graphs are calculated.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
