On the Loebl–Komlós–Sós conjecture

The Loebl–Komlós–Sós conjecture says that any graph G on n vertices with at least half of vertices of degree at least k contains each tree of size k. We prove that the conjecture is true for paths as well as for large values of k(k ≥ n − 3). © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 269–276, 2000     

Constructing trees in graphs with no K2,s

Let s ≥ 2 be an integer and k > 12(s ? 1) an integer. We give a necessary and sufficient condition for a graph G containing no K_2,s with and to contain every tree T of order k + 1. We then show that every graph G with no K_2,s and average degree greater than k ? 1 satisfies this condition, improving a result of Haxell, and verifying a special case of the Erd?s—Sós conjecture, which states that every graph of average degree greater than k ? 1 contains every tree of order k + 1. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 301–310, 2007     

The Erdős‐Sós Conjecture for trees of diameter four

The Erd?s‐Sós Conjecture is that a finite graph G with average degree greater than k ? 2 contains every tree with k vertices. Theorem 1 is a special case: every k‐vertex tree of diameter four can be embedded in G. A more technical result, Theorem 2, is obtained by extending the main ideas in the proof of Theorem 1. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 291–301, 2005     

Proof of a tiling conjecture of Komlós

A conjecture of Komlós states that for every graph H, there is a constant K such that if G is any n‐vertex graph of minimum degree at least (1 ? (1/χ_cr(H)))n, where χ_cr(H) denotes the critical chromatic number of H, then G contains an H‐matching that covers all but at most K vertices of G. In this paper we prove that the conjecture holds for all sufficiently large values of n. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 180–205, 2003     

The Erd s-Sós conjecture for graphs of girth 5

We prove that every graph of girth at least 5 with minimum degree δ k/2 contains every tree with k edges, whose maximum degree does not exceed the maximum degree of the graph. An immediate consequence is that the famous Erd s-Sós Conjecture, saying that every graph of order n with more than n(k − 1)/2 edges contains every tree with k edges, is true for graphs of girth at least 5.     

On an anti‐Ramsey problem of Burr,Erdős,Graham, and T. Sós

Given a graph L, in this article we investigate the anti‐Ramsey number χ_S(n,e,L), defined to be the minimum number of colors needed to edge‐color some graph G(n,e) with n vertices and e edges so that in every copy of L in G all edges have different colors. We call such a copy of L totally multicolored (TMC). In 7 among many other interesting results and problems, Burr, Erd?s, Graham, and T. Sós asked the following question: Let L be a connected bipartite graph which is not a star. Is it true then that In this article, we prove a slightly weaker statement, namely we show that the statement is true if L is a connected bipartite graph, which is not a complete bipartite graph. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 147–156, 2006     

The Erdös–Hajnal Conjecture—A Survey

The Erdös–Hajnal conjecture states that for every graph H, there exists a constant such that every graph G with no induced subgraph isomorphic to H has either a clique or a stable set of size at least . This article is a survey of some of the known results on this conjecture.     

Upper Bounds for Erdös–Hajnal Coefficients of Tournaments

A celebrated unresolved conjecture of Erdös and Hajnal (see Discrete Appl Math 25 (1989), 37–52) states that for every undirected graph H, there exists , such that every graph on n vertices which does not contain H as an induced subgraph contains either a clique or an independent set of size at least . In (Combinatorica (2001), 155–170), Alon et al. proved that this conjecture was equivalent to a similar conjecture about tournaments. In the directed version of the conjecture cliques and stable sets are replaced by transitive subtournaments. For a fixed undirected graph H, define to be the supremum of all ε for which the following holds: for some n₀ and every every undirected graph with vertices not containing H as an induced subgraph has a clique or independent set of size at least . The analogous definition holds if H is a tournament. We call the Erdös–Hajnal coefficient of H. The Erdös–Hajnal conjecture is true if and only if for every H. We prove in this article that:

• the Erdös–Hajnal coefficient of every graph H is at most ,
• there exists such that the Erdös–Hajnal coefficient of almost every tournament T on k vertices is at most , i.e. the proportion of tournaments on k vertices with the coefficient exceeding goes to 0 as k goes to infinity.

     

Strengthening Erdös–Pósa property for minor‐closed graph classes

Let ?? and ?? be graph classes. We say that ?? has the Erd?s–Pósa property for ?? if for any graph G ∈??, the minimum vertex covering of all ??‐subgraphs of G is bounded by a function f of the maximum packing of ??‐subgraphs in G (by ??‐subgraph of G we mean any subgraph of G that belongs to ??). Robertson and Seymour [J Combin Theory Ser B 41 (1986), 92–114] proved that if ?? is the class of all graphs that can be contracted to a fixed planar graph H, then ?? has the Erd?s–Pósa property for the class of all graphs with an exponential bounding function. In this note, we prove that this function becomes linear when ?? is any non‐trivial minor‐closed graph class. © 2010 Wiley Periodicals, Inc. J Graph Theory 66:235‐240, 2011     

