Premium
On a Problem of Judicious k ‐Partitions of Graphs
Author(s) -
Hou Jianfeng,
Zeng Qinghou
Publication year - 2017
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22094
Subject(s) - combinatorics , mathematics , conjecture , partition (number theory) , vertex (graph theory) , graph , discrete mathematics
For positive integers k ≥ 2 and m , letg k ( m )be the smallest integer such that for each graph G with m edges there exists a k ‐partition V ( G ) = V 1 ∪ … ∪ V kin which each V i contains at mostg k ( m )edges. Bollobás and Scott showed thatg k ( m ) ≤ m k 2 + k − 1 2 k 22 m + 1 / 4 − 1 / 2 . Ma and Yu posed the following problem: is it true that the limsup ofm k 2 + k − 1 2 k 22 m − g k ( m )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.