Disjoint subgraphs of large maximum degree

The authors study the minimum size \(b(n,m)\) of a graph \(G=(V,E)\) such that for every partition \(V=A\cup B\) either \(\Delta(G[A])\geq n\) or \(\Delta(G[B])\geq m\) and the minimum size \(q(n,j,l)\) of a graph \(G=(V,E)\) having \(n+j+l\) vertices such that \(\Delta(G[A])\geq n\) for every set \(A\subseteq V\) with \(|A|=n+j\). Erdős conjectured \(b(n,n)={2n+1\choose 2}-{n\choose 2}\). As a first result the authors give a probabilistic construction of a counterexample to this conjecture whose order is smaller than the order of the previously known counterexamples. They prove \(b(n,m)=2nm-m^2+O(\sqrt{m})n\) for \(n\geq m\geq 1\), \(b(n,1)=4n-2\) for \(n\geq 7\) and \(6n-110\leq b(n,2)\leq 6n-1\) for \(n\geq 2\). Furthermore, they prove \[ q(n,j,l)=(1+o(1))(l+1)n\left( 1+\frac{l}{2n+2j}\right)\quad \text{for}\quad l=o(n(n+j)/\log(n)) \] which disproves a conjectures of Erdős, Reid, Schelp and Staton. Some more related results are presented. The proofs rely on the probabilistic method and explicit constructions.

Recommendations

Cited in

(2)

This page was built for publication: Disjoint subgraphs of large maximum degree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1598819)