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.     

A note on the monotonicity of mixed Ramsey numbers

For two graphs, G and H, an edge coloring of a complete graph is (G,H)-good if there is no monochromatic subgraph isomorphic to G and no rainbow subgraph isomorphic to H in this coloring. The set of numbers of colors used by (G,H)-good colorings of K_n is called a mixed Ramsey spectrum. This note addresses a fundamental question of whether the spectrum is an interval. It is shown that the answer is “yes” if G is not a star and H does not contain a pendant edge.     

Gallai–Ramsey numbers for cycles

For given graphs G and H and an integer k, the Gallai–Ramsey number is defined to be the minimum integer n such that, in any k coloring of the edges of K_n, there exists a subgraph isomorphic to either a rainbow coloring of G or a monochromatic coloring of H. In this work, we consider Gallai–Ramsey numbers for the case when G=K₃ and H is a cycle of a fixed length.     

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.     

Rainbows in the Hypercube

Let Q_n be a hypercube of dimension n, that is, a graph whose vertices are binary n-tuples and two vertices are adjacent iff the corresponding n-tuples differ in exactly one position. An edge coloring of a graph H is called rainbow if no two edges of H have the same color. Let f(G,H) be the largest number of colors such that there exists an edge coloring of G with f(G,H) colors such that no subgraph isomorphic to H is rainbow. In this paper we start the investigation of this anti-Ramsey problem by providing bounds on f(Q_n,Q_k) which are asymptotically tight for k = 2 and by giving some exact results.     

Improvement on Brooks' chromatic bound for a class of graphs

Brooks' Theorem says that if for a graph G,Δ(G)=n, then G is n-colourable, unless (1) n=2 and G has an odd cycle as a component, or (2) n>2 and K_n+1 is a component of G. In this paper we prove that if a graph G has none of some three graphs (K_1,3;K₅?e and H) as an induced subgraph and if Δ(G)?6 and d(G)<Δ(G), then χ(G)<Δ(G). Also we give examples to show that the hypothesis Δ(G)?6 can not be non-trivially relaxed and the graph K₅?e can not be removed from the hypothesis. Moreover, for a graph G with none of K_1,3;K₅?e and H as an induced subgraph, we verify Borodin and Kostochka's conjecture that if for a graph G,Δ(G)?9 and d(G)<Δ(G), then χ(G)<Δ(G).     

Eigenvalues of a graph and its imbeddings

A graph H is imbedded in a graph G if a subset of the vertices of G determines a subgraph isomorphic to H. If λ(G) is the least eigenvalue of G and k_R(H) = lim sup_d→∞ {λ(G)| H imbedded in G; G regular and connected; diam(G) > d; deg(G) > d}, then λ(H) ? 2 ≤ k_R(H) ≤ λ(H) with these bounds being the best possible. Given a graph H, there exist arbitrarily large families of isospectral graphs such that H can be imbedded in each member of the family.     

On the Ramsey-Turán numbers of graphs and hypergraphs

Let t be an integer, f(n) a function, and H a graph. Define the t-Ramsey-Turán number of H, RT _t (n,H, f(n)), to be the maximum number of edges in an n-vertex, H-free graph G with α _t (G) ≤ f(n), where α _t (G) is the maximum number of vertices in a K _t -free induced subgraph of G. Erd?s, Hajnal, Simonovits, Sós and Szemerédi [6] posed several open questions about RT _t (n,K _s , o(n)), among them finding the minimum ? such that RT _t (n,K _t+? , o(n)) = Ω(n ²), where it is easy to see that RT _t (n,K _t+1, o(n)) = o(n ²). In this paper, we answer this question by proving that RT _t (n,K _t+2, o(n)) = Ω(n ²); our constructions also imply several results on the Ramsey-Turán numbers of hypergraphs.     

Star-critical Ramsey numbers

The graph Ramsey numberR(G,H) is the smallest integer r such that every 2-coloring of the edges of K_r contains either a red copy of G or a blue copy of H. We find the largest star that can be removed from K_r such that the underlying graph is still forced to have a red G or a blue H. Thus, we introduce the star-critical Ramsey numberr_∗(G,H) as the smallest integer k such that every 2-coloring of the edges of K_r−K_1,r−1−k contains either a red copy of G or a blue copy of H. We find the star-critical Ramsey number for trees versus complete graphs, multiple copies of K₂ and K₃, and paths versus a 4-cycle. In addition to finding the star-critical Ramsey numbers, the critical graphs are classified for R(T_n,K_m), R(nK₂,mK₂) and R(P_n,C₄).     

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.     

Some tree-star Ramsey Numbers

The Ramsey Number r(G₁, G₂) is the least integer N such that for every graph G with N vertices, either G has the graph G₁ as a subgraph or $\text{G}$, the complement of G, has the graph G₂ as a subgraph.In this paper we embed the paths P_m in a much larger class $\text{T}$ of trees and then show how some evaluations by T. D. Parsons of Ramsey numbers r(P_m, K_1,n), where K_1,n is the star of degree n, are also valid for r(T_m, K_1,n) where T_m ∈ $\text{T}$.     

Connection-graph and iteration-graph of monotone boolean functions

