Do you want to publish a course? Click here

Clique immersions and independence number

67   0   0.0 ( 0 )
 Added by Daniel A. Quiroz
 Publication date 2019
  fields
and research's language is English




Ask ChatGPT about the research

The analogue of Hadwigers conjecture for the immersion order states that every graph $G$ contains $K_{chi (G)}$ as an immersion. If true, it would imply that every graph with $n$ vertices and independence number $alpha$ contains $K_{lceil frac nalpharceil}$ as an immersion. The best currently known bound for this conjecture is due to Gauthier, Le and Wollan, who recently proved that every graph $G$ contains an immersion of a clique on $bigllceil frac{chi (G)-4}{3.54}bigrrceil$ vertices. Their result implies that every $n$-vertex graph with independence number $alpha$ contains an immersion of a clique on $bigllceil frac{n}{3.54alpha}-1.13bigrrceil$ vertices. We improve on this result for all $alphage 3$, by showing that every $n$-vertex graph with independence number $alphage 3$ contains an immersion of a clique on $bigllfloor frac {n}{2.25 alpha - f(alpha)} bigrrfloor - 1$ vertices, where $f$ is a nonnegative function.



rate research

Read More

131 - Vladimir Nikiforov 2017
We give some new bounds for the clique and independence numbers of a graph in terms of its eigenvalues.
In this paper, we establish a couple of results on extremal problems in bipartite graphs. Firstly, we show that every sufficiently large bipartite graph with average degree $Delta$ and with $n$ vertices on each side has a balanced independent set containing $(1-epsilon) frac{log Delta}{Delta} n$ vertices from each side for small $epsilon > 0$. Secondly, we prove that the vertex set of every sufficiently large balanced bipartite graph with maximum degree at most $Delta$ can be partitioned into $(1+epsilon)frac{Delta}{log Delta}$ balanced independent sets. Both of these results are algorithmic and best possible up to a factor of 2, which might be hard to improve as evidenced by the phenomenon known as `algorithmic barrier in the literature. The first result improves a recent theorem of Axenovich, Sereni, Snyder, and Weber in a slightly more general setting. The second result improves a theorem of Feige and Kogan about coloring balanced bipartite graphs.
The Ramsey number r(K_s,Q_n) is the smallest positive integer N such that every red-blue colouring of the edges of the complete graph K_N on N vertices contains either a red n-dimensional hypercube, or a blue clique on s vertices. Answering a question of Burr and ErdH{o}s from 1983, and improving on recent results of Conlon, Fox, Lee and Sudakov, and of the current authors, we show that r(K_s,Q_n) = (s-1) (2^n - 1) + 1 for every s in N and every sufficiently large n in N.
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.
185 - Minki Kim , Alan Lew 2019
Let $G=(V,E)$ be a graph and $n$ a positive integer. Let $I_n(G)$ be the abstract simplicial complex whose simplices are the subsets of $V$ that do not contain an independent set of size $n$ in $G$. We study the collapsibility numbers of the complexes $I_n(G)$ for various classes of graphs, focusing on the class of graphs with maximum degree bounded by $Delta$. As an application, we obtain the following result: Let $G$ be a claw-free graph with maximum degree at most $Delta$. Then, every collection of $leftlfloorleft(frac{Delta}{2}+1right)(n-1)rightrfloor+1$ independent sets in $G$ has a rainbow independent set of size $n$.
comments
Fetching comments Fetching comments
Sign in to be able to follow your search criteria
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا