Bipartite rainbow numbers of matchings

Given two graphs G and H, let f(G,H) denote the maximum number c for which there is a way to color the edges of G with c colors such that every subgraph H of G has at least two edges of the same color. Equivalently, any edge-coloring of G with at least rb(G,H)=f(G,H)+1 colors contains a rainbow copy of H, where a rainbow subgraph of an edge-colored graph is such that no two edges of it have the same color. The number rb(G,H) is called the rainbow number ofHwith respect toG, and simply called the bipartite rainbow number ofH if G is the complete bipartite graph K_m,n. Erd?s, Simonovits and Sós showed that rb(K_n,K₃)=n. In 2004, Schiermeyer determined the rainbow numbers rb(K_n,K_k) for all n≥k≥4, and the rainbow numbers rb(K_n,kK₂) for all k≥2 and n≥3k+3. In this paper we will determine the rainbow numbers rb(K_m,n,kK₂) for all k≥1.     

On Ramsey numbers of fans

It is shown that r(F₂,F_n)=4n+1 for n≥2, and r(F_s,F_n)≤4n+2s for n≥s≥2.     

Complete solution for the rainbow numbers of matchings

For a given graph H and a positive n, the rainbow number ofH, denoted by rb(n,H), is the minimum integer k so that in any edge-coloring of K_n with k colors there is a copy of H whose edges have distinct colors. In 2004, Schiermeyer determined rb(n,kK₂) for all n≥3k+3. The case for smaller values of n (namely, ) remained generally open. In this paper we extend Schiermeyer’s result to all plausible n and hence determine the rainbow number of matchings.     

The Ramsey numbers of paths versus wheels

For two given graphs G₁ and G₂, the Ramsey number R(G₁,G₂) is the smallest integer n such that for any graph G of order n, either G contains G₁ or the complement of G contains G₂. Let P_n denote a path of order n and W_m a wheel of order m+1. In this paper, we show that R(P_n,W_m)=2n-1 for m even and n?m-1?3 and R(P_n,W_m)=3n-2 for m odd and n?m-1?2.     

The Ramsey numbers for cycles versus wheels of odd order

For two given graphs G₁ and G₂, the Ramsey number R(G₁,G₂) is the smallest integer n such that for any graph G of order n, either G contains G₁ or the complement of G contains G₂. Let C_n denote a cycle of order n and W_m a wheel of order m+1. It is conjectured by Surahmat, E.T. Baskoro and I. Tomescu that R(C_n,W_m)=2n−1 for even m≥4, n≥m and (n,m)≠(4,4). In this paper, we confirm the conjecture for n≥3m/2+1.     

Finding a monochromatic subgraph or a rainbow path

For simple graphs G and H, let f(G,H) denote the least integer N such that every coloring of the edges of K_N contains either a monochromatic copy of G or a rainbow copy of H. Here we investigate f(G,H) when H = P_k. We show that even if the number of colors is unrestricted when defining f(G,H), the function f(G,P_k), for k = 4 and 5, equals the (k ? 2)‐ coloring diagonal Ramsey number of G. © 2006 Wiley Periodicals, Inc. J Graph Theory     

Complete graphs and complete bipartite graphs without rainbow path

Motivated by Ramsey-type questions, we consider edge-colorings of complete graphs and complete bipartite graphs without rainbow path. Given two graphs $G$ and $H$, the $k$-colored Gallai–Ramsey number $g{r}_k(G:H)$ is defined to be the minimum integer $n$ such that $\left(\genfrac{}{}{0ex}{}{n}{2}\right)\ge k$ and for every $N\ge n$, every rainbow $G$-free coloring (using all $k$ colors) of the complete graph $K_N$ contains a monochromatic copy of $H$. In this paper, we first provide some exact values and bounds of $g{r}_k(P_5:K_t)$. Moreover, we define the $k$-colored bipartite Gallai–Ramsey number $bg{r}_k(G:H)$ as the minimum integer $n$ such that $n^2\ge k$ and for every $N\ge n$, every rainbow $G$-free coloring (using all $k$ colors) of the complete bipartite graph $K_{N,N}$ contains a monochromatic copy of $H$. Furthermore, we describe the structures of complete bipartite graph $K_{n,n}$ with no rainbow $P_4$ and $P_5$, respectively. Finally, we find the exact values of $bg{r}_k(P_4:K_{s,t})$ ($1\le s\le t$), $bg{r}_k(P_4:F)$ (where $F$ is a subgraph of $K_{s,t}$), $bg{r}_k(P_5:K_{1,t})$ and $bg{r}_k(P_5:K_{2,t})$ by using the structural results.     

