{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:37:22Z","timestamp":1787323042669,"version":"build-2736575974"},"reference-count":12,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2011,1,1]]},"abstract":"<jats:p>We consider the problem of partitioning the vertices of an [Formula: see text]-vertex graph with maximum degree [Formula: see text] into [Formula: see text] classes [Formula: see text] of size at most [Formula: see text] in a way that minimizes the number of pairs [Formula: see text] for which there is an edge between [Formula: see text] and [Formula: see text]. We show that there is always such a partition with [Formula: see text] adjacent pairs, and this bound is tight. This problem is related to questions about the depth of certain graph embeddings, which have been used in the study of the complexity of subgraph and constraint satisfaction problems. (A corrected version of this paper has been appended to the originally posted pdf.)<\/jats:p>","DOI":"10.1137\/100812653","type":"journal-article","created":{"date-parts":[[2011,6,28]],"date-time":"2011-06-28T02:43:19Z","timestamp":1309228999000},"page":"631-644","source":"Crossref","is-referenced-by-count":6,"title":["Sparse Balanced Partitions and the Complexity of Subgraph Problems"],"prefix":"10.1137","volume":"25","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"D\u00e1niel","family":"Marx","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2011,6,27]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20143"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(78)90059-6"},{"key":"R4","first-page":"1","volume":"11","author":"Bodlaender H. L.","year":"1993","journal-title":"Acta Cybernet.","ISSN":"https:\/\/id.crossref.org\/issn\/0324-721X","issn-type":"print"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"H. L. Bodlaender, Treewidth: Algorithmic techniques and results, in\n                      Mathematical Foundations of Computer Science 1997\n                      , Lecture Notes in Comput. Sci.  1295, Springer, Berlin, 1997, pp.\u00a019\u201336.","DOI":"10.1007\/BFb0029946"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2009.10.010"},{"key":"R7","unstructured":"J. Chen, B. Chor, M. Fellows, X. Huang, D. Juedes, I. Kanj and G. Xia, Tight lower bounds for certain parameterized NP-hard problems, in  Proceedings of 19th Annual IEEE Conference on Computational Complexity, IEEE, Washington, DC, 2004, pp.\u00a0150\u2013160."},{"key":"R8","doi-asserted-by":"crossref","unstructured":"J. Chen, X. Huang, I. A. Kanj and G. Xia, Linear FPT reductions and computational lower bounds, in  Proceedings of the 36th Annual ACM Symposium on Theory of Computing, ACM, New York, 2004, pp.\u00a0212\u2013221.","DOI":"10.1145\/1007352.1007391"},{"key":"R9","unstructured":"E. C. Freuder, Complexity of k-tree structured constraint satisfaction problems, in  Proceedings of the Eighth National Conference on Artificial Intelligence, Boston, MA, 1990, pp.4\u20139."},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2008.06.004"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2010.v006a005"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/100812653","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:38:52Z","timestamp":1787319532000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/100812653"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1,1]]},"references-count":12,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,1,1]]}},"alternative-id":["10.1137\/100812653"],"URL":"https:\/\/doi.org\/10.1137\/100812653","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1,1]]}}}