Search

The Turán number ex(n,H) $\text{ex}(n,H)$ is the maximum number of edges in an H $H$‐free graph on n $n$ vertices. Let T $T$ be any tree. The odd‐ballooning of T $T$, denoted by To ${T}_{o}$, is a graph obtained by replacing each edge of T $T$ with an odd cycle containing the edge, and all new vertices of the odd cycles are distinct. In this paper, we determine the exact value of ex(n,To) $\text{ex}(n,{T}_{o})$ for sufficiently large n $n$ and To ${T}_{o}$ being good, which generalizes all the known results on ex(n,To) $\text{ex}(n,{T}_{o})$ for T $T$ being a star, due to Erdős, Füredi, Gould, and Gunderson (1995), Hou, Qiu, and Liu (2018), and Yuan (2018), and provides some counterexamples with chromatic number three to a conjecture of Keevash and Sudakov (2004), on the maximum number of edges not in any monochromatic copy of H $H$ in a 2‐edge‐coloring of a complete graph of order n $n$. [ABSTRACT FROM AUTHOR]

The generalized Turán number ex (n , K s , F) denotes the maximum number of copies of K s in an n -vertex F -free graph. Let kF denote k disjoint copies of F. Gerbner et al. (2019) [8] gave a lower bound for ex (n , K 3 , 2 C 5) and obtained the magnitude of ex (n , K s , k K r). In this paper, we determine the exact value of ex (n , K 3 , 2 C 5) and described the unique extremal graph for large n. Moreover, we also determine the exact value of ex (n , K r , (k + 1) K r) which generalizes some known results. [ABSTRACT FROM AUTHOR]

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]

The generalized Turán number e x (n , K s , H) is defined to be the maximum number of copies of a complete graph K s in any H-free graph on n vertices. Let F be an even linear forest, that is, F consists of paths of even order. In this paper, we determine the value of e x (n , K s , F) , which generalizes or improves some known results on generalized Turán number and classical Turán number. [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]

Abstract For k given graphs G 1 , G 2 , ... , G k , k ≥ 2 , the k -color Ramsey number, denoted by R (G 1 , G 2 , ... , G k) , is the smallest integer N such that if we arbitrarily color the edges of a complete graph of order N with k colors, then it always contains a monochromatic copy of G i colored with i , for some 1 ≤ i ≤ k. Let C m be a cycle of length m and K 1 , n a star of order n + 1. In this paper, firstly we give a general upper bound of R (C 4 , C 4 , ... , C 4 , K 1 , n). In particular, for the 3-color case, we have R (C 4 , C 4 , K 1 , n) ≤ n + 4 n + 5 + 3 and this bound is tight in some sense. Furthermore, we prove that R (C 4 , C 4 , K 1 , n) ≤ n + 4 n + 5 + 2 for all n = ℓ 2 − ℓ and ℓ ≥ 2 , and if ℓ is a prime power, then the equality holds. [ABSTRACT FROM AUTHOR]

For two given graphs G1 and G2, the Ramsey number R(G1,G2) is the smallest integer n such that for any graph G of order n, either G contains G1 or its complement G¯ contains G2. Let Pn,Sn and Tn denote a path, a star and a tree of order n, respectively. A generalized wheel, denoted by Ws,m, is the join of a complete graph Ks and a cycle Cm. In this paper, we show that R(Tn,Ws,4)=(n-1)(s+1)+1 for n≥3,s≥2 and R(Tn,Ws,5)=(n-1)(s+2)+1 for n≥3,s≥1. These generalize some known results on Ramsey numbers for a tree versus a wheel. [ABSTRACT FROM AUTHOR]

