Constrained Ramsey numbers for rainbow matching

The Ramsey number R_k(G) of a graph G is the minimum number N, such that any edge coloring of K_N with k colors contains a monochromatic copy of G. The constrained Ramsey number f(G, T) of the graphs G and T is the minimum number N, such that any edge coloring of K_N with any number of colors contains a monochromatic copy of G or a rainbow copy of T. We show that these two quantities are closely related when T is a matching. Namely, for almost all graphs G, f(G, tK₂) = R_{t ? 1}(G) for t≥2. © 2010 Wiley Periodicals, Inc. J Graph Theory 67:91‐95, 2011     

The minimum degree of Ramsey‐minimal graphs

We write H → G if every 2‐coloring of the edges of graph H contains a monochromatic copy of graph G. A graph H is G‐minimal if H → G, but for every proper subgraph H′ of H, H′ ? G. We define s(G) to be the minimum s such that there exists a G‐minimal graph with a vertex of degree s. We prove that s(K_k) = (k ? 1)² and s(K_a,b) = 2 min(a,b) ? 1. We also pose several related open problems. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 167–177, 2007     

Constrained Ramsey numbers of graphs

Given two graphs G and H, let f(G,H) denote the minimum integer n such that in every coloring of the edges of K_n, there is either a copy of G with all edges having the same color or a copy of H with all edges having different colors. We show that f(G,H) is finite iff G is a star or H is acyclic. If S and T are trees with s and t edges, respectively, we show that 1+s(t?2)/2≤f(S,T)≤(s?1)(t²+3t). Using constructions from design theory, we establish the exact values, lying near (s?1)(t?1), for f(S,T) when S and T are certain paths or star‐like trees. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 1–16, 2003     

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.     

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₄).     

The characterization of zero-sum (mod 2) bipartite Ramsey numbers

Let G be a bipartite graph, with k|e(G). The zero-sum bipartite Ramsey number B(G, Z_k) is the smallest integer t such that in every Z_k-coloring of the edges of K_t,t, there is a zero-sum mod k copy of G in K_t,t. In this article we give the first proof that determines B(G, Z₂) for all possible bipartite graphs G. In fact, we prove a much more general result from which B(G, Z₂) can be deduced: Let G be a (not necessarily connected) bipartite graph, which can be embedded in K_n,n, and let F be a field. A function f : E(K_n,n) → F is called G-stable if every copy of G in K_n,n has the same weight (the weight of a copy is the sum of the values of f on its edges). The set of all G-stable functions, denoted by U(G, K_n,n, F) is a linear space, which is called the K_n,n uniformity space of G over F. We determine U(G, K_n,n, F) and its dimension, for all G, n and F. Utilizing this result in the case F = Z₂, we can compute B(G, Z₂), for all bipartite graphs G. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 151–166, 1998     

Edge‐face chromatic number and edge chromatic number of simple plane graphs

Given a simple plane graph G, an edge‐face k‐coloring of G is a function ? : E(G) ∪ F(G) → {1,…,k} such that, for any two adjacent or incident elements a, b ∈ E(G) ∪ F(G), ?(a) ≠ ?(b). Let χ_e(G), χ_ef(G), and Δ(G) denote the edge chromatic number, the edge‐face chromatic number, and the maximum degree of G, respectively. In this paper, we prove that χ_ef(G) = χ_e(G) = Δ(G) for any 2‐connected simple plane graph G with Δ (G) ≥ 24. © 2005 Wiley Periodicals, Inc. J Graph Theory     

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.     

On totally multicolored stars

Given an edge‐coloring of a graph G, a subgraph M of G will be called totally multicolored if no two edges of M receive the same color. Let h(G, K_1,q) be the minimum integer such that every edge‐coloring of G using exactly h(G, K_1,q) colors produces at least one totally multicolored copy of K_1,q (the q‐star) in G. In this article, an upper bound of h(G, K_1,q) is presented, as well as some applications of this upper bound. © 2005 Wiley Periodicals, Inc.     

On the number of list-colorings

Given a list of boxes L for a graph G (each vertex is assigned a finite set of colors that we call a box), we denote by f(G, L) the number of L-colorings of G (each vertex must be colored wiht a color of its box). In the case where all the boxes are identical and of size k, f(G, L) = p(G, k), where P=G, k) is the chromatic polynominal of G. We denote by F(G, k) the minimum of f(G, L) over all the lists of boxes such that each box has size at least k. It is clear that F(G, k) ≤ P(G, k) for all G, k, and we will see in the introduction some examples of graphs such that F(G, k) < P(G, k) for some k. However, we will show, in answer to a problem proposed by A. Kostochka and A. Sidorenko (Fourth Czechoslovak Symposium on Combinatorics, Prachatice, Jin, 1990), that for all G, F(G, k) = P(G, k) for all k sufficiently large. It will follow in particular that F(G, k) is not given by a polynominal in k for all G. The proof is based on the analysis of an algorithm for computing f(G, L) analogous to the classical one for computing P(G, k).     

Bipartite anti‐Ramsey numbers of cycles

