Search

Robertson and Seymour proved that the family of all graphs containing a fixed graph H as a minor has the Erdős-Posa property if and only if H is planar. We show that this is no longer true for the edge version of the Erdős-Posa property, and indeed even fails when H is an arbitrary subcubic tree of large pathwidth or a long ladder. This answers a question of Raymond, Sau and Thilikos.

In this paper, we propose a simple and natural randomized algorithm to embed a tree T in a given graph G. The algorithm can be viewed as a “self-avoiding tree-indexed random walk“. The order of the tree T can be as large as a constant fraction of the order of the graph G, and the maximum degree of T can be close to the minimum degree of G. We show that our algorithm works in a variety of interesting settings. For example, we prove that any graph of minimum degree d without 4-cycles contains every tree of order ed 2 and maximum degree at most d-2ed-2. As there exist d-regular graphs without 4-cycles and with O(d 2) vertices, this result is optimal up to constant factors. We prove similar nearly tight results for graphs of given girth and graphs with no complete bipartite subgraph K s,t .

A connected graph G is said to be z-homogeneous if any isomorphism between finite connected induced subgraphs of G extends to an automorphism of G. Finite z-homogeneous graphs were classified in [17]. We show that z-homogeneity is equivalent to finite-transitivity on the class of infinite locally finite graphs. Moreover, we classify the graphs satisfying these properties. Our study of bipartite z-homogeneous graphs leads to a new characterization for hypercubes.

In this paper we prove a sufficient condition for the existence of a Hamilton cycle, which is applicable to a wide variety of graphs, including relatively sparse graphs. In contrast to previous criteria, ours is based on two properties only: one requiring expansion of “small” sets, the other ensuring the existence of an edge between any two disjoint “large” sets. We also discuss applications in positional games, random graphs and extremal graph theory.

It is shown that given a connected graph T with at least one edge and an arbitrary finite simplicial complex X, there is a graph G such that the complex Hom(T,G) is homotopy equivalent to X. The proof is constructive, and uses a nerve lemma. Along the way several results regarding Hom complexes, exponentials of graphs, and subdivisions are established that may be of independent interest.

We prove that any H-minor-free graph, for a fixed graph H, of treewidth w has an ?(w) × ?(w) grid graph as a minor. Thus grid minors suffice to certify that H-minorfree graphs have large treewidth, up to constant factors. This strong relationship was previously known for the special cases of planar graphs and bounded-genus graphs, and is known not to hold for general graphs. The approach of this paper can be viewed more generally as a framework for extending combinatorial results on planar graphs to hold on H-minor-free graphs for any fixed H. Our result has many combinatorial consequences on bidimensionality theory, parameter-treewidth bounds, separator theorems, and bounded local treewidth; each of these combinatorial results has several algorithmic consequences including subexponential fixed-parameter algorithms and approximation algorithms.

In this paper we present a Berge-Tutte-type theorem for a matching problem in directed graphs. This extends the maximum matching problem in undirected graphs, the maximum even factor problem in weakly symmetric directed graphs proposed by W. H. Cunningham and J. F. Geelen in [6], and a packing problem for cycles and edges in undirected graphs. We show an Edmonds-Gallai-type structural description of a canonical set attaining the minimum in the formula. We also give a generalization of the matching matroid to this concept.

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

Motivated by many recent algorithmic applications, this paper aims to promote a systematic study of the relationship between the topology of a graph and the metric distortion incurred when the graph is embedded into \math space. The main results are: 1. Explicit constant-distortion embeddings of all series-parallel graphs, and all graphs with bounded Euler number. These are thus the first natural families known to have constant distortion (strictly greater than 1). Using the above embeddings, we obtain algorithms to approximate the sparsest cut in such graphs to within a constant factor. 2. A constant-distortion embedding of outerplanar graphs into the restricted class of \math-metrics known as "dominating tree metrics". We also show a lower bound of \math on the distortion for embeddings of series-parallel graphs into (distributions over) dominating tree metrics. This shows, surprisingly, that such metrics approximate distances very poorly even for families of graphs with low treewidth, and excludes the possibility of using them to explore the finer structure of \math-embeddability.

