Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMaking $K_{r+1}$-Free Graphs $r$-partite
71
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
The ErdH{o}s-Simonovits stability theorem states that for all epsilon >0 there exists alpha >0 such that if G is a K_{r+1}-free graph on n vertices with e(G) > ex(n,K_{r+1}) - alpha n^2, then one can remove epsilon n^2 edges from G to obtain an r-partite graph. Furedi gave a short proof that one can choose alpha=epsilon. We give a bound for the relationship of alpha and varepsilon which is asymptotically sharp as epsilon to 0.
rate research
Read More
For a graph $H$, a graph $G$ is $H$-saturated if $G$ does not contain $H$ as a subgraph but for any $e in E(overline{G})$, $G+e$ contains $H$. In this note, we prove a sharp lower bound for the number of paths and walks on length $2$ in $n$-vertex $K_{r+1}$-saturated graphs. We then use this bound to give a lower bound on the spectral radii of such graphs which is asymptotically tight for each fixed $r$ and $ntoinfty$.
Write $rholeft( Gright) $ for the spectral radius of a graph $G$ and $S_{n,r}$ for the join $K_{r}veeoverline{K}_{n-r}.$ Let $n>rgeq2$ and $G$ be a $K_{r+1}$-saturated graph of order $n.$ Recently Kim, Kim, Kostochka, and O determined exactly the minimum value of $rholeft( Gright) $ for $r=2$, and found an asymptotically tight bound on $rholeft( Gright) $ for $rgeq3.$ They also conjectured that [ rholeft( Gright) >rholeft( S_{n,r-1}right) , ] unless $G=S_{n,r-1}.$ In this note their conjecture is proved.
Let $K_{m}-H$ be the graph obtained from $K_{m}$ by removing the edges set $E(H)$ of the graph $H$ ($H$ is a subgraph of $K_{m}$). We use the symbol $Z_4$ to denote $K_4-P_2.$ A sequence $S$ is potentially $K_{m}-H$-graphical if it has a realization containing a $K_{m}-H$ as a subgraph. Let $sigma(K_{m}-H, n)$ denote the smallest degree sum such that every $n$-term graphical sequence $S$ with $sigma(S)geq sigma(K_{m}-H, n)$ is potentially $K_{m}-H$-graphical. In this paper, we determine the values of $sigma (K_{r+1}-U, n)$ for $ngeq 5r+18, r+1 geq k geq 7,$ $j geq 6$ where $U$ is a graph on $k$ vertices and $j$ edges which contains a graph $K_3 bigcup P_3$ but not contains a cycle on 4 vertices and not contains $Z_4$. There are a number of graphs on $k$ vertices and $j$ edges which contains a graph $(K_{3} bigcup P_{3})$ but not contains a cycle on 4 vertices and not contains $Z_4$. (for example, $C_3bigcup C_{i_1} bigcup C_{i_2} bigcup >... bigcup C_{i_p}$ $(i_j eq 4, j=2,3,..., p, i_1 geq 5)$, $C_3bigcup P_{i_1} bigcup P_{i_2} bigcup ... bigcup P_{i_p}$ $(i_1 geq 3)$, $C_3bigcup P_{i_1} bigcup C_{i_2} bigcup >... bigcup C_{i_p}$ $(i_j eq 4, j=2,3,..., p, i_1 geq 3)$, etc)
By using the Szemeredi Regularity Lemma, Alon and Sudakov recently extended the classical Andrasfai-Erd~os-Sos theorem to cover general graphs. We prove, without using the Regularity Lemma, that the following stronger statement is true. Given any (r-1)-partite graph H whose smallest part has t vertices, and any fixed c>0, there exists a constant C such that whenever G is an n-vertex graph with minimum degree at least ((3r-4)/(3r-1)+c)n, either G contains H, or we can delete at most Cn^(2-1/t) edges from G to yield an r-partite graph.
For a simple graph $G$, let $chi_f(G)$ be the fractional chromatic number of $G$. In this paper, we aim to establish upper bounds on $chi_f(G)$ for those graphs $G$ with restrictions on the clique number. Namely, we prove that for $Delta geq 4$, if $G$ has maximum degree at most $Delta$ and is $K_{Delta}$-free, then $chi_f(G) leq Delta-tfrac{1}{8}$ unless $G= C^2_8$ or $G = C_5boxtimes K_2$. This im proves the result in [King, Lu, and Peng, SIAM J. Discrete Math., 26(2) (2012), pp. 452-471] for $Delta geq 4$ and the result in [Katherine and King, SIAM J.Discrete Math., 27(2) (2013), pp. 1184-1208] for $Delta in {6,7,8}$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
