Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs
Identifikátory výsledku
Kód výsledku v 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>
Výsledek na webu
<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>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs
Popis výsledku v původním jazyce
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).
Název v anglickém jazyce
Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs
Popis výsledku anglicky
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).
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
—
OECD FORD obor
10101 - Pure mathematics
Návaznosti výsledku
Projekt
<a href="/cs/project/EH22_010%2F0003229" target="_blank" >EH22_010/0003229: MSCAfellow5_MUNI</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
Rok uplatnění
2024
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název statě ve sborníku
41ST INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE, STACS 2024
ISBN
9783959773119
ISSN
1868-8969
e-ISSN
—
Počet stran výsledku
19
Strana od-do
1-19
Název nakladatele
SCHLOSS DAGSTUHL, LEIBNIZ CENTER INFORMATICS
Místo vydání
Clermont-Ferrand, France
Místo konání akce
Clermont-Ferrand, France
Datum konání akce
1. 1. 2024
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
001300393400034