Star-critical Ramsey numbers for large generalized fans and books

In this paper, we show that for any fixed integers $m\ge 2$ and $t\ge 2$, the star-critical Ramsey number $r_1(K_1+n{K}_t,K_{m+1})=(m?1)tn+t$ for all sufficiently large $n$. Furthermore, for any fixed integers $p\ge 2$ and $m\ge 2$, $r_1(K_p+n{K}_1,K_{m+1})=(m?1+o\left(1\right))n$ as $n\to \infty$.     

Rainbow and monochromatic circuits and cocircuits in binary matroids

Given a matroid together with a coloring of its ground set, a subset of its elements is called rainbow colored if no two of its elements have the same color. We show that if an n-element rank r binary matroid M is colored with exactly r colors, then M either contains a rainbow colored circuit or a monochromatic cocircuit. As the class of binary matroids is closed under taking duals, this immediately implies that if M is colored with exactly $n?r$ colors, then M either contains a rainbow colored cocircuit or a monochromatic circuit. As a byproduct, we give a characterization of binary matroids in terms of reductions to partition matroids.Motivated by a conjecture of Bérczi, Schwarcz and Yamaguchi, we also analyze the relation between the covering number of a binary matroid and the maximum number of colors or the maximum size of a color class in any of its rainbow circuit-free colorings. For simple graphic matroids, we show that there exists a rainbow circuit-free coloring that uses each color at most twice only if the graph is $(2,3)$-sparse, that is, it is independent in the 2-dimensional rigidity matroid. Furthermore, we give a complete characterization of minimally rigid graphs admitting such a coloring.     

The Ramsey numbers for disjoint unions of trees

For given graphs G and H, the Ramsey numberR(G,H) is the smallest natural number n such that for every graph F of order n: either F contains G or the complement of F contains H. In this paper, we investigate the Ramsey number R(∪G,H), where G is a tree and H is a wheel W_m or a complete graph K_m. We show that if n?3, then R(kS_n,W₄)=(k+1)n for k?2, even n and R(kS_n,W₄)=(k+1)n-1 for k?1 and odd n. We also show that .     

Generalized rainbow Turán numbers of odd cycles

Given graphs F and H, the generalized rainbow Turán number $\mathrm{ex}(n,F,\mathrm{rainbow-}H)$ is the maximum number of copies of F in an n-vertex graph with a proper edge-coloring that contains no rainbow copy of H. B. Janzer determined the order of magnitude of $\mathrm{ex}(n,C_s,\mathrm{rainbow-}{C}_t)$ for all $s\ge 4$ and $t\ge 3$, and a recent result of O. Janzer implied that $\mathrm{ex}(n,C_3,\mathrm{rainbow-}{C}_{2k})=O(n^{1+1/k})$. We prove the corresponding upper bound for the remaining cases, showing that $\mathrm{ex}(n,C_3,\mathrm{rainbow-}{C}_{2k+1})=O(n^{1+1/k})$. This matches the known lower bound for k even and is conjectured to be tight for k odd.     

Polynomial algorithm for sharp upper bound of rainbow connection number of maximal outerplanar graphs

For a finite simple edge-colored connected graph G (the coloring may not be proper), a rainbow path in G is a path without two edges colored the same; G is rainbow connected if for any two vertices of G, there is a rainbow path connecting them. Rainbow connection number, rc(G), of G is the minimum number of colors needed to color its edges such that G is rainbow connected. Chakraborty et al. (2011) [5] proved that computing rc(G) is NP-hard and deciding if rc(G)=2 is NP-complete. When edges of G are colored with fixed number k of colors, Kratochvil [6] proposed a question: what is the complexity of deciding whether G is rainbow connected? is this an FPT problem? In this paper, we prove that any maximal outerplanar graph is k rainbow connected for suitably large k and can be given a rainbow coloring in polynomial time.     

Rainbow Numbers for Cycles with Pendant Edges

A subgraph of an edge-colored graph is called rainbow if all of its edges have different colors. For a graph H and a positive integer n, the anti-Ramsey number f (n, H) is the maximum number of colors in an edge-coloring of K _n with no rainbow copy of H. The rainbow number rb(n, H) is the minimum number of colors such that any edge-coloring of K _n with rb(n, H) number of colors contains a rainbow copy of H. Certainly rb(n, H) = f(n, H) + 1. Anti-Ramsey numbers were introduced by Erdős et al. [4] and studied in numerous papers. We show that for n ≥ k + 1, where C _k ⁺ denotes a cycle C _k with a pendant edge.