The problem of compatible representatives
<|reference_start|>The problem of compatible representatives: The purpose of this note is to attach a name to a natural class of combinatorial problems and to point out that this class includes many important special cases. We also show that a simple problem of placing nonoverlapping labels on a rectangular map is NP-complete.<|reference_end|>
@article{knuth1992the,
    title={The problem of compatible representatives},
    author={Donald E. Knuth, Arvind Raghunathan},
    journal={SIAM J. Discrete Math. 5 (1992), no. 3, 422--427},
    year={1992},
    number={Knuth migration 11/2004},
    archivePrefix={arXiv},
    eprint={cs/9301116},
    primaryClass={cs.DS math.CO}
}