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     

Topological Subgraphs in Graphs of Large Girth

H of maximum degree , there is an integer g(H) such that every finite graph of minimum degree n and girth at least g(H) contains a subdivision of H. This had been conjectured for in [8]. We prove also that every finite 2n-connected graph of sufficiently large girth is n-linked, and this is best possible for all . Received: February 26, 1997     

3n − 5 Edges Do Force a Subdivision of

We prove the conjecture of G. A. Dirac from 1964, that every graph of order with edges contains a subdivision of . Received: Septeber 4, 1997     

Vertex-Disjoint Triangles in Claw-Free Graphs with Minimum Degree at Least Three

. Our main result is as follows: For any integer , if G is a claw-free graph of order at least and with minimum degree at least 3, then G contains k vertex-disjoint triangles unless G is of order and G belongs to a known class of graphs. We also construct a claw-free graph with minimum degree 3 on n vertices for each such that it does not contain k vertex-disjoint triangles. We put forward a conjecture on vertex-disjoint triangles in -free graphs. Received: November 21, 1996/Revised: Revised February 19, 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     

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     

A Bound for the Diameter of Distance-Regular Graphs

n vertices has diameter at most 5 logn. This essentially settles a problem of Brouwer, Cohen and Neumaier. Received: October 2, 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     

A Theorem of Truemper

Received November 5, 1997     

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     

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     

Neighborhoods and Covering Vertices by Cycles

G =(V,E) is a 2-connected graph, and X is a set of vertices of G such that for every pair x,x' in X, , and the minimum degree of the induced graph <X> is at least 3, then X is covered by one cycle. This result will be in fact generalised by considering tuples instead of pairs of vertices. Let be the minimum degree in the induced graph <X>. For any , . If , and , then X is covered by at most (p-1) cycles of G. If furthermore , (p-1) cycles are sufficient. So we deduce the following: Let p and t () be two integers. Let G be a 2-connected graph of order n, of minimum degree at least t. If , and , then V is covered by at most cycles, where k is the connectivity of G. If furthermore , (p-1) cycles are sufficient. In particular, if and , then G is hamiltonian. Received April 3, 1998     

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

and with an eigenvalue . Received: October 2, 1995/Revised: Revised November 26, 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     

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     

A Bound on the Total Chromatic Number

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

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     

Principally Unimodular Skew-Symmetric Matrices

principally unimodular (PU) if every principal submatrix has determinant 0 or ±1. Let A be a symmetric (0, 1)-matrix, with a zero diagonal. A PU-orientation of A is a skew-symmetric signing of A that is PU. If A′ is a PU-orientation of A, then, by a certain decomposition of A, we can construct every PU-orientation of A from A′. This construction is based on the fact that the PU-orientations of indecomposable matrices are unique up to negation and multiplication of certain rows and corresponding columns by −1. This generalizes the well-known result of Camion, that if a (0, 1)-matrix can be signed to be totally unimodular then the signing is unique up to multiplying certain rows and columns by −1. Camion's result is an easy but crucial step in proving Tutte's famous excluded minor characterization of totally unimodular matrices. Received: May 17, 1996     

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     

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