Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the size of $(K_t, K_{1,k})$-co-critical graphs
68
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Given graphs $G, H_1, H_2$, we write $G rightarrow ({H}_1, H_2)$ if every ${$red, blue$}$-coloring of the edges of $G$ contains a red copy of $H_1$ or a blue copy of $H_2$. A non-complete graph $G$ is $(H_1, H_2)$-co-critical if $G rightarrow ({H}_1, H_2)$, but $G+erightarrow ({H}_1, H_2)$ for every edge $e$ in $overline{G}$. Motivated by a conjecture of Hanson and Toft from 1987, we study the minimum number of edges over all $(K_t, K_{1,k})$-co-critical graphs on $n$ vertices. We prove that for all $tge3$ and $kge 3$, there exists a constant $ell(t, k)$ such that, for all $n ge (t-1)k+1$, if $G$ is a $(K_t, K_{1,k})$-co-critical graph on $n$ vertices, then $$ e(G)ge left(2t-4+frac{k-1}{2}right)n-ell(t, k).$$ Furthermore, this linear bound is asymptotically best possible when $tin{3, 4,5}$ and all $kge3$ and $nge (2t-2)k+1$. It seems non-trivial to construct extremal $(K_t, K_{1,k})$-co-critical graphs for $tge6$. We also obtain the sharp bound for the size of $(K_3, K_{1,3})$-co-critical graphs on $nge13$ vertices by showing that all such graphs have at least $3n-4$ edges.
rate research
Read More
Given an integer $rge1$ and graphs $G, H_1, ldots, H_r$, we write $G rightarrow ({H}_1, ldots, {H}_r)$ if every $r$-coloring of the edges of $G$ contains a monochromatic copy of $H_i$ in color $i$ for some $iin{1, ldots, r}$. A non-complete graph $G$ is $(H_1, ldots, H_r)$-co-critical if $G rightarrow ({H}_1, ldots, {H}_r)$, but $G+erightarrow ({H}_1, ldots, {H}_r)$ for every edge $e$ in $overline{G}$. In this paper, motivated by Hanson and Tofts conjecture [Edge-colored saturated graphs, J Graph Theory 11(1987), 191--196], we study the minimum number of edges over all $(K_t, mathcal{T}_k)$-co-critical graphs on $n$ vertices, where $mathcal{T}_k$ denotes the family of all trees on $k$ vertices. Following Day [Saturated graphs of prescribed minimum degree, Combin. Probab. Comput. 26 (2017), 201--207], we apply graph bootstrap percolation on a not necessarily $K_t$-saturated graph to prove that for all $tge4 $ and $kge max{6, t}$, there exists a constant $c(t, k)$ such that, for all $n ge (t-1)(k-1)+1$, if $G$ is a $(K_t, mathcal{T}_k)$-co-critical graph on $n$ vertices, then $$ e(G)ge left(frac{4t-9}{2}+frac{1}{2}leftlceil frac{k}{2} rightrceilright)n-c(t, k).$$ Furthermore, this linear bound is asymptotically best possible when $tin{4,5}$ and $kge6$. The method we develop in this paper may shed some light on attacking Hanson and Tofts conjecture.
A well-known theorem of Vizing states that if $G$ is a simple graph with maximum degree $Delta$, then the chromatic index $chi(G)$ of $G$ is $Delta$ or $Delta+1$. A graph $G$ is class 1 if $chi(G)=Delta$, and class 2 if $chi(G)=Delta+1$; $G$ is $Delta$-critical if it is connected, class 2 and $chi(G-e)<chi(G)$ for every $ein E(G)$. A long-standing conjecture of Vizing from 1968 states that every $Delta$-critical graph on $n$ vertices has at least $(n(Delta-1)+ 3)/2$ edges. We initiate the study of determining the minimum number of edges of class 1 graphs $G$, in addition, $chi(G+e)=chi(G)+1$ for every $ein E(overline{G})$. Such graphs have intimate relation to $(P_3; k)$-co-critical graphs, where a non-complete graph $G$ is $(P_3; k)$-co-critical if there exists a $k$-coloring of $E(G)$ such that $G$ does not contain a monochromatic copy of $P_3$ but every $k$-coloring of $E(G+e)$ contains a monochromatic copy of $P_3$ for every $ein E(overline{G})$. We use the bound on the size of the aforementioned class 1 graphs to study the minimum number of edges over all $(P_3; k)$-co-critical graphs. We prove that if $G$ is a $(P_3; k)$-co-critical graph on $nge k+2$ vertices, then [e(G)ge {k over 2}left(n- leftlceil {k over 2} rightrceil - varepsilonright) + {lceil k/2 rceil+varepsilon choose 2},] where $varepsilon$ is the remainder of $n-lceil k/2 rceil $ when divided by $2$. This bound is best possible for all $k ge 1$ and $n ge leftlceil {3k /2} rightrceil +2$.
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.
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.
A graph $G$ is $k$-vertex-critical if $G$ has chromatic number $k$ but every proper induced subgraph of $G$ has chromatic number less than $k$. The study of $k$-vertex-critical graphs for graph classes is an important topic in algorithmic graph theory because if the number of such graphs that are in a given hereditary graph class is finite, then there is a polynomial-time algorithm to decide if a graph in the class is $(k-1)$-colorable. In this paper, we prove that for every fixed integer $kge 1$, there are only finitely many $k$-vertex-critical ($P_5$,gem)-free graphs and $(P_5,overline{P_3+P_2})$-free graphs. To prove the results we use a known structure theorem for ($P_5$,gem)-free graphs combined with properties of $k$-vertex-critical graphs. Moreover, we characterize all $k$-vertex-critical ($P_5$,gem)-free graphs and $(P_5,overline{P_3+P_2})$-free graphs for $k in {4,5}$ using a computer generation algorithm.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
