The DOI matches its Crossref record; 6 of the 6 references it cites were found in a registry or an index.
Bisection of Circle Colorings
Abstract
Consider $2n$ beads of k colors arranged on a necklace, using $2a$, beads of color i. A bisection is a set of disjoint strings (“intervals”) of beads whose union captures half the beads of each color. We prove that any arrangement with k colors has a bisection using at most $\lceil k / 2 \rceil $ intervals. In addition, if k is odd, an endpoint of one interval can be specified arbitrarily. The result is best possible. For fixed k, there is a polynomial-time algorithm to find such a bisection; it runs in $O ( n^{k - 2} )$ for $k\geqq 3$. We consider continuous and linear versions of the problem and use them to obtain applications in geometry, VLSI circuit design, and orthogonal functions.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“A well-known theorem of Goldberg and West states that two thieves can always split a necklace containing an even number of beads from each of k types fairly by at most k cuts.”
From Necklace Bisection with One Cut Less than Needed (2008) · cites this paper as [6]
Citations
Cites
Villani, V (2011) · Springer eBooks · doi:10.1007/978-3-642-11102-0 · Cited by 564
Some Unsolved Problems in Plane Geometry
Klee, V. L. (1979) · Mathematics Magazine · doi:10.1080/0025570x.1979.11976769 · Cited by 48
Inscribed Squares in Plane Curves
Jerrard, R. (1961) · Transactions of the American Mathematical Society · doi:10.1090/s0002-9947-1961-0120604-3 · Cited by 31
A layout strategy for VLSI which is provably good (Extended Abstract)
Leighton, F. T. (1982) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/800070.802180 · Cited by 28
On the enumeration of cross-sections
James, I. M., & Thomas, E. (1966) · Topology · doi:10.1016/0040-9383(66)90012-7 · Cited by 15
How to assemble tree machines (Extended Abstract)
Bhatt, S. N., & Leiserson, C. E. (1982) · Proceedings of the fourteenth annual ACM symposium on Theory of computing · doi:10.1145/800070.802179
Research works printed but not linked: 1
- 10.2307/2690274 · doi:10.2307/2690274
Cited by
Alon, N. (1987) · Advances in Mathematics · doi:10.1016/0001-8708(87)90055-7 · Cited by 136
The Chromatic Number of Kneser Hypergraphs
Alon, N., Frankl, P., & Lovász, L. (1986) · Transactions of the American Mathematical Society · doi:10.1090/s0002-9947-1986-0857448-8 · Cited by 127
The Borsuk-Ulam Theorem and Bisection of Necklaces
Alon, N., & West, D. B. (1986) · Proceedings of the American Mathematical Society · doi:10.1090/s0002-9939-1986-0861764-9 · Cited by 88
Self-citationThe discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
Loera, J. A. D., Goaoc, X., Meunier, F., & Mustafa, N. H. (2019) · Bulletin of the American Mathematical Society · doi:10.1090/bull/1653 · Cited by 85
Consensus-halving via theorems of Borsuk-Ulam and Tucker
Simmons, F. W., & Su, F. E. (2003) · Mathematical Social Sciences · doi:10.1016/s0165-4896(02)00087-2 · Cited by 74
Metadata
- Authors
- Goldberg, C. H., & West, D. B.
- ORCID
- West, Douglas B.
- Venue
- SIAM Journal on Algebraic Discrete Methods
- Published
- 1985-01
- Volume
- 6
- Issue
- 1
- Pages
- 93-106
- ISSN
- 0196-5212 (ISSN-L)
- 2168-345X
- OpenAlex
- W2016462171
- Semantic Scholar
- 6b74516001b73a690e4c4ef01ac024254f312f4e
- Cited by
- 69
- References
- 4
- Citations by year
- 2026: 4 · 2025: 3 · 2024: 2 · 2023: 3 · 2022: 5 · 2021: 3 · 2020: 4 · 2019: 4 · 2018: 1 · 2017: 1 · 2016: 2 · 2015: 3 · 2014: 1 · 2012: 1
- FWCI
- 1.58
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- SIAM Journal on Algebraic and Discrete Methods (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Mathematics › Discrete Mathematics and Combinatorics › Advanced Combinatorial Mathematics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Advanced Graph Theory Research
- Keywords
- interval bisection, polynomial-time algorithms, VLSI design, orthogonal functions, combinatorial geometry
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Bisection of Circle Colorings. https://app.cochat.ai/papers/10.1137/0606010
- The paper
- Goldberg, C. H., & West, D. B. (1985). Bisection of Circle Colorings. SIAM Journal on Algebraic Discrete Methods. https://doi.org/10.1137/0606010
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.
