Coloring Block Designs is NP-Complete

DOI10.1137/0603031zbMath0497.05022OpenAlexW2032050111MaRDI QIDQ3960717

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

Publication date: 1982

Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0603031

zbMATH Keywords

NP-complete problemschromatic numberpartial Steiner triple systems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Triple systems (05B07) Designs and configurations (05B99)

Related Items

The strong chromatic number of partial triple systems ⋮ On the algorithmic complexity of coloring simple hypergraphs and Steiner triple systems ⋮ Coloring face-hypergraphs of graphs on surfaces

Cites Work

• A partial Steiner triple system of order n can be embedded in a Steiner triple system of order 6n + 3
• On embedding incomplete symmetric Latin squares
• Coloring Steiner Triple Systems
• On chromatic number of graphs and set-systems
• Colouring Steiner quadruple systems
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Coloring Block Designs is NP-Complete