A Hamiltonian cycle decomposition of a complete graph K 2 n + 1 is an n -edge-coloring of K 2 n + 1 such that each color class is a Hamiltonian cycle. For a given Hamiltonian cycle decomposition, a subgraph of K 2 n + 1 is called rainbow if all its edges are colored differently. Let H be any subgraph of K 2 n + 1 consisting of n edges. In 1999, Wu conjectured that K 2 n + 1 has a Hamiltonian cycle decomposition such that H is rainbow. In this paper, we show that the conjecture is true in the cases that | H | ≤ n + 1 , or H is a linear forest, or n ≤ 5. Using this result, we partially confirm a conjecture on restricted size Ramsey numbers due to Miralaei and Shahsiah in 2020. [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 of order N , either G contains a copy of G 1 or its complement contains a copy of G 2 . Let C m be a cycle of length m and K 1 , n a star of order n + 1 . Parsons (1975) [6] shows that R ( C 4 , K 1 , n ) ≤ n + ⌊ n − 1 ⌋ + 2 for all n ≥ 2 and the equality holds if n is the square of a prime power. Let q be a prime power. In this paper, we first construct a graph Γ q on q 2 − 1 vertices without C 4 by using the Galois field F q , and then we prove that R ( C 4 , K 1 , ( q − 1 ) 2 + t ) = ( q − 1 ) 2 + q + t for q ≥ 4 is even and t = 1 , 0 , − 2 , and R ( C 4 , K 1 , q ( q − 1 ) − t ) = q 2 − t for q ≥ 5 is odd and t = 2 , 4 , . . . , 2 ⌈ q 4 ⌉ . [ABSTRACT FROM AUTHOR]

The generalized Turán number ex (n , K s , H) is defined to be the maximum number of copies of a complete graph K s in any H -free graph on n vertices. Let F be a linear forest consisting of k paths of orders ℓ 1 , ℓ 2 ,... , ℓ k. By characterizing the structure of the F -free graph with large minimum degree, we determine the value of ex (n , K s , F) for n = Ω (| F | s) and k ≥ 2 except some ℓ i = 3 , and the corresponding extremal graphs. Our result confirms a conjecture, due to Yuan and Zhang (2021), on classical Turán number of any linear forest for n = Ω (| F | 2) and each ℓ i ≠ 3 , and improves some known results on classical Turán number of linear forest. [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]

Given two 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_1$$ is a subgraph of $$G$$ , or $$G_2$$ is a subgraph of the complement of $$G$$ . We consider the case that $$G_1$$ is a cycle and $$G_2$$ is a (generalized) wheel. We expand the knowledge on exact values of Ramsey numbers in three directions: large cycles versus wheels of odd order; large wheels versus cycles of even order; and large cycles versus generalized odd wheels. [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]

For k given graphs H 1 , ... , H k , k ≥ 2 , the k -color Ramsey number, denoted by R (H 1 , ... , H k) , is the smallest integer N such that if we arbitrarily color the edges of a complete graph of order N with k colors, then it always contains a monochromatic copy of H i colored with i , for some 1 ≤ i ≤ k. Let C m be a cycle of length m , K 1 , n a star of order n + 1 and W n a wheel of order n + 1. In this paper, by using algebraic and probabilistic methods, we first give two lower bounds for (k + 1) -color Ramsey number R (C 4 , ... , C 4 , K 1 , n) for some special n , which shows the upper bound due to Zhang et al. (2019) is tight in some sense, and then establish a general lower bound for R (C 4 , ... , C 4 , K 1 , n) in terms of n and k , which extends the classical result of Burr et al. (1989). Moreover, we show that R (C 4 , ... , C 4 , K 1 , n) = R (C 4 , ... , C 4 , W n) for sufficiently large n. [ABSTRACT FROM AUTHOR]

Abstract: For two given graphs and , the planar Ramsey number is the smallest integer such that for any planar graph on vertices, either contains or its complement contains . Let denote a cycle of length and a complete graph of order . Sun, Yang, Lin and Song conjectured that and the conjecture was proved for . In this paper, it is shown that which confirms the conjecture for . [Copyright &y& Elsevier]

Abstract: For two given graphs and , the Ramsey number is the smallest integer such that for any graph of order , either contains or the complement of contains . Let denote a cycle of order and a wheel of order . Surahmat, Baskoro and Tomescu conjectured that for odd, and . In this paper, we confirm the conjecture for . [Copyright &y& Elsevier]

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

Abstract: For two given graphs and , the Ramsey number is the smallest integer such that for any graph of order , either contains or the complement of contains . Let denote a cycle of length m and a complete graph of order . It was conjectured that for and . We show that and , and the latter result confirms the conjecture in the case when . [Copyright &y& Elsevier]

Abstract: Let denote a tree of order and a wheel of order . In this paper, we show the Ramsey numbers for , where if , if or and , and otherwise; for . [Copyright &y& Elsevier]

For two given graphs G1 and G2, the Ramsey number R(G1,G2) is the smallest positive integer n such that for any graph G of order n, either G contains G1 or the complement of G contains G2. Let Sn denote a star of order n and Wm a wheel of order m+1. This paper shows that R(Sn,W6)=2n+1 for n≥3 and R(Sn,Wm)=3n-2 for m odd and n≥m-1≥2. [Copyright &y& Elsevier]

Let Tn denote a tree of order n and Wm a wheel of order m + 1. In a previous paper, we evaluated the Ramsey number R(Tn, Wm) in the cases where Tn is the star of order n and m = 6 or m is odd and n ≥ m - 1 ≥ 2. In this paper, we determine R(Tn, W6) in the case where the maximum degree of Tn is at least n - 3. Our results show that a recent conjecture of Baskoro et al. is false. [Copyright &y& Elsevier]

Abstract: For two given graphs and , the Ramsey number is the smallest integer such that for any graph of order , either contains or the complement of contains . Let denote a cycle of order and a wheel of order . In this paper, we show that for odd, and , which was conjectured by Surahmat, Baskoro and Tomescu. [Copyright &y& Elsevier]

Abstract: For two given graphs and , the Ramsey number is the smallest integer n such that for any graph G of order n, either G contains or the complement of G contains . Let denote a path of order n and a wheel of order . In this paper, we show that for m even and and for m odd and . [Copyright &y& Elsevier]

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]

