On the Ramsey number of trees versus graphs with large clique number

Chvátal established that r(T_m, K_n) = (m – 1)(n – 1) + 1, where T_m is an arbitrary tree of order m and K_n is the complete graph of order n. This result was extended by Chartrand, Gould, and Polimeni who showed K_n could be replaced by a graph with clique number n and order n + 1 provided n ≧ 3 and m ≧ 3. We further extend these results to show that K_n can be replaced by any graph on n + 2 vertices with clique number n, provided n ≧ 5 and m ≧ 4. We then show that further extensions, in particular to graphs on n + 3 vertices with clique number n are impossible. We also investigate the Ramsey number of trees versus complete graphs minus sets of independent edges. We show that r(T_m, K_n –tK₂) = (m – 1)(n – t – 1) + 1 for m ≧ 3, n ≧ 6, where T_m is any tree of order m except the star, and for each t, O ≦ t ≦ [(n – 2)/2].     

On the Number of Edges in Colour-Critical Graphs and Hypergraphs

A (hyper)graph G is called k-critical if it has chromatic number k, but every proper sub(hyper)graph of it is (k-1)-colourable. We prove that for sufficiently large k, every k-critical triangle-free graph on n vertices has at least (k-o(k))n edges. Furthermore, we show that every (k+1)-critical hypergraph on n vertices and without graph edges has at least (k-3/³?{k}) n(k-3/\sqrt[3]{k}) n edges. Both bounds differ from the best possible bounds by o(kn) even for graphs or hypergraphs of arbitrary girth.     

Conditions for -graphic sequences to be potentially -graphic

An r-graph is a loopless undirected graph in which no two vertices are joined by more than r edges. An r-complete graph on m+1 vertices, denoted by , is an r-graph on m+1 vertices in which each pair of vertices is joined by exactly r edges. A non-increasing sequence π=(d₁,d₂,…,d_n) of nonnegative integers is said to be r-graphic if it is realizable by an r-graph on n vertices. An r-graphic sequence π is said to be potentially -graphic if it has a realization containing as a subgraph. In this paper, some conditions for r-graphic sequences to be potentially -graphic are given. These are generalizations from 1-graphs to r-graphs of four theorems due to Rao [A.R. Rao, The clique number of a graph with given degree sequence, in: A.R. Rao (Ed.), Proc. Symposium on Graph Theory, in: I.S.I. Lecture Notes Series, vol. 4, MacMillan and Co. India Ltd., (1979), 251–267; A.R. Rao, An Erdös-Gallai type result on the clique number of a realization of a degree sequence (unpublished)] and Kézdy and Lehel [A.E. Kézdy, J. Lehel, Degree sequences of graphs with prescribed clique size, in: Y. Alavi et al., (Eds.), in: Combinatorics, Graph Theory, and Algorithms, vol. 2, New Issues Press, Kalamazoo Michigan, 1999, 535–544].     

On the edge-density of 4-critical graphs

Gallai conjectured that every 4-critical graph on n vertices has at least 5/3n-2/3 edges. We prove this conjecture for 4-critical graphs in which the subgraph induced by vertices of degree 3 is connected.     

On unavoidable hypergraphs

A r-uniform hypergraph H (or a r-graph, for short) is a collection E = E(H) of r-element subsets (called edges) of a set V = V(H) (called vertices). We say a r-graph H is (n, e)-unavoidable if every r-graph with n vertices and e edges must contain H. In this paper we investigate the largest possible number of edges in an (n, e)-unavoidable 3-graph for fixed n and e. We also study the structure of such unavoidable 3-graphs.     

Uniform Families and Count Matroids

Given an r-graph G on [n], we are allowed to add consecutively new edges to it provided that every time a new r-graph with at least l edges and at most m vertices appears. Suppose we have been able to add all edges. What is the minimal number of edges in the original graph? For all values of parameters, we present an example of G which we conjecture to be extremal and establish the validity of our conjecture for a range of parameters. Our proof utilises count matroids which is a new family of matroids naturally extending that of White and Whiteley. We characterise, in certain cases, the extremal graphs. In particular, we answer a question by Erdős, Füredi and Tuza. Received: May 6, 1998 Final version received: September 1, 1999     

