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.     

Long paths in sparse random graphs

We consider random graphs withn labelled vertices in which edges are chosen independently and with probabilityc/n. We prove that almost every random graph of this kind contains a path of length ≧(1 −α(c))n where α(c) is an exponentially decreasing function ofc. Dedicated to Tibor Gallai on his seventieth birthday     

On-line coloring of perfect graphs

Lovász, Saks, and Trotter showed that there exists an on-line algorithm which will color any on-linek-colorable graph onn vertices withO(nlog^(2k–3) n/log^(2k–4) n) colors. Vishwanathan showed that at least (log ^k–1 n/k ^k ) colors are needed. While these remain the best known bounds, they give a distressingly weak approximation of the number of colors required. In this article we study the case of perfect graphs. We prove that there exists an on-line algorithm which will color any on-linek-colorable perfect graph onn vertices withn ^10k/loglogn colors and that Vishwanathan's techniques can be slightly modified to show that his lower bound also holds for perfect graphs. This suggests that Vishwanathan's lower bound is far from tight in the general case.Research partially supported by Office of Naval Research grant N00014-90-J-1206.     

An optimal lower bound on the number of variables for graph identification

In this paper we show that (n) variables are needed for first-order logic with counting to identify graphs onn vertices. Thek-variable language with counting is equivalent to the (k–1)-dimensional Weisfeiler-Lehman method. We thus settle a long-standing open problem. Previously it was an open question whether or not 4 variables suffice. Our lower bound remains true over a set of graphs of color class size 4. This contrasts sharply with the fact that 3 variables suffice to identify all graphs of color class size 3, and 2 variables suffice to identify almost all graphs. Our lower bound is optimal up to multiplication by a constant becausen variables obviously suffice to identify graphs onn vertices.Research supported by NSF grant CCR-8709818.Research supported by NSF grant CCR-8805978 and Pennsylvania State University Research Initiation grant 428-45.Research supported by NSF grants DCR-8603346 and CCR-8806308.     

Automorphisms of random graphs with specified vertices

Conditions are found under which the expected number of automorphisms of a large random labelled graph with a given degree sequence is close to 1. These conditions involve the probability that such a graph has a given subgraph. One implication is that the probability that a random unlabelledk-regular simple graph onn vertices has only the trivial group of automorphisms is asymptotic to 1 asn → ∞ with 3≦k=O(n ^1/2−c). In combination with previously known results, this produces an asymptotic formula for the number of unlabelledk-regular simple graphs onn vertices, as well as various asymptotic results on the probable connectivity and girth of such graphs. Corresponding results for graphs with more arbitrary degree sequences are obtained. The main results apply equally well to graphs in which multiple edges and loops are permitted, and also to bicoloured graphs. Research of the second author supported by U. S. National Science Foundation Grant MCS-8101555, and by the Australian Department of Science and Technology under the Queen Elizabeth II Fellowships Scheme. Current address: Mathematics Department, University of Auckland, Auckland, New Zealand.     

Explicit constructions of graphs without short cycles and low density codes

We give an explicit construction of regular graphs of degree 2r withn vertices and girth ≧c logn/logr. We use Cayley graphs of factor groups of free subgroups of the modular group. An application to low density codes is given.     

On Turán’s theorem for sparse graphs

For a graphG withn vertices and average valencyt, Turán’s theorem yields the inequalityα≧n/(t+1) whereα denotes the maximum size of an independent set inG. We improve this bound for graphs containing no large cliques.     

On the signless Laplacian spectral radius of graphs with cut vertices

In this paper, we show that among all the connected graphs with n vertices and k cut vertices, the maximal signless Laplacian spectral radius is attained uniquely at the graph G_n,k, where G_n,k is obtained from the complete graph K_n-k by attaching paths of almost equal lengths to all vertices of K_n-k. We also give a new proof of the analogous result for the spectral radius of the connected graphs with n vertices and k cut vertices (see [A. Berman, X.-D. Zhang, On the spectral radius of graphs with cut vertices, J. Combin. Theory Ser. B 83 (2001) 233-240]). Finally, we discuss the limit point of the maximal signless Laplacian spectral radius.     

Independent sets ink-chromatic graphs

A graph is said to have propertyP _k if in eachk-colouring ofG using allk colours there arek independent vertices having all colours. An (unpublished) suggestion of P. Erdős is answered in the affirmative: For eachk≧3 there is a k-critical graph withP _k . With the aid of a construction of T. Gallaik-chromatic graphs (k≧7) withP _k orP _k+1 of arbitrarily high connectivity are obtained. The main result is: Eachk-chromatic graph (k≧3) of girth ≧6 hasP _k or is a circuit of length 7. Dedicated to Paul Erdős on his seventieth birthday     

An algorithm for finding hamilton paths and cycles in random graphs

