Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F24%3A00138003" target="_blank" >RIV/00216224:14330/24:00138003 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.4230/LIPIcs.STACS.2024.34" target="_blank" >http://dx.doi.org/10.4230/LIPIcs.STACS.2024.34</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.STACS.2024.34" target="_blank" >10.4230/LIPIcs.STACS.2024.34</a>

Result language
angličtina
Original language name
Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs
Original language description
A linearly ordered (LO) k-colouring of a hypergraph is a colouring of its vertices with colours 1,..., k such that each edge contains a unique maximal colour. Deciding whether an input hypergraph admits LO k-colouring with a fixed number of colours is NP-complete (and in the special case of graphs, LO colouring coincides with the usual graph colouring).
Czech name
—
Czech description
—

Project
<a href="/en/project/EH22_010%2F0003229" target="_blank" >EH22_010/0003229: MSCAfellow5_MUNI</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2024
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
41ST INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE, STACS 2024
ISBN
9783959773119
ISSN
1868-8969
e-ISSN
—
Number of pages
19
Pages from-to
1-19
Publisher name
SCHLOSS DAGSTUHL, LEIBNIZ CENTER INFORMATICS
Place of publication
Clermont-Ferrand, France
Event location
Clermont-Ferrand, France
Event date
Jan 1, 2024
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
001300393400034

Similar results(10)