BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
We prove that if G is a k-partite graph on n vertices in which all of the parts have order at most n/r and every vertex is adjacent to at least a 1−1/r+o(1) proportion of the vertices in every other part, then G contains the (r−1)-st power of a Hamiltonian cycle
Let G=(V,E) be an n-vertex edge-colored graph. In 2013, H. Li proved that if every vertex v∈V is incident to at least (n+1)/2 distinctly colored edges, then G admits a rainbow triangle. We prove that the same hypothesis ensures a rainbow ℓ-cycle Cℓ whenever n≥432ℓ. This result is sharp for all odd integers ℓ≥3, and extends earlier work of the authors for when ℓ is even.
Let Tk be the transitive tournament on k vertices. We show that every oriented graph on n=4m vertices with minimum total degree (11/12+o(1))n can be partitioned into vertex disjoint T4's, and this bound is asymptotically tight. We also improve the best known bound on the minimum total degree for partitioning oriented graphs into vertex disjoint Tk's.
The Hajnal--Szemerédi theorem states that for any integer r≥1 and any multiple n of r, if G is a graph on n vertices and δ(G)≥(1−1/r)n, then G can be partitioned into n/r vertex-disjoint copies of the complete graph on r vertices. We prove a very general analogue of this result for directed graphs: for any integer r≥4 and any sufficiently large multiple n of r, if G is a directed graph on n vertices and every vertex is incident to at least 2(1−1/r)n−1 directed edges, then G can be partitioned into n/r vertex-disjoint subgraphs of size r each of which contain every tournament on r vertices. A related Turán-type result is also proven.
We study the minimum degree necessary to guarantee the existence of perfect and almost-perfect triangle-tilings in an n-vertex graph G with sublinear independence number. In this setting, we show that if δ(G)≥n/3+o(n) then G has a triangle-tiling covering all but at most four vertices. Also, for every r≥5, we asymptotically determine the minimum degree threshold for a perfect triangle-tiling under the additional assumptions that G is Kr-free and n is divisible by 3.
In 1963, Corrádi and Hajnal settled a conjecture of Erdős by proving that, for all k≥1, any graph G with ∣G∣≥3k and minimum degree at least 2k contains k vertex-disjoint cycles. In 2008, Finkel proved that for all k≥1, any graph G with ∣G∣≥4k and minimum degree at least 3k contains k vertex-disjoint chorded cycles. Finkel's result was strengthened by Chiba, Fujita, Gao, and Li in 2010, who showed, among other results, that for all k≥1, any graph G with ∣G∣≥4k and minimum Ore-degree at least 6k−1 contains k vertex-disjoint cycles. We refine this result, characterizing the graphs G with ∣G∣≥4k and minimum Ore-degree at least 6k−2 that do not have k disjoint chorded cycles.
Let n be sufficiently large and suppose that G is a digraph on n vertices where every vertex has in- and outdegree at least n/2. We show that G contains every orientation of a Hamilton cycle except, possibly, the antidirected one. The antidirected case was settled by DeBiasio and Molla, where the threshold is n/2+1. Our result is best possible and improves on an approximate result by Häggkvist and Thomason.
An edge-ordering of a graph G=(V,E) is a bijection ϕ:E→{1,2,...,∣E∣}. Given an edge-ordering, a sequence of edges P=e1,e2,...,ek is an increasing path if it is a path in G which satisfies ϕ(ei)<ϕ(ej) for all i<j. For a graph G, let f(G) be the largest integer ℓ such that every edge-ordering of G contains an increasing path of length ℓ. The parameter f(G) was first studied for G=Kn and has subsequently been studied for other families of graphs. This paper gives bounds on f for the hypercube and the random graph G(n,p).
In 1960, Ghouila-Houri extended Dirac's theorem to directed graphs by proving that if D is a directed graph on n vertices with minimum out-degree and in-degree at least n/2 (i.e. minimum semi-degree at least n/2), then D contains a directed Hamiltonian cycle. Of course there are other orientations of a cycle in a directed graph and it is not clear that the semi-degree threshold for the directed Hamiltonian cycle is the same as the semi-degree threshold for some other orientation. In 1980, Grant initiated the problem of determining the minimum semi-degree threshold for the anti-directed Hamiltonian cycle (an orientation in which consecutive edges alternate direction). We prove that for sufficiently large even n, if D is a directed graph on n vertices with minimum semi-degree at least n/2+1, then D contains an anti-directed Hamiltonian cycle. This result is sharp.
Hajnal and Szemeredi proved that every graph G with |G|=ks and minimum degree at least k(s-1) contains k vertex disjoint s-cliques; moreover this degree bound is optimal. We extend their theorem to directed graphs by showing that every directed graph D with |D|=ks and minimum (total) degree at least 2k(s-1)-1 contains k vertex disjoint transitive tournaments on s vertices. Our result implies the Hajnal-Szemeredi Theorem, and the degree bound is optimal. We also make some conjectures regarding even more general results for multigraphs and partitioning into other tournaments. One of these conjectures is supported by an asymptotic result.
For k∈N, Corrádi and Hajnal proved that every graph G on 3k vertices with minimum degree δ(G)≥2k has a C3-factor, i.e., a partitioning of the vertex set so that each part induces the 3-cycle C3. Wang proved that every directed graph G on 3k vertices with minimum total degree δt(G):=minv∈V(deg−(v)+deg+(v))≥3(3k−1)/2 has a C3-factor, where C3 is the directed 3-cycle. The degree bound in Wang's result is tight. However, our main result implies that for all integers a≥1 and b≥0 with a+b=k, every directed graph G on 3k vertices with minimum total degree δt(G)≥4k−1 has a factor consisting of a copies of T3 and b copies of C3, where T3 is the transitive tournament on three vertices. In particular, using b=0, there is a T3-factor of G, and using a=1, it is possible to obtain a C3-factor of G by reversing just one edge of G. All these results are phrased and proved more generally in terms of undirected multigraphs. We conjecture that every directed graph G on 3k vertices with minimum semidegree δ0(G):=minv∈Vmin(deg−(v),deg+(v))≥2k has a C3-factor, and prove that this is asymptotically correct.
In 2006, Kühn and Osthus showed that if a 3-graph H on n vertices has minimum co-degree at least (1/4 +o(1))n and n is even then H has a loose Hamilton cycle. In this paper, we prove that the minimum co-degree of n/4 suffices. The result is tight.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.