A graph G is inexhaustible if whenever a vertex of G is deleted the remaining graph is isomorphic to G. We address a question of Cameron [6], who asked which countable graphs are inexhaustible. In particular, we prove that there are continuum many countable inexhaustible graphs with properties in common with the infinite random graph, including adjacency properties and universality. Locally finite inexhaustible graphs and forests are investigated, as is a semigroup structure on the class of inexhaustible graphs. We extend a result of [7] on homogeneous inexhaustible graphs to pseudo-homogeneous inexhaustible graphs.

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).

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.

and the testing algorithm can perform queries of the form: ``who is the ith neighbor of vertex v''. The tester should determine with high probability whether the graph is bipartite or e-far from bipartite for any given distance parameter e. Distance between graphs is defined to be the fraction of entries on which the graphs differ in their incidence-lists representation. Our testing algorithm has query complexity and running time where N is the number of graph vertices. It was shown before that queries are necessary (for constant e), and hence the performance of our algorithm is tight (in its dependence on N), up to polylogarithmic factors. In our analysis we use techniques that were previously applied to prove fast convergence of random walks on expander graphs. Here we use the contrapositive statement by which slow convergence implies small cuts in the graph, and further show that these cuts have certain additional properties. This implication is applied in showing that for any graph, the graph vertices can be divided into disjoint subsets such that: (1) the total number of edges between the different subsets is small; and (2) each subset itself exhibits a certain mixing property that is useful in our analysis.

Several properties of graphs with λ=μ=2,a2=4 are studied. It is proved that such graphs are locally unions of triangles, hexagons or heptagons. As a consequence, a distance regular graph with intersection array (13,10,7;1,2,7) does not exist.

In 1966 T. Gallai asked whether every criticalk-chromatic graph possesses an orientation having just one directed path of lengthk−1. In this note we show that in general the answer is negative, but also that the answer is affirmative whenk≥5 and the graph has maximal degree at mostk.

In this paper we explore some implications of viewing graphs asgeometric objects. This approach offers a new perspective on a number of graph-theoretic and algorithmic problems. There are several ways to model graphs geometrically and our main concern here is with geometric representations that respect themetric of the (possibly weighted) graph. Given a graphG we map its vertices to a normed space in an attempt to (i) keep down the dimension of the host space, and (ii) guarantee a smalldistortion, i.e., make sure that distances between vertices inG closely match the distances between their geometric images. In this paper we develop efficient algorithms for embedding graphs low-dimensionally with a small distortion. Further algorithmic applications include: Given faithful low-dimensional representations of statistical data, it is possible to obtain meaningful and efficientclustering. This is one of the most basic tasks in pattern-recognition. For the (mostly heuristic) methods used in the practice of pattern-recognition, see [20], especially chapter 6. Our studies of multicommodity flows also imply that every embedding of (the metric of) ann-vertex, constant-degree expander into a Euclidean space (of any dimension) has distortion Ω(logn). This result is tight, and closes a gap left open by Bourgain [12].

