Weak internal partition of regular graphs (Q1690616): Difference between revisions

An internal partition of an \(n\)-vertex graph \(G\) is a partition of \(V(G)\) such that every vertex has at least as many neighbors in its own part as in the other part. An \((s,t)\)-partition of graph \(G\) is a partition of \(V(G)=V_1 \cup V_2\) such that \(\delta(G[V_1])\geq s\) and \(\delta(G[V_2])\geq t\). An internal partition of \(d\)-regular graph \(G\) is also a \((\lceil \frac{d}{2} \rceil,\lceil \frac{d}{2} \rceil)\)-partition of \(G\). It has been conjectured by \textit{M. DeVos} [``Friendly partitions'' (2009), \url{http://www.openproblemgarden.org/op/friendly_partitions}] that for every \(d\) there is an \(n_0\) such that every \(d\)-regular graph with at least \(n_0\) vertices has an internal partition. The conjecture is still open for \(d=5\) and \(d \geq 7\). A weak version of the conjecture is that every \(d\)-regular graph with enough vertices has a \((\lceil \frac{d}{2} \rceil,\lfloor \frac{d}{2} \rfloor)\)-partition. The case for \(d=2k\) has been settled by \textit{M. Stiebitz} [J. Graph Theory 23, No. 3, 321--324 (1996; Zbl 0865.05058)]. In this paper, the odd case is considered. The authors solve the problem in the weak version of the conjecture for the cases \(d=5,7\) and \(9\).