Search

Kim, Kühn, Osthus and Tyomkyn (Trans. Amer. Math. Soc. 371 (2019), 4655–4742) greatly extended the well-known blow-up lemma of Komlós, Sárközy and Szemerédi by proving a 'blow-up lemma for approximate decompositions' which states that multipartite quasirandom graphs can be almost decomposed into any collection of bounded degree graphs with the same multipartite structure and slightly fewer edges. This result has already been used by Joos, Kim, Kühn and Osthus to prove the tree packing conjecture due to Gyárfás and Lehel from 1976 and Ringel's conjecture from 1963 for bounded degree trees as well as implicitly in the recent resolution of the Oberwolfach problem (asked by Ringel in 1967) by Glock, Joos, Kim, Kühn and Osthus. Here we present a new and significantly shorter proof of the blow-up lemma for approximate decompositions. In fact, we prove a more general theorem that yields packings with stronger quasirandom properties which is useful for potential applications. [ABSTRACT FROM AUTHOR]

Robertson and Seymour proved that the family of all graphs containing a fixed graph H as a minor has the Erdős-Pósa property if and only if H is planar. We show that this is no longer true for the edge version of the Erdős-Pósa 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. [ABSTRACT FROM AUTHOR]

We show that a quasirandom k-uniform hypergraph G has a tight Euler tour subject to the necessary condition that k divides all vertex degrees. The case when G is complete confirms a conjecture of Chung, Diaconis and Graham from 1989 on the existence of universal cycles for the k-subsets of an n-set. [ABSTRACT FROM AUTHOR]

A (Γ1,Γ2)-labeled graph is an oriented graph with its edges labeled by elements of the direct sum of two groups Γ1,Γ2. A cycle in such a labeled graph is (Γ1,Γ2)-non-zero if it is non-zero in both coordinates. Our main result is a generalization of the Flat Wall Theorem of Robertson and Seymour to (Γ1,Γ2)-labeled graphs. As an application, we determine all canonical obstructions to the Erdős–Pósa property for (Γ1,Γ2)-non-zero cycles in (Γ1,Γ2)-labeled graphs. The obstructions imply that the half-integral Erdős–Pósa property always holds for (Γ1,Γ2)-non-zero cycles. Moreover, our approach gives a unified framework for proving packing results for constrained cycles in graphs. For example, as immediate corollaries we recover the Erdős–Pósa property for cycles and S-cycles and the half-integral Erdős–Pósa property for odd cycles and odd S-cycles. Furthermore, we recover Reed's Escher-wall Theorem. We also prove many new packing results as immediate corollaries. For example, we show that the half-integral Erdős–Pósa property holds for cycles not homologous to zero, odd cycles not homologous to zero, and S-cycles not homologous to zero. Moreover, the (full) Erdős–Pósa property holds for S1-S2-cycles and cycles not homologous to zero on an orientable surface. Finally, we also describe the canonical obstructions to the Erdős–Pósa property for cycles not homologous to zero and for odd S-cycles. [ABSTRACT FROM AUTHOR]

We prove that the set of long cycles has the edge-Erdős-Pósa property: for every fixed integer ℓ ≥ 3 and every k ∈ ℕ, every graph G either contains k edge-disjoint cycles of length at least ℓ (long cycles) or an edge set X of size O(k2 logk+kℓ) such that G—X does not contain any long cycle. This answers a question of Birmelé, Bondy, and Reed (Combinatorica 27 (2007), 135-145). [ABSTRACT FROM AUTHOR]

For a fixed degree sequence $${\mathcal {D}}=(d_1,\ldots ,d_n)$$ , let $$G({\mathcal {D}})$$ be a uniformly chosen (simple) graph on $$\{1,\ldots ,n\}$$ where the vertex i has degree $$d_i$$ . In this paper we determine whether $$G({\mathcal {D}})$$ has a giant component with high probability, essentially imposing no conditions on $${\mathcal {D}}$$ . We simply insist that the sum of the degrees in $${\mathcal {D}}$$ which are not 2 is at least $$\lambda (n)$$ for some function $$\lambda $$ going to infinity with n. This is a relatively minor technical condition, and when $${\mathcal {D}}$$ does not satisfy it, both the probability that $$G({\mathcal {D}})$$ has a giant component and the probability that $$G({\mathcal {D}})$$ has no giant component are bounded away from 1. [ABSTRACT FROM AUTHOR]

The maximum number vertices of a graph G inducing a 2-regular subgraph of G is denoted by $$c_\mathrm{ind}(G)$$ . We prove that if G is an r-regular graph of order n, then $$c_\mathrm{ind}(G) \ge \frac{n}{2(r-1)} + \frac{1}{(r-1)(r-2)}$$ and we prove that if G is a cubic, claw-free graph on order n, then $$c_\mathrm{ind}(G) > \frac{13}{20}n$$ and this bound is asymptotically best possible. [ABSTRACT FROM AUTHOR]

The boxicity of a graph G is the least integer d such that G has an intersection model of axis-aligned d-dimensional boxes. Boxicity, the problem of deciding whether a given graph G has boxicity at most d, is NP-complete for every fixed $$d \ge 2$$ . We show that Boxicity is fixed-parameter tractable when parameterized by the cluster vertex deletion number of the input graph. This generalizes the result of Adiga et al. (2010), that Boxicity is fixed-parameter tractable in the vertex cover number. Moreover, we show that Boxicity admits an additive 1-approximation when parameterized by the pathwidth of the input graph. Finally, we provide evidence in favor of a conjecture of Adiga et al. (2010) that Boxicity remains NP-complete even on graphs of constant treewidth. [ABSTRACT FROM AUTHOR]

If $$G$$ is a claw-free Hamiltonian graph of order $$n$$ and maximum degree $$\Delta $$ with $$\Delta \ge 24$$ , then $$G$$ has cycles of at least $$\min \left\{ n,\left\lceil \frac{3}{2}\Delta \right\rceil \right\} -2$$ many different lengths. [ABSTRACT FROM AUTHOR]