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
|