Extremal subgraphs of random graphs

We prove that there is a constant c > 0, such that whenever p ≥ n^‐c, with probability tending to 1 when n goes to infinity, every maximum triangle‐free subgraph of the random graph G_n,p is bipartite. This answers a question of Babai, Simonovits and Spencer (Babai et al., J Graph Theory 14 (1990) 599–622). The proof is based on a tool of independent interest: we show, for instance, that the maximum cut of almost all graphs with M edges, where M ? n and M ≤ /2, is “nearly unique”. More precisely, given a maximum cut C of G_n,M, we can obtain all maximum cuts by moving at most \begin{align*}\mathcal{O}(\sqrt{n^3/M})\end{align*} vertices between the parts of C. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Compatible triangulations and point partitions by series-triangular graphs

We introduce series-triangular graph embeddings and show how to partition point sets with them. This result is then used to prove an upper bound on the number of Steiner points needed to obtain compatible triangulations of point sets. The problem is generalized to finding compatible triangulations for more than two point sets and we show that such triangulations can be constructed with only a linear number of Steiner points added to each point set. Moreover, the compatible triangulations constructed by these methods are regular triangulations.     

Spanning maximal planar subgraphs of random graphs

We study the threshold for the existence of a spanning maximal planar subgraph in the random graph G_{n, p} . We show that it is very near p = 1/n^? We also discuss the threshold for the existence of a spanning maximal outerplanar subgraph. This is very near p = 1/n^½.     

Topological minors in bipartite graphs

For a bipartite graph G on m and n vertices, respectively, in its vertices classes, and for integers s and t such that 2 ≤ s ≤ t, 0 ≤ m − s ≤ n − t, and m + n ≤ 2s + t − 1, we prove that if G has at least mn − (2(m − s) + n − t) edges then it contains a subdivision of the complete bipartite K _(s,t) with s vertices in the m-class and t vertices in the n-class. Furthermore, we characterize the corresponding extremal bipartite graphs with mn − (2(m − s) + n − t + 1) edges for this topological Turan type problem.     

Two characterisations of the minimal triangulations of permutation graphs

A minimal triangulation of a graph is a chordal supergraph with an inclusion-minimal edge set. Minimal triangulations are obtained from adding edges only to minimal separators, completing minimal separators into cliques. Permutation graphs are the comparability graphs whose complements are also comparability graphs. Permutation graphs can be characterised as the intersection graphs of specially arranged line segments in the plane, which is called a permutation diagram. The minimal triangulations of permutation graphs are known to be interval graphs, and they can be obtained from permutation diagrams by applying a geometric operation, that corresponds to the completion of separators into cliques. We precisely specify this geometric completion process to obtain minimal triangulations, and we completely characterise those interval graphs that are minimal triangulations of permutation graphs.     

Spanning bipartite quadrangulations of even triangulations

A triangulation (resp., a quadrangulation) on a surface is a map of a loopless graph (possibly with multiple edges) on with each face bounded by a closed walk of length 3 (resp., 4). It is easy to see that every triangulation on any surface has a spanning quadrangulation. Kündgen and Thomassen proved that every even triangulation (ie, each vertex has even degree) on the torus has a spanning nonbipartite quadrangulation, and that if has sufficiently large edge width, then also has a bipartite one. In this paper, we prove that an even triangulation on the torus admits a spanning bipartite quadrangulation if and only if does not have as a subgraph, and moreover, we give some other results for the problem.     

Minimizer graphs for a class of extremal problems

We consider the family of graphs with a fixed number of vertices and edges. Among all these graphs, we are looking for those minimizing the sum of the square roots of the vertex degrees. We prove that there is a unique such graph, which consists of the largest possible complete subgraph plus only one other non‐isolated vertex. The same result is proven for any power of the vertex‐degrees less than one half. © 2002 Wiley Periodicals, Inc. J Graph Theory 39: 230–240, 2002; DOI 10.1002/jgt.10025     

Spanning 3-colourable subgraphs of small bandwidth in dense graphs

A conjecture by Bollobás and Komlós states the following: For every γ>0 and integers r2 and Δ, there exists β>0 with the following property. If G is a sufficiently large graph with n vertices and minimum degree at least and H is an r-chromatic graph with n vertices, bandwidth at most βn and maximum degree at most Δ, then G contains a copy of H.This conjecture generalises several results concerning sufficient degree conditions for the containment of spanning subgraphs. We prove the conjecture for the case r=3.     

Spanning trees in randomly perturbed graphs