We determine the maximum number of colors in a coloring of the edges of K_m,n such that every cycle of length 2k contains at least two edges of the same color. One of our main tools is a result on generalized path covers in balanced bipartite graphs. For positive integers q≤ a, let g(a,q) be the maximum number of edges in a spanning subgraph G of K_a,a such that the minimum number of vertex‐disjoint even paths and pairs of vertices from distinct partite sets needed to cover V(G) is q. We prove that g(a,q) = a² ? aq + max {a, 2q ? 2}. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 9–28, 2004     

A constructive approach for the lower bounds on the Ramsey numbers R (s,t)

Graph G is a (k, p)‐graph if G does not contain a complete graph on k vertices K_k, nor an independent set of order p. Given a (k, p)‐graph G and a (k, q)‐graph H, such that G and H contain an induced subgraph isomorphic to some K_k?1‐free graph M, we construct a (k, p + q ? 1)‐graph on n(G) + n(H) + n(M) vertices. This implies that R (k, p + q ? 1) ≥ R (k, p) + R (k, q) + n(M) ? 1, where R (s, t) is the classical two‐color Ramsey number. By applying this construction, and some its generalizations, we improve on 22 lower bounds for R (s, t), for various specific values of s and t. In particular, we obtain the following new lower bounds: R (4, 15) ≥ 153, R (6, 7) ≥ 111, R (6, 11) ≥ 253, R (7, 12) ≥ 416, and R (8, 13) ≥ 635. Most of the results did not require any use of computer algorithms. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 231–239, 2004     

On induced Folkman numbers

In 1970, Folkman proved that for any graph G there exists a graph H with the same clique number as G. In addition, any r ‐coloring of the vertices of H yields a monochromatic copy of G. For a given graph G and a number of colors r let f(G, r) be the order of the smallest graph H with the above properties. In this paper, we give a relatively small upper bound on f(G, r) as a function of the order of G and its clique number. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 40, 493–500, 2012     

Set vertex colorings and joins of graphs

For a nontrivial connected graph G, let c: V (G) → ℕ be a vertex coloring of G where adjacent vertices may be colored the same. For a vertex v of G, the neighborhood color set NC(v) is the set of colors of the neighbors of v. The coloring c is called a set coloring if NC(u) ≠ NC(v) for every pair u, v of adjacent vertices of G. The minimum number of colors required of such a coloring is called the set chromatic number x _s (G). A study is made of the set chromatic number of the join G+H of two graphs G and H. Sharp lower and upper bounds are established for x _s (G + H) in terms of x _s (G), x _s (H), and the clique numbers ω(G) and ω(H).     

Cleavages of graphs: the spectral radius

A cleavage of a finite graph G is a morphism f : H → G of graphs such that if P is the m × n characteristic matrix defined as P _ik = 1 if i ∈ f ^?1(k), otherwise = 0, then A(H)P ≤ PA(G), where A(G) and A(H) are the adjacency matrices of G and H, respectively. This concept generalizes induced subgraphs, quotients of graphs, Galois covers, path-tree graphs and others. We show that for spectral radii we have the inequality ρ(H) ≤ ρ(G). Equality holds only in case f : H → G is an equivariant quotient and H has isoperimetric constant i(H) = 0.     

A note on short cycles in a hypercube

How many edges can a quadrilateral-free subgraph of a hypercube have? This question was raised by Paul Erd?s about 27 years ago. His conjecture that such a subgraph asymptotically has at most half the edges of a hypercube is still unresolved. Let f(n,C_l) be the largest number of edges in a subgraph of a hypercube Q_n containing no cycle of length l. It is known that f(n,C_l)=o(|E(Q_n)|), when l=4k, k?2 and that . It is an open question to determine f(n,C_l) for l=4k+2, k?2. Here, we give a general upper bound for f(n,C_l) when l=4k+2 and provide a coloring of E(Q_n) by four colors containing no induced monochromatic C₁₀.     

On the Size‐Ramsey Number of Hypergraphs

The size‐Ramsey number of a graph G is the minimum number of edges in a graph H such that every 2‐edge‐coloring of H yields a monochromatic copy of G. Size‐Ramsey numbers of graphs have been studied for almost 40 years with particular focus on the case of trees and bounded degree graphs. We initiate the study of size‐Ramsey numbers for k‐uniform hypergraphs. Analogous to the graph case, we consider the size‐Ramsey number of cliques, paths, trees, and bounded degree hypergraphs. Our results suggest that size‐Ramsey numbers for hypergraphs are extremely difficult to determine, and many open problems remain.     

An application of the regularity lemma in generalized Ramsey theory

Given graphs G and H, an edge coloring of G is called an (H,q)‐coloring if the edges of every copy of H ? G together receive at least q colors. Let r(G,H,q) denote the minimum number of colors in a (H,q)‐coloring of G. In 9 Erd?s and Gyárfás studied r(K_n,K_p,q) if p and q are fixed and n tends to infinity. They determined for every fixed p the smallest q (denoted by q_lin) for which r(K_n,K_p,q) is linear in n and the smallest q (denoted by q_quad) for which r(K_n,K_p,q) is quadratic in n. They raised the problem of determining the smallest q for which we have . In this paper by using the Regularity Lemma we show that if , then we have . © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 39–49, 2003