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

DOI10.1007/BF02579160MaRDI QIDQ791320zbMATH OpenOpenAlexFDO

Authors 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

algorithmic complexityhypergraph coloringSteiner systems

Mathematics Subject Classification ID

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

Recommendations

• On colourings of Steiner triple systems
• Strict colouring for classes of Steiner triple systems
• scientific article; zbMATH DE number 2061154
• Greedy Colourings of Steiner Triple Systems
• Strict colorings of Steiner triple and quadruple systems: A survey
• Colouring of cubic graphs by Steiner triple systems
• On the block coloring of Steiner triple systems
• scientific article; zbMATH DE number 1290170
• Improved algorithms for colorings of simple hypergraphs and applications
• scientific article; zbMATH DE number 3890249

Cites work

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

Cited in

(11)

• Color-bounded hypergraphs. I: General results
• The strong chromatic number of partial triple systems
• Graph properties and hypergraph colourings
• Complexity of choosing subsets from color sets
• Coloring face-hypergraphs of graphs on surfaces
• Star chromatic numbers of hypergraphs and partial Steiner triple systems
• The complexity of generalized graph colorings
• Colorability of mixed hypergraphs and their chromatic inversions
• The \(r\)-coloring and maximum stable set problem in hypergraphs with bounded matching number and edge size
• Some NP-completeness results on partial Steiner triple systems and parallel classes.
• Colourings of uniform group divisible designs and maximum packings

This page was built for publication: On the algorithmic complexity of coloring simple hypergraphs and Steiner triple systems

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