اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدGallai Ramsey number for double stars
375
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Given a graph $G$ and a positive integer $k$, the emph{Gallai-Ramsey number} is defined to be the minimum number of vertices $n$ such that any $k$-edge coloring of $K_n$ contains either a rainbow (all different colored) copy of $G$ or a monochromatic copy of $G$. In this paper, we obtain general upper and lower bounds on the Gallai-Ramsey numbers for double stars $S(n,m)$, where $S(n,m)$ is the graph obtained from the union of two stars $K_{1,n}$ and $K_{1,m}$ by adding an edge between their centers. We also provide the sharp result in some cases.
قيم البحث
اقرأ أيضاً
For a graph $H$ and an integer $kge1$, the $k$-color Ramsey number $R_k(H)$ is the least integer $N$ such that every $k$-coloring of the edges of the complete graph $K_N$ contains a monochromatic copy of $H$. Let $C_m$ denote the cycle on $mge4$ vert
ices and let $Theta_m$ denote the family of graphs obtained from $C_m$ by adding an additional edge joining two non-consecutive vertices. Unlike Ramsey number of odd cycles, little is known about the general behavior of $R_k(C_{2n})$ except that $R_k(C_{2n})ge (n-1)k+n+k-1$ for all $kge2$ and $nge2$. In this paper, we study Ramsey number of even cycles with chords under Gallai colorings, where a Gallai coloring is a coloring of the edges of a complete graph without rainbow triangles. For an integer $kgeq 1$, the Gallai-Ramsey number $GR_k(H)$ of a graph $H$ is the least positive integer $N$ such that every Gallai $k$-coloring of the complete graph $K_N$ contains a monochromatic copy of $H$. We prove that $GR_k(Theta_{2n})=(n-1)k+n+1$ for all $kgeq 2$ and $ngeq 3$. This implies that $GR_k(C_{2n})=(n-1)k+n+1$ all $kgeq 2$ and $ngeq 3$. Our result yields a unified proof for the Gallai-Ramsey number of all even cycles on at least four vertices.
A Gallai coloring is a coloring of the edges of a complete graph without rainbow triangles, and a Gallai $k$-coloring is a Gallai coloring that uses at most $k$ colors. For an integer $kgeq 1$, the Gallai-Ramsey number $GR_k(H)$ of a given graph $H$
is the least positive integer $N$ such that every Gallai $k$-coloring of the complete graph $K_N$ contains a monochromatic copy of $H$. Let $C_m$ denote the cycle on $mge4$ vertices and let $Theta_m$ denote the family of graphs obtained from $C_m$ by adding an additional edge joining two non-consecutive vertices. We prove that $GR_k(Theta_{2n+1})=ncdot 2^k+1$ for all $kgeq 1$ and $ngeq 3$. This implies that $GR_k(C_{2n+1})=ncdot 2^k+1$ all $kgeq 1$ and $ngeq 3$. Our result yields a unified proof for the Gallai-Ramsey number of all odd cycles on at least five vertices.
A Gallai coloring of a complete graph is an edge-coloring such that no triangle has all its edges colored differently. A Gallai $k$-coloring is a Gallai coloring that uses $k$ colors. Given a graph $H$ and an integer $kgeq 1$, the Gallai-Ramsey numbe
r $GR_k(H)$ of $H$ is the least positive integer $N$ such that every Gallai $k$-coloring of the complete graph $K_N$ contains a monochromatic copy of $H$. Let $W_{2n} $ denote an even wheel on $2n+1ge5$ vertices. In this note, we study Gallai-Ramsey number of $W_{2n}$ and completely determine the exact value of $GR_k(W_4)$ for all $kge2$.
Given graphs $G$ and $H$ and a positive integer $k$, the emph{Gallai-Ramsey number}, denoted by $gr_{k}(G : H)$ is defined to be the minimum integer $n$ such that every coloring of $K_{n}$ using at most $k$ colors will contain either a rainbow copy o
f $G$ or a monochromatic copy of $H$. We consider this question in the cases where $G in {P_{4}, P_{5}}$. In the case where $G = P_{4}$, we completely solve the Gallai-Ramsey question by reducing to the $2$-color Ramsey numbers. In the case where $G = P_{5}$, we conjecture that the problem reduces to the $3$-color Ramsey numbers and provide several results in support of this conjecture.
Given two graphs $G$ and $H$, the $k$-colored Gallai-Ramsey number $gr_k(G : H)$ is defined to be the minimum integer $n$ such that every $k$-coloring of the complete graph on $n$ vertices contains either a rainbow copy of $G$ or a monochromatic copy
of $H$. In this paper, we consider $gr_k(K_3 : H)$ where $H$ is a connected graph with five vertices and at most six edges. There are in total thirteen graphs in this graph class, and the Gallai-Ramsey numbers for some of them have been studied step by step in several papers. We determine all the Gallai-Ramsey numbers for the remaining graphs, and we also obtain some related results for a class of unicyclic graphs.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