Abstract: For two given graphs and , the Ramsey number is the smallest integer such that for any graph of order , either contains or the complement of contains . Let denote a cycle of order and a wheel of order . It is conjectured by Surahmat, E.T. Baskoro and I. Tomescu that for even , and . In this paper, we confirm the conjecture for . [Copyright &y& Elsevier]

For bipartite graphs H 1 , ... , H μ , μ ≥ 2 , the μ -color bipartite Ramsey number, denoted by R b (H 1 , ... , H μ) , is the least positive integer N such that if we arbitrarily color the edges of a complete bipartite graph K N , N with μ colors, then it contains a monochromatic copy of H i in color i for some i , 1 ≤ i ≤ μ. Let C 4 and K 1 , n be a quadrilateral and a star on n + 1 vertices, respectively. In this paper, we show that the (μ + 1) -color bipartite Ramsey number R b (C 4 , ... , C 4 , K 1 , n) ≤ n + ⌈ 1 2 μ 2 (4 n + μ 2 + 2 μ − 7) + 4 ⌉ + μ 2 + μ 2 − 1. Moreover, using algebraic methods, we construct Ramsey graphs or near Ramsey graphs and determine infinitely many values of R b (C 4 , ... , C 4 , K 1 , n) , which reach the upper bound if μ = 1 , 2 and are at most ⌊ μ 2 ⌋ less than the upper bound if μ ≥ 3. [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 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 , G contains G 1 as a subgraph or the complement of G contains G 2 as a subgraph. Let T n denote a tree of order n , W n a wheel of order n + 1 and F n a fan of order 2 n + 1 . We establish Ramsey numbers for fans and trees versus wheels of even order, thereby extending several known results. In particular, we prove that R ( F n , W m ) = 6 n + 1 for odd m ≥ 3 and n ≥ ( 5 m + 3 ) / 4 , and that R ( T n , W m ) = 3 n − 2 for odd m ≥ 3 and n ≥ m − 2 , and T n being a tree for which the Erdős–Sós Conjecture holds. [ABSTRACT FROM AUTHOR]

In this paper, we study the upper size Ramsey number u ( G 1 , G 2 ) , defined by Erdős and Faudree, as well as the star-critical Ramsey number r ∗ ( G 1 , G 2 ) , defined by Hook and Isaak. We define Ramsey-full graphs and size Ramsey good graphs, and perform a detailed study on these graphs. We generalize earlier results by determining u ( n K k , m K l ) and r ∗ ( n K k , m K l ) for k , l ≥ 3 and large m , n ; u ( C n , C m ) for m odd, with n > m ≥ 3 ; and r ∗ ( C n , C m ) for m odd, with n ≥ m ≥ 3 and ( m , n ) ≠ ( 3 , 3 ) . [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. Let T n be a tree of order n , S n a star of order n , and F m a fan of order 2 m + 1 , i.e., m triangles sharing exactly one vertex. In this paper, we prove that R ( T n , F m ) = 2 n − 1 for n ≥ 3 m 2 − 2 m − 1 , and if T n = S n , then the range can be replaced by n ≥ max { m ( m − 1 ) + 1 , 6 ( m − 1 ) } , which is tight in some sense. [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]