Advertisement
Published in:
01-05-2016
On judicious partitions of graphs
Published in: Journal of Combinatorial Optimization | Issue 4/2016
Log inActivate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
Let \(k, m\) be positive integers, let \(G\) be a graph with \(m\) edges, and let \(h(m)=\sqrt{2m+\frac{1}{4}}-\frac{1}{2}\). Bollobás and Scott asked whether \(G\) admits a \(k\)-partition \(V_{1}, V_{2}, \ldots , V_{k}\) such that \(\max _{1\le i\le k} \{e(V_{i})\}\le \frac{m}{k^2}+\frac{k-1}{2k^2}h(m)\) and \(e(V_1, \ldots , V_k)\ge {k-1\over k} m +{k-1\over 2k}h(m) -\frac{(k-2)^{2}}{8k}\). In this paper, we present a positive answer to this problem on the graphs with large number of edges and small number of vertices with degrees being multiples of \(k\). Particularly, if \(d\) is not a multiple of \(k\) and \(G\) is \(d\)-regular with \(m\ge {9\over 128}k^4(k-2)^2\), then \(G\) admits a \(k\)-partition as desired. We also improve an earlier result by showing that \(G\) admits a partition \(V_{1}, V_{2}, \ldots , V_{k}\) such that \(e(V_{1},V_{2},\ldots ,V_{k})\ge \frac{k-1}{k}m+\frac{k-1}{2k}h(m)-\frac{(k-2)^{2}}{2(k-1)}\) and \(\max _{1\le i\le k}\{e(V_{i})\}\le \frac{m}{k^{2}}+\frac{k-1}{2k^{2}}h(m)\).