Journal article icon

Journal article

Linearly ordered colourings of hypergraphs

Abstract:

A linearly ordered (LO) π‘˜-colouring of an π‘Ÿ-uniform hypergraph assigns an integer from {1, . . . , π‘˜} to every vertex so that, in every edge, the (multi)set of colours has a unique maximum. Equivalently, for π‘Ÿ = 3, if two vertices in an edge are assigned the same colour, then the third vertex is assigned a larger colour (as opposed to a different colour, as in classic non-monochromatic colouring). Barto, Battistelli, and Berg [STACS’21] studied LO colourings on 3-uniform hypergraphs in the co...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
Publisher copy:
10.1145/3570909

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
ORCID:
0000-0003-3684-9412
More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Oxford college:
Jesus College
Role:
Author
ORCID:
0000-0002-0263-159X
More from this funder
Name:
UK Research and Innovation/ European Research Council
Grant:
EP/X024431/1
More from this funder
Name:
European Commission
Grant:
714532
Publisher:
Association for Computing Machinery
Journal:
ACM Transactions on Computation Theory More from this journal
Volume:
14
Issue:
3-4
Pages:
1–19
Publication date:
2022-11-23
Acceptance date:
2022-11-01
DOI:
EISSN:
1942-3462
ISSN:
1942-3454
Language:
English
Keywords:
Pubs id:
1295418
Local pid:
pubs:1295418
Deposit date:
2022-11-02

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP