Search

For two graphs G 1 and G 2 , the star-critical Ramsey number r ∗ (G 1 , G 2) is the minimum integer k such that any red/blue edge-coloring of K r - 1 ⊔ K 1 , k contains a red copy of G 1 or a blue copy of G 2 , where r is the classical Ramsey number R (G 1 , G 2) and K r - 1 ⊔ K 1 , k is the graph obtained from a K r - 1 and an additional vertex v by joining v to k vertices of K r - 1 . Let C n denote a cycle of order n and W m a wheel of order m + 1 . Hook (2010) proved that r ∗ (C n , W 3) = 2 n for n ≥ 5 . In this paper, it is shown that r ∗ (C n , W m) = 2 n for m odd, n ≥ m ≥ 5 and n ≥ 60 . [ABSTRACT FROM AUTHOR]

A Gallai coloring of a complete graph is a coloring of the edges without rainbow triangles (all edges colored differently). Given a graph H and a positive integer k , the Gallai Ramsey number G R k (H) is the minimum integer N such that every Gallai k -coloring of K N contains a monochromatic copy of H. A uniform coloring of a complete multipartite graph is a coloring of the edges such that the edges between any two parts receive the same color. Given a graph H and positive integers k and ℓ , the ℓ -uniform Ramsey number R k ℓ (H) is the minimum integer N such that any uniform k -coloring of any complete multipartite graph on N vertices with each part of cardinality no more than ℓ , contains a monochromatic copy of H. Let K m , n denote a complete bipartite graph. Wu et al. conjectured that G R k (K m , n) = (n − 1) (k − 2) + R 2 1 (K m , n) if R 2 1 (K m , n) ≥ 3 m − 2 , where k ≥ 3 and m ≥ n ≥ 2. In this paper, we show that G R k (K m , n) = (n − 1) (k − 2) + R 2 m − 1 (K m , n) for all integers k ≥ 3 and m ≥ n ≥ 2. Based on this result, we improve the known general bounds for G R k (K m , n) , and confirm the conjecture for some complete bipartite graphs. [ABSTRACT FROM AUTHOR]

For two given sets C1 and C2 of cycles, the Ramsey number R(C1,C2) is the smallest integer N such that for any graph G on N vertices, either G contains a cycle from C1 or G¯ contains a cycle from C2. In this paper, we determine all Ramsey numbers R(C1,C2), which confirms a conjecture due to Hansson, and extends the well‐known Ramsey numbers for two cycles. [ABSTRACT FROM AUTHOR]

For two given graphs G 1 and G 2 , the planar Ramsey number P R (G 1 , G 2) is the smallest integer N such that every planar graph G on N vertices either contains a copy of G 1 or its complement contains a copy of G 2 . In this paper, we determine all planar Ramsey numbers for the complete graphs versus trees. [ABSTRACT FROM AUTHOR]

For two given graphs $$G_1$$ and $$G_2$$ , the planar Ramsey number $$PR(G_1,G_2)$$ is the smallest integer $$N$$ such that for any planar graph $$G$$ of order $$N$$ , either $$G$$ contains $$G_1$$ or the complement of $$G$$ contains $$G_2$$ . Let $$K_m$$ denote a complete graph of order $$m$$ and $$W_n$$ a wheel of order $$n+1$$ . In this paper, we determine all planar Ramsey numbers $$PR(K_m,W_n)$$ . [ABSTRACT FROM AUTHOR]

For two given graphs $G_{1}$ and $G_{2}$, the Ramsey number $R(G_{1},G_{2})$ is the smallest integer $N$ such that, for any graph $G$ of order $N$, either $G$ contains $G_{1}$ as a subgraph or the complement of $G$ contains $G_{2}$ as a subgraph. A fan $F_{l}$ is $l$ triangles sharing exactly one vertex. In this note, it is shown that $R(F_{n},F_{m})=4n+1$ for $n\geq \max \{m^{2}-m/2,11m/2-4\}$. [ABSTRACT FROM PUBLISHER]

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 at most k colors. Given an integer k ≥ 2 , and graphs H 1 , H 2 , ... , H k , the Gallai-Ramsey number G R (H 1 , H 2 , ... , H k) is the least positive integer N such that every Gallai k -coloring of the complete graph K N contains a monochromatic copy of H i in color i for some i ∈ { 1 , 2 , ... , k }. Let m G denote the union of m disjoint copies of G. This paper studies the Gallai–Ramsey number G R (t 1 K 3 , ... , t k K 3) for all integers t 1 ≥ t 2 ≥ ⋯ ≥ t k ≥ 1. The case t 1 = t 2 = ⋯ = t k = 1 was obtained by Chung and Graham (1983). In this paper, we obtain a general bound of G R (t 1 K 3 , ... , t k K 3) for all t 1 ≥ t 2 ≥ ⋯ ≥ t k ≥ 1 , and prove that both the upper and lower bounds can be attained for some t i , i ∈ { 1 , ... , k }. [ABSTRACT FROM AUTHOR]

Abstract For given graphs H 1 ,... , H k , k ≥ 2 , the k -color Ramsey number R (H 1 ,... , H k) is the smallest integer N such that every k -coloring of the edges of a complete graph K N contains a monochromatic copy of H i colored in i , for some i with 1 ≤ i ≤ k. Let C ℓ , K 1 , m and P n denote a cycle of length ℓ , a star of order m + 1 and a path of order n , respectively. In this paper, it is shown that R (C 4 , K 1 , m , P n) ≤ m + n − 1 + ⌈ m + n − 2 ⌉ for all m , n ≥ 2 and R (C 4 , K 1 , m , P n) ≤ m + n − 2 + ⌈ m + n − 2 ⌉ if m + n = ℓ 2 + 3 and ℓ ≥ 1. Moreover, by discussing the local structure of the polarity graph whose vertices are points in the projective plane over Galois fields, we show that the two upper bounds can be attained for some special m and n. These results also extend some known results on R (C 4 , K 1 , m) obtained by Parsons in 1975 and by Zhang et al. recently. [ABSTRACT FROM AUTHOR]

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 k ≥ 1 , the Gallai–Ramsey number G R 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 m ≥ 4 vertices and let Θ m denote the family of graphs obtained from C m by adding an additional edge joining two non-consecutive vertices. We prove that G R k (Θ 2 n + 1) = n ⋅ 2 k + 1 for all k ≥ 1 and n ≥ 3. This implies that G R k (C 2 n + 1) = n ⋅ 2 k + 1 all k ≥ 1 and n ≥ 3. Our result yields a unified proof for the Gallai–Ramsey number of all odd cycles on at least five vertices. [ABSTRACT FROM AUTHOR]

For a graph H and an integer k ≥ 1 , 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 m ≥ 4 vertices and let Θ 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 2 n) except that R k (C 2 n) ≥ (n − 1) k + n + k − 1 for all k ≥ 2 and n ≥ 2. 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 k ≥ 1 , the Gallai-Ramsey number G R 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 G R k (Θ 2 n) = (n − 1) k + n + 1 for all k ≥ 2 and n ≥ 3. This implies that G R k (C 2 n) = (n − 1) k + n + 1 all k ≥ 2 and n ≥ 3. Our result yields a unified proof for the Gallai-Ramsey number of all even cycles on at least four vertices. [ABSTRACT FROM AUTHOR]

Abstract: Given two graphs and , the Ramsey number is the smallest integer such that for any graph of order , either contains or its complement contains . Let denote a cycle of order and a wheel of order . In this paper, it is shown that for odd, and , and for odd and . [Copyright &y& Elsevier]