On the algorithmic complexity of coloring simple hypergraphs and Steiner triple systems
From MaRDI portal
Publication:791320
DOI10.1007/BF02579160zbMath0535.68030OpenAlexW2049432567MaRDI QIDQ791320
Publication date: 1984
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02579160
Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Steiner systems in finite geometry (51E10) Triple systems (05B07)
Related Items (8)
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
This page was built for publication: On the algorithmic complexity of coloring simple hypergraphs and Steiner triple systems