Tree embeddings

We give a general theorem on embedding trees in graphs with certain expanding properties. As an application, we show that for r = ⌊t/18⌋, any graph with average degree greater than t − 1 that does not contain a copy of K_2,r contains every tree with t edges as a subgraph. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 121–130, 2001     

The Erdős–Pósa Property for Long Circuits

For an integer ? at least 3, we prove that if G is a graph containing no two vertex‐disjoint circuits of length at least ?, then there is a set X of at most vertices that intersects all circuits of length at least ?. Our result improves the bound due to Birmelé, Bondy, and Reed (The Erd?s–Pósa property for long circuits, Combinatorica 27 (2007), 135–145) who conjecture that ? vertices always suffice.     

Pósa's conjecture for graphs of order at least 2 × 108

In 1962 Pósa conjectured that every graph G on n vertices with minimum degree \begin{align*}\delta(G)\ge \frac{2}{3}n\end{align*} contains the square of a hamiltonian cycle. In 1996 Fan and Kierstead proved the path version of Pósa's Conjecture. They also proved that it would suffice to show that G contains the square of a cycle of length greater than \begin{align*}\frac{2}{3}n\end{align*}. Still in 1996, Komlós, Sárközy, and Szemerédi proved Pósa's Conjecture, using the Regularity and Blow‐up Lemmas, for graphs of order n ≥ n₀, where n₀ is a very large constant. Here we show without using these lemmas that n₀:= 2 × 10⁸ is sufficient. We are motivated by the recent work of Levitt, Sárközy and Szemerédi, but our methods are based on techniques that were available in the 90's. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

On Seymour’s strengthening of Hadwiger’s conjecture for graphs with certain forbidden subgraphs

Let H be a set of graphs. A graph is called H-free if it does not contain a copy of a member of H as an induced subgraph. If H is a graph then G is called H-free if it is {H}-free. Plummer, Stiebitz, and Toft proved that, for every -free graph H on at most four vertices, every -free graph G has a collection of ⌈|V(G)|/2⌉ many pairwise adjacent vertices and edges (where a vertexvand an edgeeare adjacent if v is disjoint from the set V(e) of endvertices of e and adjacent to some vertex of V(e), and two edgeseandfare adjacent if V(e) and V(f) are disjoint and some vertex of V(e) is adjacent to some vertex of V(f)). Here we generalize this statement to -free graphs H on at most five vertices.     

A Tighter Erdős‐Pósa Function for Long Cycles

We prove that there exists a bivariate function f with such that for every natural k and ?, every graph G has at least k vertex‐disjoint cycles of length at least ? or a set of at most vertices that meets all cycles of length at least ?. This improves a result by Birmelé et al. (Combinatorica, 27 (2007), 135–145), who proved the same result with .     

A generalization of the three-dimensional Bernfeld–Haddock conjecture and its proof

Consider the following system of delay differential equations

where r₁, r₂ and r₃ are positive constants, F, GC(R¹), and F is nondecreasing on R¹. These systems have important practical applications and also are a three-dimensional generalization of the Bernfeld–Haddock conjecture. In this paper, by using comparative technique, we obtain the asymptotic behavior of solutions that each bounded solution of the systems tends to a constant vector under a desirable condition.     

On the Brown–Shields conjecture for cyclicity in the Dirichlet space

Let be the Dirichlet space, namely the space of holomorphic functions on the unit disk whose derivative is square-integrable. We establish a new sufficient condition for a function to be cyclic, i.e. for to be dense in . This allows us to prove a special case of the conjecture of Brown and Shields that a function is cyclic in iff it is outer and its zero set (defined appropriately) is of capacity zero.     

Milnor numbers, spanning trees, and the Alexander–Conway polynomial

We study relations between the Alexander–Conway polynomial _L and Milnor higher linking numbers of links from the point of view of finite-type (Vassiliev) invariants. We give a formula for the first non-vanishing coefficient of _L of an m-component link L all of whose Milnor numbers μ_i1…ip vanish for pn. We express this coefficient as a polynomial in Milnor numbers of L. Depending on whether the parity of n is odd or even, the terms in this polynomial correspond either to spanning trees in certain graphs or to decompositions of certain 3-graphs into pairs of spanning trees. Our results complement determinantal formulas of Traldi and Levine obtained by geometric methods.     

On Fraïssé’s conjecture for linear orders of finite Hausdorff rank

We prove that the maximal order type of the wqo of linear orders of finite Hausdorff rank under embeddability is φ₂(0), the first fixed point of the ε-function. We then show that Fraïssé’s conjecture restricted to linear orders of finite Hausdorff rank is provable in  +“φ₂(0) is well-ordered” and, over , implies  +“φ₂(0) is well-ordered”.