NOTE New Upper Bounds for a Canonical Ramsey Problem

f (l,k) be the minimum n with the property that every coloring yields either with , or with all distinct. We prove that if , then as . This supports the conjecture of Lefmann, R?dl, and Thomas that . Received July 2, 1998     

An Anti-Ramsey Theorem

Let be the Turán number which gives the maximum size of a graph of order containing no subgraph isomorphic to . In 1973, Erdős, Simonovits and Sós [5] proved the existence of an integer such that for every integer , the minimum number of colours , such that every -colouring of the edges of which uses all the colours produces at least one all whose edges have different colours, is given by . However, no estimation of was given in [5]. In this paper we prove that for . This formula covers all the relevant values of n and p. Received January 27, 1997/Revised March 14, 2000     

The Distance-regular Graphs with Intersection Number and with an Eigenvalue

and with an eigenvalue . Received: October 2, 1995/Revised: Revised November 26, 1997     

Partitioning Graphs of Bounded Tree-Width

Received: October 10, 1996     

On the Relation Between Two Minor-Monotone Graph Parameters

, where μ and λ are minor-monotone graph invariants introduced by Colin de Verdière [3] and van der Holst, Laurent, and Schrijver [5]. It is also shown that a graph G exists with . The graphs G with maximal planar complement and , characterised by Kotlov, Lovász, and Vempala, are shown to be forbidden minors for . Received: June 13, 1997     

Bicliques in Graphs I: Bounds on Their Number

Bicliques are inclusion-maximal induced complete bipartite subgraphs in graphs. Upper bounds on the number of bicliques in bipartite graphs and general graphs are given. Then those classes of graphs where the number of bicliques is polynomial in the vertex number are characterized, provided the class is closed under induced subgraphs. Received January 27, 1997     

Note – Edge-Coloring Cliques with Three Colors on All 4-Cliques

is constructed such that every copy of has at least three colors on its edges. As , the number of colors used is . This improves upon the previous probabilistic bound of due to Erdős and Gyárfás. Received: March 12, 1998     

NOTE – Edge-Coloring Cliques with Many Colors on Subcliques

with colors in which the edges of every copy of together receive at least 3 colors. We prove that this construction also has the property that at least colors appear on the edges of every copy of for . Received August 11, 1998     

Induced Ramsey Numbers

   We investigate the induced Ramsey number of pairs of graphs (G, H). This number is defined to be the smallest possible order of a graph Γ with the property that, whenever its edges are coloured red and blue, either a red induced copy of G arises or else a blue induced copy of H arises. We show that, for any G and H with , we have

Self-Converse and Oriented Graphs among the Third Parts of Nearly Complete Digraphs

H into t isomorphic parts is generalized so that either a remainder R or a surplus S, both of the numerically smallest possible size, are allowed. The sets of such nearly parts are defined to be the floor class and the ceiling class , respectively. We restrict ourselves to the case of nearly third parts of , the complete digraph, with . Then if , else and . The existence of nearly third parts which are oriented graphs and/or self-converse digraphs is settled in the affirmative for all or most n's. Moreover, it is proved that floor classes with distinct R's can have a common member. The corresponding result on the nearly third parts of the complete 2-fold graph is deduced. Furthermore, also if . Received: September 12, 1994/Revised: Revised November 3, 1995     

More-Than-Nearly-Perfect Packings and Partial Designs

o (n) of the n vertices. Here we show, in particular, that regular uniform hypergraphs for which the ratio of degree to maximum codegree is , for some ɛ>0, have packings which cover all but vertices, where α=α(ɛ)>0. The proof is based on the analysis of a generalized version of R?dl's nibble technique. We apply the result to the problem of finding partial Steiner systems with almost enough blocks to be Steiner systems, where we prove that, for fixed positive integers t<k, there exist partial S(t,k,n)'s with at most uncovered t-sets, improving the earlier result. Received: September 23, 1994/Revised: November 14, 1996     

List Coloring of Random and Pseudo-Random Graphs

choice number of a graph G is the minimum integer k such that for every assignment of a set S(v) of k colors to every vertex v of G, there is a proper coloring of G that assigns to each vertex v a color from S(v). It is shown that the choice number of the random graph G(n, p(n)) is almost surely whenever . A related result for pseudo-random graphs is proved as well. By a special case of this result, the choice number (as well as the chromatic number) of any graph on n vertices with minimum degree at least in which no two distinct vertices have more than common neighbors is at most . Received: October 13, 1997     

Ramsey Numbers for Trees of Small Maximum Degree

For a tree T we write and , , for the sizes of the vertex classes of T as a bipartite graph. It is shown that for T with maximum degree , the obvious lower bound for the Ramsey number R(T,T) of is asymptotically the correct value for R(T,T). Received December 15, 1999 RID=" " ID=" " The first and third authors were partially supported by NSERC. The second author was partially supported by KBN grant 2 P03A 021 17.     

Perfect Matchings in ε-Regular Graphs and the Blow-Up Lemma

G on vertex set , , with density d>2ε and all vertex degrees not too far from d, has about as many perfect matchings as a corresponding random bipartite graph, i.e. about . In this paper we utilize that result to prove that with probability quickly approaching one, a perfect matching drawn randomly from G is spread evenly, in the sense that for any large subsets of vertices and , the number of edges of the matching spanned between S and T is close to |S||T|/n (c.f. Lemma 1). As an application we give an alternative proof of the Blow-up Lemma of Komlós, Sárk?zy and Szemerédi [10]. Received: December 5, 1997     

Concentration of Multivariate Polynomials and Its Applications

are independent random variables which take values either 0 or 1, and Y is a multi-variable polynomial in 's with positive coefficients. We give a condition which guarantees that Y concentrates strongly around its mean even when several variables could have a large effect on Y. Some applications will be discussed. Received March 29, 1999     

A Bound on the Total Chromatic Number

. The proof is probabilistic. Received: November 26, 1996     

Exact Bounds for Judicious Partitions of Graphs

has a bipartite subgraph of size at least . We show that every graph of size has a bipartition in which the Edwards bound holds, and in addition each vertex class contains at most edges. This is exact for complete graphs of odd order, which we show are the only extremal graphs without isolated vertices. We also give results for partitions into more than two classes. Received: December 27, 1996/Revised: Revised June 10, 1998     

An Algebraic Matching Algorithm

V by V skew-symmetric matrix , called the Tutte matrix, associated with a simple graph G=(V,E). He associates an indeterminate with each , then defines when , and otherwise. The rank of the Tutte matrix is exactly twice the size of a maximum matching of G. Using linear algebra and ideas from the Gallai–Edmonds decomposition, we describe a very simple yet efficient algorithm that replaces the indeterminates with constants without losing rank. Hence, by computing the rank of the resulting matrix, we can efficiently compute the size of a maximum matching of a graph. Received September 4, 1997     

Graphs Whose Circular Chromatic Number Equals the Chromatic Number

Received: October 24, 1997