On a Problem of Judicious k‐Partitions of Graphs |
| |
Authors: | Jianfeng Hou Qinghou Zeng |
| |
Institution: | CENTER FOR DISCRETE MATHEMATICS, FUZHOU UNIVERSITY, FUJIAN, P. R. CHINA |
| |
Abstract: | For positive integers and m , let be the smallest integer such that for each graph G with m edges there exists a k‐partition in which each contains at most edges. Bollobás and Scott showed that . Ma and Yu posed the following problem: is it true that the limsup of tends to infinity as m tends to infinity? They showed it holds when k is even, establishing a conjecture of Bollobás and Scott. In this article, we solve the problem completely. We also present a result by showing that every graph with a large k‐cut has a k‐partition in which each vertex class contains relatively few edges, which partly improves a result given by Bollobás and Scott. |
| |
Keywords: | graph max‐cut judicious partition |
|
|