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.     

A Minimum Degree Result for Disjoint Cycles and Forests in Graphs

F on s edges and k disjoint cycles. The main result is the following theorem. Let F be a forest on s edges without isolated vertices and let G be a graph of order at least with minimum degree at least , where k, s are nonnegative integers. Then G contains the disjoint union of the forest F and k disjoint cycles. This theorem provides a common generalization of previous results of Corrádi & Hajnal [4] and Brandt [3] who considered the cases (cycles only) and (forests only), respectively. Received: October 13, 1995     

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     

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.     

On a Max-min Problem Concerning Weights of Edges

The weight w(e) of an edge e = uv of a graph is defined to be the sum of degrees of the vertices u and v. In 1990 P. Erdős asked the question: What is the minimum weight of an edge of a graph G having n vertices and m edges? This paper brings a precise answer to the above question of Erdős. Received July 12, 1999     

On the Existence of Disjoint Cycles in a Graph

G is a graph of order at least 3k with . Then G contains k vertex-disjoint cycles. Received: April 23, 1998     

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.

Subdivisions of a Graph of Maximal Degree n + 1 in Graphs of Average Degree and Large Girth

Dedicated to the memory of Paul Erdős It is proved that for every finite graph H of maximal degree and every , there is an integer such that every finite graph of average degree at least and of girth at least contains a subdivision of H. Received May 5, 1999     

Random Graph Coverings I: General Theory and Graph Connectivity

In this paper we describe a simple model for random graphs that have an n-fold covering map onto a fixed finite base graph. Roughly, given a base graph G and an integer n, we form a random graph by replacing each vertex of G by a set of n vertices, and joining these sets by random matchings whenever the corresponding vertices are adjacent in G. The resulting graph covers the original graph in the sense that the two are locally isomorphic. We suggest possible applications of the model, such as constructing graphs with extremal properties in a more controlled fashion than offered by the standard random models, and also "randomizing" given graphs. The main specific result that we prove here (Theorem 1) is that if is the smallest vertex degree in G, then almost all n-covers of G are -connected. In subsequent papers we will address other graph properties, such as girth, expansion and chromatic number. Received June 21, 1999/Revised November 16, 2000 RID="*" ID="*" Work supported in part by grants from the Israel Academy of Aciences and the Binational Israel-US Science Foundation.     

Density Conditions for Panchromatic Colourings of Hypergraphs

Let be a hypergraph. A panchromatic t-colouring of is a t-colouring of its vertices such that each edge has at least one vertex of each colour; and is panchromatically t-choosable if, whenever each vertex is given a list of t colours, the vertices can be coloured from their lists in such a way that each edge receives at least t different colours. The Hall ratio of is . Among other results, it is proved here that if every edge has at least t vertices and whenever , then is panchromatically t-choosable, and this condition is sharp; the minimum such that every t-uniform hypergraph with is panchromatically t-choosable satisfies ; and except possibly when t = 3 or 5, a t-uniform hypergraph is panchromatically t-colourable if whenever , and this condition is sharp. This last result dualizes to a sharp sufficient condition for the chromatic index of a hypergraph to equal its maximum degree. Received November 10, 1998 RID="*" ID="*" This work was carried out while the first author was visiting Nottingham, funded by Visiting Fellowship Research Grant GR/L54585 from the Engineering and Physical Sciences Research Council. The work of this author was also partly supported by grants 96-01-01614 and 97-01-01075 of the Russian Foundation for Fundamental Research.     

On Bipartite Graphs with Linear Ramsey Numbers

Dedicated to the memory of Paul Erdős We provide an elementary proof of the fact that the ramsey number of every bipartite graph H with maximum degree at most is less than . This improves an old upper bound on the ramsey number of the n-cube due to Beck, and brings us closer toward the bound conjectured by Burr and Erdős. Applying the probabilistic method we also show that for all and there exists a bipartite graph with n vertices and maximum degree at most whose ramsey number is greater than for some absolute constant c>1. Received December 1, 1999 RID="*" ID="*" Supported by NSF grant DMS-9704114 RID="**" ID="**" Supported by KBN grant 2 P03A 032 16     

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.     

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     

Boolean Functions With Low Average Sensitivity Depend On Few Coordinates

. The sensitivity of a point is dist, i.e. the number of neighbors of the point in the discrete cube on which the value of differs. The average sensitivity of is the average of the sensitivity of all points in . (This can also be interpreted as the sum of the influences of the variables on , or as a measure of the edge boundary of the set which is the characteristic function of.) We show here that if the average sensitivity of is then can be approximated by a function depending on coordinates where is a constant depending only on the accuracy of the approximation but not on . We also present a more general version of this theorem, where the sensitivity is measured with respect to a product measure which is not the uniform measure on the cube. Received: November 12, 1996     

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

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     

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.     

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