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
|