Size Ramsey Numbers of Stars Versus 3-chromatic Graphs

  Let be the star with n edges, be the triangle, and be the family of odd cycles. We establish the following bounds on the corresponding size Ramsey numbers.

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.     

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

On a Generalized Anti-Ramsey Problem

For positive integers , a coloring of is called a -coloring if the edges of every receive at least and at most colors. Let denote the maximum number of colors in a -coloring of . Given we determine the largest such that all -colorings of have at most O(n) colors and we determine asymptotically when it is of order equal to . We give several bounds and constructions. Received May 3, 1999     

Chromatic Numbers of Cayley Graphs on Z and Recurrence

Dedicated to the memory of Paul Erdős In 1987 Paul Erdős asked me if the Cayley graph defined on Z by a lacunary sequence has necessarily a finite chromatic number. Below is my answer, delivered to him on the spot but never published, and some additional remarks. The key is the interpretation of the question in terms of return times of dynamical systems. Received February 7, 2000     

Small Universal Graphs for Bounded-Degree Planar Graphs

For all positive integers N and k, let denote the family of planar graphs on N or fewer vertices, and with maximum degree k. For all positive integers N and k, we construct a -universal graph of size . This construction answers with an explicit construction the previously open question of the existence of such a graph. Received July 8, 1998 RID="*" ID="*" Supported by NSF grant CCR98210-58 and ARO grant DAAH04-96-1-0013.     

Perfect Graphs, Partitionable Graphs and Cutsets

We prove a theorem about cutsets in partitionable graphs that generalizes earlier results on amalgams, 2-amalgams and homogeneous pairs. Received December 13, 1999 RID="*" ID="*" This work was supported in part by the Fields Institute for Research in Mathematical Sciences, Toronto, Canada, and by NSF grants DMI-0098427 and DMI-9802773 and ONR grant N00014-97-1-0196.     

Superpolynomial Size Set-systems with Restricted Intersections mod 6 and Explicit Ramsey Graphs

Dedicated to the memory of Paul Erdős We construct a system of subsets of a set of n elements such that the size of each set is divisible by 6 but their pairwise intersections are not divisible by 6. The result generalizes to all non-prime-power moduli m in place of m=6. This result is in sharp contrast with results of Frankl and Wilson (1981) for prime power moduli and gives strong negative answers to questions by Frankl and Wilson (1981) and Babai and Frankl (1992). We use our set-system to give an explicit Ramsey-graph construction, reproducing the logarithmic order of magnitude of the best previously known construction due to Frankl and Wilson (1981). Our construction uses certain mod m polynomials, discovered by Barrington, Beigel and Rudich (1994). Received January 15, 1996/Revised August 2, 1999     

Homomorphisms of Products of Graphs into Graphs Without Four Cycles

Given two graphs A and G, we write if there is a homomorphism of A to G and if there is no such homomorphism. The graph G is -free if, whenever both a and c are adjacent to b and d, then a = c or b = d. We will prove that if A and B are connected graphs, each containing a triangle and if G is a -free graph with and , then (here " denotes the categorical product). Received August 31, 1998/Revised April 19, 2000 RID="†" ID="†" Supported by NSERC of Canada Grant #691325.     

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     

Large Cliques in -Free Graphs

Dedicated to the memory of Paul Erdős A graph is called -free if it contains no cycle of length four as an induced subgraph. We prove that if a -free graph has n vertices and at least edges then it has a complete subgraph of vertices, where depends only on . We also give estimates on and show that a similar result does not hold for H-free graphs––unless H is an induced subgraph of . The best value of is determined for chordal graphs. Received October 25, 1999 RID="*" ID="*" Supported by OTKA grant T029074. RID="**" ID="**" Supported by TKI grant stochastics@TUB and by OTKA grant T026203.     

On the Signed Domination in Graphs

G on n vertices with minimum degree r, there exists a two-coloring of the vertices of G with colors +1 and -1, such that the closed neighborhood of each vertex contains more +1's than -1's, and altogether the number of 1's does not exceed the number of -1's by more than . As a construction by Füredi and Mubayi shows, this is asymptotically tight. The proof uses the partial coloring method from combinatorial discrepancy theory. Received May 12, 1998     

Totally Odd -subdivisions in 4-chromatic Graphs

We prove the conjecture made by Bjarne Toft in 1975 that every 4-chromatic graph contains a subdivision of in which each edge of corresponds to a path of odd length. As an auxiliary result we characterize completely the subspace of the cycle space generated by all cycles through two fixed edges. Toft's conjecture was proved independently in 1995 by Wenan Zang. Received May 26, 1998     

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     

Integer and Fractional Packings in Dense Graphs

Let be any fixed graph. For a graph G we define to be the maximum size of a set of pairwise edge-disjoint copies of in G. We say a function from the set of copies of in G to [0, 1] is a fractional -packing of G if for every edge e of G. Then is defined to be the maximum value of over all fractional -packings of G. We show that for all graphs G. Received July 27, 1998 / Revised December 3, 1999     

Connected [a,b]-factors in Graphs

In this paper, we prove the following result: Let G be a connected graph of order n, and minimum degree . Let a and b two integers such that 2a <= b. Suppose and . Then G has a connected [a,b]-factor. Received February 10, 1998/Revised July 31, 2000     

Random Minimum Length Spanning Trees in Regular Graphs

r -regular n-vertex graph G with random independent edge lengths, each uniformly distributed on (0, 1). Let mst(G) be the expected length of a minimum spanning tree. We show that mst(G) can be estimated quite accurately under two distinct circumstances. Firstly, if r is large and G has a modest edge expansion property then , where . Secondly, if G has large girth then there exists an explicitly defined constant such that . We find in particular that . Received: Februray 9, 1998     

NOTE The Johnson Graphs Satisfy a Distance Extension Property

G has property if whenever F and H are connected graphs with and |H|=|F|+1, and and are isometric embeddings, then there is an isometric embedding such that . It is easy to construct an infinite graph with for all k, and holds in almost all finite graphs. Prior to this work, it was not known whether there exist any finite graphs with . We show that the Johnson graphs J(n,3) satisfy whenever , and that J(6,3) is the smallest graph satisfying . We also construct finite graphs satisfying and local versions of the extension axioms studied in connection with the Rado universal graph. Received June 9, 1998     

Hamiltonian Kneser Graphs

The Kneser graph K(n,k) has as vertices the k-subsets of {1, 2, ..., n}. Two vertices are adjacent if the corresponding k-subsets are disjoint. It was recently proved by the first author [2] that Kneser graphs have Hamilton cycles for n >= 3k. In this note, we give a short proof for the case when k divides n. Received September 14, 1999