This paper describes a polynomial time algorithm HAM that searches for Hamilton cycles in undirected graphs. On a random graph its asymptotic probability of success is that of the existence of such a cycle. If all graphs withn vertices are considered equally likely, then using dynamic programming on failure leads to an algorithm with polynomial expected time. The algorithm HAM is also used to solve the symmetric bottleneck travelling salesman problem with probability tending to 1, asn tends to ∞. Various modifications of HAM are shown to solve several Hamilton path problems. Supported by NSF Grant MCS 810 4854.     

The signless Laplacian spectral radius of tricyclic graphs and trees with k pendant vertices

In this paper, we consider the following problem: of all tricyclic graphs or trees of order n with k pendant vertices (n,k fixed), which achieves the maximal signless Laplacian spectral radius?We determine the graph with the largest signless Laplacian spectral radius among all tricyclic graphs with n vertices and k pendant vertices. Then we show that the maximal signless Laplacian spectral radius among all trees of order n with k pendant vertices is obtained uniquely at T_n,k, where T_n,k is a tree obtained from a star K_1,k and k paths of almost equal lengths by joining each pendant vertex to one end-vertex of one path. We also discuss the signless Laplacian spectral radius of T_n,k and give some results.     

Graphs With 3n−6 Edges Not Containing A Subdivision Of K 5

We determine all graphs on n ≥ 3 vertices with 3n-6 edges which do not contain a subdivision of K₅. These are exactly the graphs which one gets from any number of disjoint maximal planar graphs by successively pasting along triangles.     

A class of constructions for turán’s (3, 4)-problem

Letf(n) denote the minimal number of edges of a 3-uniform hypergraphG=(V, E) onn vertices such that for every quadrupleY ⊂V there existsY ⊃e ∈E. Turán conjectured thatf(3k)=k(k−1)(2k−1). We prove that if Turán’s conjecture is correct then there exist at least 2 ^k−2 non-isomorphic extremal hypergraphs on 3k vertices.     

Disjoint shortest paths in graphs

It is an interesting problem that how much connectivity ensures the existence ofn disjoint paths joining givenn pairs of vertices, but to get a sharp bound seems to be very difficult. In this paper, we study how muchgeodetic connectivity ensures the existence ofn disjointgeodesics joining givenn pairs of vertices, where a graph is calledk-geodetically connected if the removal of anyk−1 vertices does not change the distance between any remaining vertices.     

Cycles through specified vertices of a graph

We prove that ifS is a set ofk−1 vertices in ak-connected graphG, then the cycles throughS generate the cycle space ofG. Moreover, whenk≧3, each cycle ofG can be expressed as the sum of an odd number of cycles throughS. On the other hand, ifS is a set ofk vertices, these conclusions do not necessarily hold, and we characterize the exceptional cases. As corollaries, we establish the existence of odd and even cycles through specified vertices and deduce the existence of long odd and even cycles in graphs of high connectivity.     

Global Connectivity And Expansion: Long Cycles and Factors In f-Connected Graphs

Given a function f : ℕ→ℝ, call an n-vertex graph f-connected if separating off k vertices requires the deletion of at least f(k) vertices whenever k≤(n−f(k))/2. This is a common generalization of vertex connectivity (when f is constant) and expansion (when f is linear). We show that an f-connected graph contains a cycle of length linear in n if f is any linear function, contains a 1-factor and a 2-factor if f(k)≥2k+1, and contains a Hamilton cycle if f(k)≥2(k+1)². We conjecture that linear growth of f suffices to imply hamiltonicity.     

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     

An approximate Dirac-type theorem for k-uniform hypergraphs

A k-uniform hypergraph is hamiltonian if for some cyclic ordering of its vertex set, every k consecutive vertices form an edge. In 1952 Dirac proved that if the minimum degree in an n-vertex graph is at least n/2 then the graph is hamiltonian. We prove an approximate version of an analogous result for uniform hypergraphs: For every K ≥ 3 and γ > 0, and for all n large enough, a sufficient condition for an n-vertex k-uniform hypergraph to be hamiltonian is that each (k − 1)-element set of vertices is contained in at least (1/2 + γ)n edges. Research supported by NSF grant DMS-0300529. Research supported by KBN grant 2P03A 015 23 and N201036 32/2546. Part of research performed at Emory University, Atlanta. Research supported by NSF grant DMS-0100784.     

Small transversals in hypergraphs

For each positive integerk, we consider the setA _k of all ordered pairs [a, b] such that in everyk-graph withn vertices andm edges some set of at mostam+bn vertices meets all the edges. We show that eachA _k withk2 has infinitely many extreme points and conjecture that, for every positive , it has only finitely many extreme points [a, b] witha. With the extreme points ordered by the first coordinate, we identify the last two extreme points of everyA _k , identify the last three extreme points ofA ₃, and describeA ₂ completely. A by-product of our arguments is a new algorithmic proof of Turán's theorem.     

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