2-factors in triangle-free graphs

We study the cycle structure of 1-tough, triangle-free graphs. In particular, we prove that every such graph on n ≥ 3 vertices with minimum degree δ ≥ 1/4 (n + 2) has a 2-factor. We also show this is best possible by exhibiting an infinite class of 1-tough, triangle-free graphs having δ = 1/4(n + 1) and no 2-factor. © 1996 John Wiley & Sons, Inc.     

On the Maximum Number of Cliques in a Graph

A clique is a set of pairwise adjacent vertices in a graph. We determine the maximum number of cliques in a graph for the following graph classes: (1) graphs with n vertices and m edges; (2) graphs with n vertices, m edges, and maximum degree Δ; (3) d-degenerate graphs with n vertices and m edges; (4) planar graphs with n vertices and m edges; and (5) graphs with n vertices and no K₅-minor or no K_3,3-minor. For example, the maximum number of cliques in a planar graph with n vertices is 8(n − 2). Research supported by a Marie Curie Fellowship of the European Community under contract 023865, and by the projects MCYT-FEDER BFM2003-00368 and Gen. Cat 2001SGR00224.     

Subgraphs of colour-critical graphs

Some problems and results on the distribution of subgraphs in colour-critical graphs are discussed. In section 3 arbitrarily largek-critical graphs withn vertices are constructed such that, in order to reduce the chromatic number tok−2, at leastc _k n ² edges must be removed. In section 4 it is proved that a 4-critical graph withn vertices contains at mostn triangles. Further it is proved that ak-critical graph which is not a complete graph contains a (k−1)-critical graph which is not a complete graph.     

Contractions to k8

It is proved that the maximal number of edges in a graph with n ≧ 8 vertices that is not contractible to K₈ is 6n ? 21, unless 5 divides n, and the only graphs with n = 5m vertices and more than 6n ? 21 edges that are not contractible to K₈ are the K₅(2)-cockades that have exactly 6n ? 20 edges.     

How to decrease the diameter of triangle-free graphs

Assume that G is a triangle-free graph. Let be the minimum number of edges one has to add to G to get a graph of diameter at most d which is still triangle-free. It is shown that for connected graphs of order n and of fixed maximum degree. The proof is based on relations of and the clique-cover number of edges of graphs. It is also shown that the maximum value of over (triangle-free) graphs of order n is . The behavior of is different, its maximum value is . We could not decide whether for connected (triangle-free) graphs of order n with a positive ε. Received: October 12, 1997     

A characterization of diameter-2-critical graphs with no antihole of length four

A graph G is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. In this paper we characterize the diameter-2-critical graphs with no antihole of length four, that is, the diameter-2-critical graphs whose complements have no induced 4-cycle. Murty and Simon conjectured that the number of edges in a diameter-2-critical graph of order n is at most n ²/4 and that the extremal graphs are complete bipartite graphs with equal size partite sets. As a consequence of our characterization, we prove the Murty-Simon Conjecture for graphs with no antihole of length four.     

Small graphs with chromatic number 5: A computer search

In this article we give examples of a triangle-free graph on 22 vertices with chromatic number 5 and a K₄-free graph on 11 vertices with chromatic number 5. We very briefly describe the computer searches demonstrating that these are the smallest possible such graphs. All 5-critical graphs on 9 vertices are exhibited. © 1995 John Wiley & Sons, Inc.     

Bisections of graphs

A bisection of a graph is a bipartition of its vertex set in which the number of vertices in the two parts differ by at most 1, and its size is the number of edges which go across the two parts. In this paper, motivated by several questions and conjectures of Bollobás and Scott, we study maximum bisections of graphs. First, we extend the classical Edwards bound on maximum cuts to bisections. A simple corollary of our result implies that every graph on n vertices and m   edges with no isolated vertices, and maximum degree at most n/3+1$n/3+1$, admits a bisection of size at least m/2+n/6$m/2+n/6$. Then using the tools that we developed to extend Edwards?s bound, we prove a judicious bisection result which states that graphs with large minimum degree have a bisection in which both parts span relatively few edges. A special case of this general theorem answers a conjecture of Bollobás and Scott, and shows that every graph on n vertices and m   edges of minimum degree at least 2 admits a bisection in which the number of edges in each part is at most (1/3+o(1))m$(1/3+o(1))m$. We also present several other results on bisections of graphs.     

