Coloring Block Designs is NP-Complete

descriptionPublicationkeyboard_double_arrow_right Article 01 Sep 1982 English Publisher:Society for Industrial & Applied Mathematics (SIAM)Journal:SIAM Journal on Algebraic Discrete Methods, volume 3, pages 305-307 (issn: 0196-5212, eissn: 2168-345X,

Copyright policy )

Authors: Colbourn, Charles J.; Colbourn, Marlene J.; Phelps, Kevin T.; Rödl, Vojtěch;

doi: 10.1137/0603031

Coloring Block Designs is NP-Complete

- Summary
- Subjects
- Metrics

Abstract

Coloring partial Steiner triple systems is shown to be NP-complete. Together with an embedding technique of Lindner, this provides a short proof of the NP-completeness of coloring block designs.

Keywords

Coloring of graphs and hypergraphs, Triple systems, chromatic number, Analysis of algorithms and problem complexity, partial Steiner triple systems, NP-complete problems, Designs and configurations

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	8
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average