A logarithmic approximation of linearly-ordered colourings
A linearly ordered (LO) k-colouring of a hypergraph assigns to each vertex a colour from the set {0,1,…,k-1} in such a way that each hyperedge has a unique maximum element. Barto, Batistelli, and Berg conjectured that it is NP-hard to find an LO k-colouring of an LO 2-colourable 3-uniform hypergraph...
| المؤلفون الرئيسيون: | , , , |
|---|---|
| التنسيق: | Conference item |
| اللغة: | English |
| منشور في: |
Schloss Dagstuhl
2024
|