Perfect Matchings and K 4 3 -Tilings in Hypergraphs of Large Codegree

For a k-graph F, let t _l (n, m, F) be the smallest integer t such that every k-graph G on n vertices in which every l-set of vertices is included in at least t edges contains a collection of vertex-disjoint F-subgraphs covering all but at most m vertices of G. Let K _m ^k denote the complete k-graph on m vertices. The function $t_{k-1} (kn, 0, K_k^k)For a k-graph F, let t _l (n, m, F) be the smallest integer t such that every k-graph G on n vertices in which every l-set of vertices is included in at least t edges contains a collection of vertex-disjoint F-subgraphs covering all but at most m vertices of G. Let K _m ^k denote the complete k-graph on m vertices. The function (i.e. when we want to guarantee a perfect matching) has been previously determined by Kühn and Osthus [9] (asymptotically) and by R?dl, Ruciński, and Szemerédi [13] (exactly). Here we obtain asymptotic formulae for some other l. Namely, we prove that for any and , . Also, we present various bounds in another special but interesting case: t ₂(n, m, K ₄³) with m = 0 or m = o(n), that is, when we want to tile (almost) all vertices by copies of K ₄³, the complete 3-graph on 4 vertices. Reverts to public domain 28 years from publication. Oleg Pikhurko: Partially supported by the National Science Foundation, Grant DMS-0457512.     

Geometric Graphs with Few Disjoint Edges

A geometric graph is a graph drawn in the plane so that the vertices are represented by points in general position, the edges are represented by straight line segments connecting the corresponding points. Improving a result of Pach and T?rőcsik, we show that a geometric graph on n vertices with no k+1 pairwise disjoint edges has at most k ³ (n+1) edges. On the other hand, we construct geometric graphs with n vertices and approximately (3/2)(k-1)n edges, containing no k+1 pairwise disjoint edges. We also improve both the lower and upper bounds of Goddard, Katchalski, and Kleitman on the maximum number of edges in a geometric graph with no four pairwise disjoint edges. Received May 7, 1998, and in revised form March 24, 1999.     

Total domination of graphs and small transversals of hypergraphs

The main result of this paper is that every 4-uniform hypergraph on n vertices and m edges has a transversal with no more than (5n + 4m)/21 vertices. In the particular case n = m, the transversal has at most 3n/7 vertices, and this bound is sharp in the complement of the Fano plane. Chvátal and McDiarmid [5] proved that every 3-uniform hypergraph with n vertices and edges has a transversal of size n/2. Two direct corollaries of these results are that every graph with minimal degree at least 3 has total domination number at most n/2 and every graph with minimal degree at least 4 has total domination number at most 3n/7. These two bounds are sharp.     

A generalization of a conjecture due to Erd?s, Jacobson and Lehel

An r-graph is a loopless undirected graph in which no two vertices are joined by more than r edges. An r-complete graph on m+1 vertices, denoted by , is an r-graph on m+1 vertices in which each pair of vertices is joined by exactly r edges. A non-increasing sequence π=(d₁,d₂,…,d_n) of nonnegative integers is r-graphic if it is realizable by an r-graph on n vertices. Let be the smallest even integer such that each n-term r-graphic sequence with term sum of at least is realizable by an r-graph containing as a subgraph. In this paper, we determine the value of for sufficiently large n, which generalizes a conjecture due to Erd?s, Jacobson and Lehel.     

The size of chordal,interval and threshold subgraphs

Given a graphG withn vertices andm edges, how many edges must be in the largest chordal subgraph ofG? Form=n ²/4+1, the answer is 3n/2?1. Form=n ²/3, it is 2n?3. Form=n ²/3+1, it is at least 7n/3?6 and at most 8n/3?4. Similar questions are studied, with less complete results, for threshold graphs, interval graphs, and the stars on edges, triangles, andK ₄'s.