Premium
Judicious partitions of bounded‐degree graphs
Author(s) -
Bollobás B.,
Scott A. D.
Publication year - 2004
Publication title -
journal of graph theory
Language(s) - Slovenian
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.10174
Subject(s) - mathematics , bounded function , combinatorics , degree (music) , discrete mathematics , graph , graph theory , mathematical analysis , physics , acoustics
We prove results on partitioning graphs G with bounded maximum degree. In particular, we provide optimal bounds for bipartitions V ( G ) = V 1 ∪ V 2 in which we minimize { e ( V 1 ), e ( V 2 )}. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 131–143, 2004