Search

The Oberwolfach problem, posed by Ringel in 1967, asks for a decomposition of K2n+1 into edge-disjoint copies of a given 2-factor. We show that this can be achieved for all large n. We actually prove a significantly more general result, which allows for decompositions into more general types of factors. In particular, this also resolves the Hamilton-Waterloo problem for large n. [ABSTRACT FROM AUTHOR]

For a collection G={G1,⋯,Gs} of not necessarily distinct graphs on the same vertex set V, a graph H with vertices in V is a G‐transversal if there exists a bijection ϕ:E(H)→[s] such that e∈E(Gϕ(e)) for all e∈E(H). We prove that for |V|=s⩾3 and δ(Gi)⩾s/2 for each i∈[s], there exists a G‐transversal that is a Hamilton cycle. This confirms a conjecture of Aharoni. We also prove an analogous result for perfect matchings. [ABSTRACT FROM AUTHOR]

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 O(n/logn). 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 no(1)≤Δ≤cn/logn 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 Δ. [ABSTRACT FROM AUTHOR]

We prove that for every graph, any vertex subset S, and given integers [ABSTRACT FROM AUTHOR]

We show the following for every sufficiently connected graph G, any vertex subset S of G, and given integer k: there are k disjoint odd cycles in G each containing a vertex of S or there is set X of at most [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]

For a graph G, let vs(G) be the size of a largest induced matching of G. We prove that vs(G) ≥ n(G)/(⌈Δ/2⌇+1)(⌈Δ/2⌇+1) for every graph of sufficiently large maximum degree Δ and without isolated vertices. This bound is sharp. Moreover, there is a polynomial-time algorithm which computes induced matchings of the size stated above. [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]

For a graph G, let νs(G) be the strong matching number of G. We prove the sharp bound νs(G) ≥ n(G)/9 for every graph G of maximum degree at most 4 and without isolated vertices that does not contain a certain blown-up 5-cycle as a component. This result implies a strengthening of a consequence, namely, νs(G) ≥ m(G)/18 for such graphs and νs(G) ≥ m(G)/20 for a graph of maximum degree 4, of the well-known conjecture of Erdős and Nešetřil, which says that the strong chromatic index χ's(G) of a graph G is at most 5/4Δ(G)², since νs(G) ≥ m(G)/χ's(G) and n(G) ≥ 2m(G)/Δ(G). This bound is tight and the proof implies a polynomial time algorithm to find an induced matching of this size. [ABSTRACT FROM AUTHOR]

We investigate the threshold probability for connectivity of sparse graphs under weak assumptions. As a corollary this completely solves the problem for Cartesian powers of arbitrary graphs. In detail, let G be a connected graph on k vertices, Gn be the nth Cartesian power of G, αi be the number of vertices of degree i of G, λ be a positive real number, and Gnp be the graph obtained from Gn by deleting every edge independently with probability 1 − p. If ∑i αi(1 − p)i = λ 1/n , then limn→∞ ℙ[Gnp is connected] = exp(−λ). This result extends known results for regular graphs. The main result implies that the threshold probability does not depend on the graph structure of G itself, but only on the degree sequence of the graph. [ABSTRACT FROM AUTHOR]