اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOn the size of $(K_t,mathcal{T}_k)$-co-critical graphs
79
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
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.
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 $Delt
a$-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$.
Let $G=(V,E)$ be a $tau$-critical graph with $tau(G)=t$. ErdH{o}s and Gallai proved that $|V|leq 2t$ and the bound $|E|leq {t+1choose 2}$ was obtained by ErdH{o}s, Hajnal and Moon. We give here the sharp combined bound $|E|+|V|leq {t+2choose 2}$ and find all graphs with equality.
A graph $G$ is emph{uniquely k-colorable} if the chromatic number of $G$ is $k$ and $G$ has only one $k$-coloring up to permutation of the colors. A uniquely $k$-colorable graph $G$ is edge-critical if $G-e$ is not a uniquely $k$-colorable graph for
any edge $ein E(G)$. Melnikov and Steinberg [L. S. Melnikov, R. Steinberg, One counterexample for two conjectures on three coloring, Discrete Math. 20 (1977) 203-206] asked to find an exact upper bound for the number of edges in a edge-critical 3-colorable planar graph with $n$ vertices. In this paper, we give some properties of edge-critical uniquely 3-colorable planar graphs and prove that if $G$ is such a graph with $n(geq6)$ vertices, then $|E(G)|leq frac{5}{2}n-6 $, which improves the upper bound $frac{8}{3}n-frac{17}{3}$ given by Matsumoto [N. Matsumoto, The size of edge-critical uniquely 3-colorable planar graphs, Electron. J. Combin. 20 (3) (2013) $#$P49]. Furthermore, we find some edge-critical 3-colorable planar graphs which have $n(=10,12, 14)$ vertices and $frac{5}{2}n-7$ edges.
The size-Ramsey number of a graph $F$ is the smallest number of edges in a graph $G$ with the Ramsey property for $F$, that is, with the property that any 2-colouring of the edges of $G$ contains a monochromatic copy of $F$. We prove that the size-Ra
msey number of the grid graph on $ntimes n$ vertices is bounded from above by $n^{3+o(1)}$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
