Weak Internal Partition of Regular Graphs

Abstract

An (s, t)-partition of a graph $G=(V,E)$ is a partition of $V=V_1\cup V_2$ such that $\delta (G[V_1])\ge s$ and $\delta (G[V_2])\ge t$. It has been conjectured that, for sufficiently large n, every d-regular graph of order n has a $(\lceil \frac{d}{2}\rceil , \lceil \frac{d}{2}\rceil )$-partition (called an internal partition). In this paper, we prove that every d-regular graph of order n has a $(\lceil \frac{d}{2}\rceil , \lfloor \frac{d}{2}\rfloor )$ partition (called a weak internal partition) for $d\le 9$ and sufficiently large n.

Keywords

Internal partition / External partition / Regular graph

References

[1] Ban A, Linial N. Internal partitions of regular graphs. J. Graph Theory. 2016, 83 1 5-18

[2] DeVos, M.: http://www.openproblemgarden.org/op/friendlypartitions (2009)

[3] Stiebitz M. Decomposing graphs under degree constraints. J. Graph Theory. 1996, 23 3 321-324

[4] Shafique KH, Dutton RD. On satisfactory partitioning of graphs. Congr. Numer.. 2002, 154 183-194

Funding

NNSF(11671376)