A classical result of Komlós, Sárközy, and Szemerédi states that every n‐vertex graph with minimum degree at least (1/2 + o(1))n contains every n‐vertex tree with maximum degree . Krivelevich, Kwan, and Sudakov proved that for every n‐vertex graph G_α with minimum degree at least αn for any fixed α > 0 and every n‐vertex tree T with bounded maximum degree, one can still find a copy of T in G_α with high probability after adding O(n) randomly chosen edges to G_α. We extend the latter results to trees with (essentially) unbounded maximum degree; for a given and α > 0, we determine up to a constant factor the number of random edges that we need to add to an arbitrary n‐vertex graph with minimum degree αn in order to guarantee with high probability a copy of any fixed n‐vertex tree with maximum degree at most Δ.     

The number of edges of radius-invariant graphs

The eccentricity e(υ) of vertex υ is defined as a distance to a farthest vertex from υ. The radius of a graph G is defined as r(G) = {e(u)}. We consider properties of unchanging the radius of a graph under two different situations: deleting an arbitrary edge and deleting an arbitrary vertex. This paper gives the upper bounds for the number of edges in such graphs. Supported by VEGA grant No. 1/0084/08.     

Regularity inheritance in pseudorandom graphs

Advancing the sparse regularity method, we prove one‐sided and two‐sided regularity inheritance lemmas for subgraphs of bijumbled graphs, improving on results of Conlon, Fox, and Zhao. These inheritance lemmas also imply improved H‐counting lemmas for subgraphs of bijumbled graphs, for some H.     

On the editing distance of graphs

An edge‐operation on a graph G is defined to be either the deletion of an existing edge or the addition of a nonexisting edge. Given a family of graphs , the editing distance from G to is the smallest number of edge‐operations needed to modify G into a graph from . In this article, we fix a graph H and consider Forb(n, H), the set of all graphs on n vertices that have no induced copy of H. We provide bounds for the maximum over all n‐vertex graphs G of the editing distance from G to Forb(n, H), using an invariant we call the binary chromatic number of the graph H. We give asymptotically tight bounds for that distance when H is self‐complementary and exact results for several small graphs H. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:123–138, 2008     

Extremal results in sparse pseudorandom graphs

Szemerédi's regularity lemma is a fundamental tool in extremal combinatorics. However, the original version is only helpful in studying dense graphs. In the 1990s, Kohayakawa and Rödl proved an analogue of Szemerédi's regularity lemma for sparse graphs as part of a general program toward extending extremal results to sparse graphs. Many of the key applications of Szemerédi's regularity lemma use an associated counting lemma. In order to prove extensions of these results which also apply to sparse graphs, it remained a well-known open problem to prove a counting lemma in sparse graphs.     

The number of defective colorings of graphs on surfaces

A (k, 1)‐coloring of a graph is a vertex‐coloring with k colors such that each vertex is permitted at most 1 neighbor of the same color. We show that every planar graph has at least cρⁿ distinct (4, 1)‐colorings, where c is constant and ρ≈1.466 satisfies ρ³ = ρ² + 1. On the other hand for any ε>0, we give examples of planar graphs with fewer than c(? + ε)ⁿ distinct (4, 1)‐colorings, where c is constant and . Let γ(S) denote the chromatic number of a surface S. For every surface S except the sphere, we show that there exists a constant c′ = c′(S)>0 such that every graph embeddable in S has at least c′2ⁿ distinct (γ(S), 1)‐colorings. © 2010 Wiley Periodicals, Inc. J Graph Theory 28:129‐136, 2011     

Graph relations,clique divergence and surface triangulations

This work has two aims: first, we introduce a powerful technique for proving clique divergence when the graph satisfies a certain symmetry condition. Second, we prove that each closed surface admits a clique divergent triangulation. By definition, a graph is clique divergent if the orders of its iterated clique graphs tend to infinity, and the clique graph of a graph is the intersection graph of its maximal complete subgraphs. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Sparse partition universal graphs for graphs of bounded degree

In 1983, Chvátal, Trotter and the two senior authors proved that for any Δ there exists a constant B such that, for any n, any 2-colouring of the edges of the complete graph KN with N?Bn vertices yields a monochromatic copy of any graph H that has n vertices and maximum degree Δ. We prove that the complete graph may be replaced by a sparser graph G that has N vertices and edges, with N=⌈B^′n⌉ for some constant B^′ that depends only on Δ. Consequently, the so-called size-Ramsey number of any H with n vertices and maximum degree Δ is . Our approach is based on random graphs; in fact, we show that the classical Erd?s–Rényi random graph with the numerical parameters above satisfies a stronger partition property with high probability, namely, that any 2-colouring of its edges contains a monochromatic universal graph for the class of graphs on n vertices and maximum degree Δ.The main tool in our proof is the regularity method, adapted to a suitable sparse setting. The novel ingredient developed here is an embedding strategy that allows one to embed bounded degree graphs of linear order in certain pseudorandom graphs. Crucial to our proof is the fact that regularity is typically inherited at a scale that is much finer than the scale at which it is assumed.