Cunningham and Edmonds [4[ have proved that a 2-connected graphG has a unique minimal decomposition into graphs, each of which is either 3-connected, a bond or a polygon. They define the notion of a good split, and first prove thatG has a unique minimal decomposition into graphs, none of which has a good split, and second prove that the graphs that do not have a good split are precisely 3-connected graphs, bonds and polygons. This paper provides an analogue of the first result above for 3-connected graphs, and an analogue of the second for minimally 3-connected graphs. Following the basic strategy of Cunningham and Edmonds, an appropriate notion of good split is defined. The first main result is that ifG is a 3-connected graph, thenG has a unique minimal decomposition into graphs, none of which has a good split. The second main result is that the minimally 3-connected graphs that do not have a good split are precisely cyclically 4-connected graphs, twirls (K3,n for somen≥3) and wheels. From this it is shown that ifG is a minimally 3-connected graph, thenG has a unique minimal decomposition into graphs, each of which is either cyclically 4-connected, a twirl or a wheel.

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.

We present a problem of construction of certain intersection graphs. If these graphs were explicitly constructed, we would have an explicit construction of Boolean functions of large complexity.

A generalization of the Prufer coding of trees is given providing a natural correspondence between the set of codes of spanning trees of a graph and the set of codes of spanning trees of theextension of the graph. This correspondence prompts us to introduce and to investigate a notion ofthe spanning tree volume of a graph and provides a simple relation between the volumes of a graph and its extension (and in particular a simple relation between the spanning tree numbers of a graph and its uniform extension). These results can be used to obtain simple purely combinatorial proofs of many previous results obtained by the Matrix-tree theorem on the number of spanning trees of a graph. The results also make it possible to construct graphs with the maximal number of spanning trees in some classes of graphs.

We establish a minimax formula for the chromatic index of series-parallel graphs; and also prove the correctness of a “greedy” algorithm for finding a vertex-colouring of a series-parallel graph.

In his thesis [3] B. D. Thatte conjectured that ifG=G 1,G 2,...G n is a sequence of finitely many simple connected graphs (isomorphic graphs may occur in the sequence) with the same number of vertices and edges then their shuffled edge deck uniquely determines the graph sequence (up to a permutation). In this paper we prove that there are such sequences of graphs with the same shuffled edge deck.

We consider the class of graphs characterized by the forbidden subgraphsC andN:C is the claw (unique graph with degree sequence (3, 1, 1, 1)) andN the net (unique graph with degree sequence (3, 3, 3, 1, 1, 1)). For this class of graphs (calledCN-free) an algorithm is described for determining the stability numberα(G). It is based on a construction associating with anyCN-free graphG anotherCN-free graphG′ such thatα(G′)=α(G)−1. Such a construction reducing the stability number is called a struction.

Results involving automorphisms and fragments of infinite graphs are proved. In particular for a given fragmentC and a vertex-transitive subgroupG of the automorphism group of a connected graph there exists σ≠G such that σ[C] ⊂C. This proves the countable case of a conjecture of L. Babai and M. E. Watkins concerning graphs allowing a vertex-transitive torsion group action.

Three new strongly regular graphs on 256, 120, and 135 vertices are described in this paper. They satisfy thet-vertex condition — in the sense of [1] — on the edges and on the nonedges fort=4 but they are not rank 3 graphs. The problem to search for any such graph was discussed on a folklore level several times and was fixed in [2]. Here the graph on 256 vertices satisfies even the 5-vertex condition, and has the graphs on 120 and 135 vertices as its subgraphs. The existence of these graphs was announced in [3] and [4]. [4] contains M. H. Klin's interpretation of the graph on 120 vertices. Further results concerning these graphs were obtained by A. E. Brouwer, cf. [5].

Using simplicial decompositions a new and simple proof of Lekkerkerker-Boland’s criterion for interval graphs is given. Also the infinite case is considered, and the problem is tackled to what extent the representation of a graph as an interval graph is unique.

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.

The splittance of an arbitrary graph is the minimum number of edges to be added or removed in order to produce a split graph (i.e. a graph whose vertex set can be partitioned into a clique and an independent set). The splittance is seen to depend only on the degree sequence of the graph, and an explicit formula for it is derived. This result allows to give a simple characterization of the degree sequences of split graphs. Worst cases for the splittance are determined for some classes of graphs (the class of all graphs, of all trees and of all planar graphs).

It is shown that a 3-skein isomorphism between 3-connected graphs with at least 5 vertices is induced by an isomorphism. These graphs have no loops but may be infinite and have multiple edges.

In this paper we introduce a notion ofrandom interval graphs: the intersection graphs of real, compact intervals whose end points are chosen at random. We establish results about the number of edges, degrees, Hamiltonicity, chromatic number and independence number of almost all interval graphs.

Given a graphG withn vertices andm edges, how many edges must be in the largest chordal subgraph ofG? Form=n2/4+1, the answer is 3n/2−1. Form=n2/3, it is 2n−3. Form=n2/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, andK4's.

We prove a reduction theorem for prime (simple) graphs in Cunningham’s sense. Roughly speaking this theorem says that every prime (simple) graph of ordern>5 “contains” a smaller prime graph of ordern−1. As an application we give a polynomial algorithm for recognizing circle graphs.

We call a graphmatching-covered if every line belongs to a perfect matching. We study the technique of “ear-decompositions” of such graphs. We prove that a non-bipartite matching-covered graph containsK 4 orK 2⊕K 3 (the triangular prism). Using this result, we give new characterizations of those graphs whose matching and covering numbers are equal. We apply these results to the theory of τ-critical graphs.

We prove that the inequalitys≦7 holds for finites-transitive graphs assuming that the list of known 2-transitive permutation groups is complete.