AbstractIn 1975, Erdős asked for the maximum number of edges that an n-vertex graph can have if it does not contain two edge-disjoint cycles on the same vertex set. This problem has since been reiterated by several authors including Bollobás in 1978, Pyber, Rödl, and Szemerédi in 1995, and Chen, Erdős, and Staton in 1996. We asymptotically resolve this long-standing problem in a strong form, ...
AbstractA classical result of Hajnal and Thomassen asserts that for every$k$ there exists $K$ such that the vertices of every $K$-connected graph can be partitioned into two sets inducing $k$-connected subgraphs. Moreover they showed $K=O(k)$. There is now a whole area of combinatorial problems concerned with questions of this type; namely, to understand whether for a certain (di)graph property...