In this paper, we establish some relationships between the circuits of the connection-graph G_C(F), and the circuits of theiteration-graph G₁(F), of a monotone boolean function F. We first show that if G₁(F) contains an element circuit of length multiple of p? {2,3}, then G_C(F) contains an elementary circuit of length multiple of p; then we prove that if G_C(F) is a subgraph of a caterpillar, then G₁(F) is a subgraph of a tree; at last we exhibit an infinite family of monotone boolean functions {F_n; n = 2 × 5^q, q ≥ 1} such that any G_C(F_n) is a subgraph of a tree, and G₁(F_n) contains a circuit of length 2^q+1, i.e., of the order $\text{n}{}^{\mathrm{<mtext>log</mtext><mtext>2</mtext><mtext>log5</mtext>}}$.     

The rainbow number of matchings in regular bipartite graphs

Given a graph G and a subgraph H of G, let rb(G,H) be the minimum number r for which any edge-coloring of G with r colors has a rainbow subgraph H. The number rb(G,H) is called the rainbow number of H with respect to G. Denote as mK₂ a matching of size m and as B_n,k the set of all the k-regular bipartite graphs with bipartition (X,Y) such that X=Y=n and k≤n. Let k,m,n be given positive integers, where k≥3, m≥2 and n>3(m−1). We show that for every GB_n,k, rb(G,mK₂)=k(m−2)+2. We also determine the rainbow numbers of matchings in paths and cycles.     

On Some Ramsey Numbers for Quadrilaterals Versus Wheels

For given graphs G ₁ and G ₂, the Ramsey number R(G ₁, G ₂) is the least integer n such that every 2-coloring of the edges of K _n contains a subgraph isomorphic to G ₁ in the first color or a subgraph isomorphic to G ₂ in the second color. Surahmat et al. proved that the Ramsey number ${R(C_4, W_n) \leq n + \lceil (n-1)/3\rceil}$ . By using asymptotic methods one can obtain the following property: ${R(C_4, W_n) \leq n + \sqrt{n}+o(1)}$ . In this paper we show that in fact ${R(C_4, W_n) \leq n + \sqrt{n-2}+1}$ for n ≥ 11. Moreover, by modification of the Erd?s-Rényi graph we obtain an exact value ${R(C_4, W_{q^2+1}) = q^2 + q + 1}$ with q ≥ 4 being a prime power. In addition, we provide exact values for Ramsey numbers R(C ₄, W _n ) for 14 ≤ n ≤ 17.     

Nombres de ramsey dans le cas orienté

Given two directed graphs G₁, G₂, the Ramsey number R(G₁,G₂) is the smallest integer n such that for any partition {U₁,U₂} of the arcs of the complete symmetric directed graph K¹_n, there exists an integer i such that the partial graph generated by U_i contains G_i as a subgraph. In this article, we determine R(P?_m,D?_n) and R(D?_m,D?_n) for some values of m and n, where P?_m denotes the directed path having m vertices and D?_m is obtained from P?_m by adding an arc from the initial vertex of P?_m to the terminal vertex.     

More on monochromatic-rainbow Ramsey type theorems

An edge colored graph is called a rainbow if no two of its edges have the same color. Let ? and $\mathcal{G}$ be two families of graphs. Denote by $RM({\mathcal{H}},\mathcal{G})$ the smallest integer R, if it exists, having the property that every coloring of the edges of K _R by an arbitrary number of colors implies that either there is a monochromatic subgraph of K _R that is isomorphic to a graph in ? or there is a rainbow subgraph of K _R that is isomorphic to a graph in $\mathcal{G}$ . ${\mathcal{T}}_{n}$ is the set of all trees on n vertices. ${\mathcal{T}}_{n}(k)$ denotes all trees on n vertices with diam(T _n (k))≤k. In this paper, we investigate $RM({\mathcal{T}}_{n},4K_{2})$ , $RM({\mathcal{T}}_{n},K_{1,4})$ and $RM({\mathcal{T}}_{n}(4),K_{3})$ .     

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     

On the chromatic forcing number of a random graph

When we wish to compute lower bounds for the chromatic number χ(G) of a graph G, it is of interest to know something about the ‘chromatic forcing number’ f_χ(G), which is defined to be the least number of vertices in a subgraph H of G such that χ(H) = χ(G). We show here that for random graphs G_n,p with n vertices, f_χ(G_n,p) is almost surely at least ($\text{1}\text{2}$?ε)n, despite say the fact that the largest complete subgraph of G_n,p has only about log n vertices.     

Maximal antiramsey graphs and the strong chromatic number

A typical problem arising in Ramsey graph theory is the following. For given graphs G and L, how few colors can be used to color the edges of G in order that no monochromatic subgraph isomorphic to L is formed? In this paper we investigate the opposite extreme. That is, we will require that in any subgraph of G isomorphic to L, all its edges have different colors. We call such a subgraph a totally multicolored copy of L. Of particular interest to us will be the determination of X_s(n, e, L), defined to be the minimum number of colors needed to edge-color some graph G(n, ?) with n vertices and e edges so that all copies of L in it are totally multicolored. It turns out that some of these questions are surprisingly deep, and are intimately related, for example, to the well-studied (but little understood) functions r_k(n), defined to be the size of the largest subset of {1, 2,…, n} containing no k-term arithmetic progression, and g(n; k, l), defined to be the maximum number of triples which can be formed from {1, 2,…, n} so that no two triples share a common pair, and no k elements of {1, 2,…, n} span l triples.