Search

We present new sharp sufficient conditions for the existence of properly colored and rainbow C4 ${C}_{4}$'s in edge‐colored graphs. Our first results deal with sharp color neighborhood conditions for the existence of properly colored C4 ${C}_{4}$'s in edge‐colored complete graphs and complete bipartite graphs, respectively. Next, we characterize the extremal graphs for an anti‐Ramsey number result due to Alon on the existence of rainbow C4 ${C}_{4}$'s in edge‐colored complete graphs. We also generalize Alon's result from complete to general edge‐colored graphs. Finally, we derive a structural property regarding the extremal graphs for a bipartite counterpart of Alon's result due to Axenovich, Jiang, and Kündgen on the existence of rainbow C4 ${C}_{4}$'s in edge‐colored complete bipartite graphs. We also generalize their result from complete to general bipartite edge‐colored graphs. [ABSTRACT FROM AUTHOR]

Given a graph G and a positive integer k, the sub-Ramsey number sr(G, k) is defined to be the minimum number m such that every K m whose edges are colored using every color at most k times contains a subgraph isomorphic to G all of whose edges have distinct colors. In this paper, we will concentrate on s r (n K 2 , k) with n K 2 denoting a matching of size n. We first give upper and lower bounds for s r (n K 2 , k) and exact values of s r (n K 2 , k) for some n and k. Afterwards, we show that s r (n K 2 , k) = 2 n when n is sufficiently large and k < n 8 by applying the Local Lemma. [ABSTRACT FROM AUTHOR]

Let $$G_1$$ and $$G_2$$ be two given graphs. The Ramsey number $$R(G_1,G_2)$$ is the least integer r such that for every graph G on r vertices, either G contains a $$G_1$$ or $$\overline{G}$$ contains a $$G_2$$ . A complete bipartite graph $$K_{1,n}$$ is called a star. The kipas $$\widehat{K}_n$$ is the graph obtained from a path of order n by adding a new vertex and joining it to all the vertices of the path. Alternatively, a kipas is a wheel with one edge on the rim deleted. Whereas for star-wheel Ramsey numbers not all exact values are known to date, in contrast we determine all exact values of star-kipas Ramsey numbers. [ABSTRACT FROM AUTHOR]

For a graph G, we denote by $$\nu (G)$$ the order of G, by $$\chi (G)$$ the chromatic number of G and by $$\sigma (G)$$ the minimum size of a color class over all proper $$\chi (G)$$ -colorings of G. For two graphs $$G_1$$ and $$G_2$$ , the Ramsey number $$R(G_1,G_2)$$ is the least integer r such that for every graph G on r vertices, either G contains a $$G_1$$ or $$\overline{G}$$ contains a $$G_2$$ . Suppose that $$G_1$$ is connected. We say that $$G_1$$ is $$G_2$$ -good if $$R(G_1,G_2)=(\chi (G_2)-1)(\nu (G_1)-1)+\sigma (G_2)$$ . In this note, we obtain a condition for graphs H such that a path is H-good. [ABSTRACT FROM AUTHOR]

For two given graphs $$G_1$$ and $$G_2$$ , the Ramsey number $$R(G_1,G_2)$$ is the least integer r such that for every graph G on r vertices, either G contains a $$G_1$$ or $$\overline{G}$$ contains a $$G_2$$ . In this note, we determined the Ramsey number $$R(K_{1,n},W_m)$$ for even m with $$n+2\le m\le 2n-2$$ , where $$W_m$$ is the wheel on $$m+1$$ vertices, i.e., the graph obtained from a cycle $$C_m$$ by adding a vertex v adjacent to all vertices of the $$C_m$$ . [ABSTRACT FROM AUTHOR]

Let G1 and G2 be two given graphs. The Ramsey number R(G1,G2) is the least integer r such that for every graph G on r vertices, either G contains a G1 or Ḡ contains a G2. Parsons gave a recursive formula to determine the values of R(Pn,K1,m), where Pn is a path on n vertices and K1,m is a star on m+1 vertices. In this note, we study the Ramsey numbers R(Pn,K1,m), where Pn is a linear forest on m vertices. We determine the exact values of R(Pn,K1∨Fm) for the cases m ≤ n and m ≥ 2n, and for the case that Fm has no odd component. Moreover, we give a lower bound and an upper bound for the case n+1 ≤ m ≤ 2n−1 and Fm has at least one odd component. [ABSTRACT FROM AUTHOR]

A spanning circuit in a graph is defined as a closed trail visiting each vertex of the graph. A compatible spanning circuit in an edge-colored graph refers to a spanning circuit in which each pair of edges traversed consecutively along the spanning circuit has distinct colors. As two extreme cases, sufficient conditions for the existence of compatible Hamilton cycles and compatible Euler tours have been obtained in previous literature. In this paper, we first establish sufficient conditions for the existence of compatible spanning circuits visiting each vertex exactly k times, for every feasible integer k , in edge-colored complete graphs and complete equipartition r -partite graphs. We also provide sufficient conditions for the existence of compatible spanning circuits visiting each vertex v at least ⌊ (d (v) − 1) ∕ 2 ⌋ times in edge-colored graphs satisfying Ore-type degree conditions. [ABSTRACT FROM AUTHOR]

Let G be an edge-colored complete graph on n vertices such that there exist at least n distinct colors on edges incident to every pair of its vertices. In this paper, we first show that every edge of G with n ≥ 6 k − 19 is contained in a properly colored cycle of length k. Further, we prove that if G contains no monochromatic triangles, then there exists a properly colored path of length l for every 1 ≤ l ≤ n − 1 between each pair of vertices of G and every vertex of G is contained in a properly colored cycle of length k for any 3 ≤ k ≤ n. [ABSTRACT FROM AUTHOR]

An edge-colored graph is called rainbow if all the colors on its edges are distinct. Given a positive integer n and a graph G , the anti-Ramsey number a r (n , G) is the maximum number of colors in an edge-coloring of K n with no rainbow copy of G. Denote by k C 3 the union of k vertex-disjoint copies of C 3. In this paper, we determine the anti-Ramsey number a r (n , k C 3) for n = 3 k and n ≥ 2 k 2 − k + 2 , respectively. When 3 k ≤ n ≤ 2 k 2 − k + 2 , we give lower and upper bounds for a r (n , k C 3). [ABSTRACT FROM AUTHOR]

A subgraph of an edge-colored graph is rainbow, if all of its edges have different colors. For a graph G and a family H of graphs, the anti-Ramsey number ar (G , H) is the maximum number k such that there exists an edge-coloring of G with exactly k colors without rainbow copy of any graph in H. In this paper, we study the anti-Ramsey numbers of C 3 and C 4 in complete r -partite graphs. For r ≥ 3 and n 1 ≥ n 2 ≥ ⋯ ≥ n r ≥ 1 , we determine ar (K n 1 , n 2 , ... , n r , { C 3 , C 4 }) , ar (K n 1 , n 2 , ... , n r , C 3) and ar (K n 1 , n 2 , ... , n r , C 4). [ABSTRACT FROM AUTHOR]