Coloring Block Designs is NP-Complete

DOI10.1137/0603031MaRDI QIDQ3960717zbMATH OpenOpenAlexFDO

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

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

chromatic numberNP-complete problemspartial 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)

Cites work

• scientific article; zbMATH DE number 3492718 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3338396 (Why is no real title available?)
• A partial Steiner triple system of order n can be embedded in a Steiner triple system of order 6n + 3
• Coloring Steiner Triple Systems
• Colouring Steiner quadruple systems
• On chromatic number of graphs and set-systems
• On embedding incomplete symmetric Latin squares

Cited in

(3)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3960717)