Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA spectral stability theorem for large forbidden graphs
193
0
0.0
(
0
)
Authors
Vladimir Nikiforov
Ask ChatGPT about the research
No Arabic abstract
We extend the classical stability theorem of Erdos and Simonovits in two directions: first, we allow the order of the forbidden graph to grow as log of order of the host graph, and second, our extremal condition is on the spectral radius of the host graph.
rate research
Read More
We extend the classical stability theorem of Erdos and Simonovits for forbidden graphs of logarithmic order.
The vertex arboricity $a(G)$ of a graph $G$ is the minimum $k$ such that $V(G)$ can be partitioned into $k$ sets where each set induces a forest. For a planar graph $G$, it is known that $a(G)leq 3$. In two recent papers, it was proved that planar graphs without $k$-cycles for some $kin{3, 4, 5, 6, 7}$ have vertex arboricity at most 2. For a toroidal graph $G$, it is known that $a(G)leq 4$. Let us consider the following question: do toroidal graphs without $k$-cycles have vertex arboricity at most 2? It was known that the question is true for k=3, and recently, Zhang proved the question is true for $k=5$. Since a complete graph on 5 vertices is a toroidal graph without any $k$-cycles for $kgeq 6$ and has vertex arboricity at least three, the only unknown case was k=4. We solve this case in the affirmative; namely, we show that toroidal graphs without 4-cycles have vertex arboricity at most 2.
We prove a `resilience version of Diracs theorem in the setting of random regular graphs. More precisely, we show that, whenever $d$ is sufficiently large compared to $varepsilon>0$, a.a.s. the following holds: let $G$ be any subgraph of the random $n$-vertex $d$-regular graph $G_{n,d}$ with minimum degree at least $(1/2+varepsilon)d$. Then $G$ is Hamiltonian. This proves a conjecture of Ben-Shimon, Krivelevich and Sudakov. Our result is best possible: firstly, the condition that $d$ is large cannot be omitted, and secondly, the minimum degree bound cannot be improved.
In this paper, we present a spectral sufficient condition for a graph to be Hamilton-connected in terms of signless Laplacian spectral radius with large minimum degree.
All planar graphs are 4-colorable and 5-choosable, while some planar graphs are not 4-choosable. Determining which properties guarantee that a planar graph can be colored using lists of size four has received significant attention. In terms of constraining the structure of the graph, for any $ell in {3,4,5,6,7}$, a planar graph is 4-choosable if it is $ell$-cycle-free. In terms of constraining the list assignment, one refinement of $k$-choosability is choosability with separation. A graph is $(k,s)$-choosable if the graph is colorable from lists of size $k$ where adjacent vertices have at most $s$ common colors in their lists. Every planar graph is $(4,1)$-choosable, but there exist planar graphs that are not $(4,3)$-choosable. It is an open question whether planar graphs are always $(4,2)$-choosable. A chorded $ell$-cycle is an $ell$-cycle with one additional edge. We demonstrate for each $ell in {5,6,7}$ that a planar graph is $(4,2)$-choosable if it does not contain chorded $ell$-cycles.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
