On the algorithmic complexity of coloring simple hypergraphs and Steiner triple systems

DOI10.1007/BF02579160zbMath0535.68030OpenAlexW2049432567MaRDI QIDQ791320

Kevin T. Phelps, Vojtěch Rödl

Publication date: 1984

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02579160

zbMATH Keywords

Steiner systemsalgorithmic complexityhypergraph coloring

Mathematics Subject Classification ID

Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Steiner systems in finite geometry (51E10) Triple systems (05B07)

Related Items

The strong chromatic number of partial triple systems, Star chromatic numbers of hypergraphs and partial Steiner triple systems, The complexity of generalized graph colorings, The \(r\)-coloring and maximum stable set problem in hypergraphs with bounded matching number and edge size, Colorability of mixed hypergraphs and their chromatic inversions, Graph properties and hypergraph colourings, Color-bounded hypergraphs. I: General results, Coloring face-hypergraphs of graphs on surfaces

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finite partial quadruple systems can be finitely embedded
• A partial Steiner triple system of order n can be embedded in a Steiner triple system of order 6n + 3
• Some simplified NP-complete graph problems
• Near vector spaces over GF(q) and (v,q + 1,1) BIBDs
• On embedding incomplete symmetric Latin squares
• The completion of finite incomplete Steiner triple systems with applications to loop theory
• Endliche Vervollständigung endlicher partieller Steinerscher Systeme. (Finite completion of finite partial Steiner systems)
• A Survey of Embedding Theorems for Steiner Systems
• Coloring Block Designs is NP-Complete
• The Complexity of Near-Optimal Graph Coloring
• On chromatic number of graphs and set-systems
• Colouring Steiner quadruple systems