{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T21:13:46Z","timestamp":1772313226331,"version":"3.50.1"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"3-4","license":[{"start":{"date-parts":[[2022,12,31]],"date-time":"2022-12-31T00:00:00Z","timestamp":1672444800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Research Council (ERC) under the European Union\u2019s Horizon 2020 research and innovation programme","award":["714532"],"award-info":[{"award-number":["714532"]}]},{"DOI":"10.13039\/100014013","name":"UKRI","doi-asserted-by":"crossref","award":["EP\/X024431\/1"],"award-info":[{"award-number":["EP\/X024431\/1"]}],"id":[{"id":"10.13039\/100014013","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Clarendon Fund Scholarship"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2022,12,31]]},"abstract":"<jats:p>\n            A linearly ordered (LO)\n            <jats:italic>k<\/jats:italic>\n            -colouring of an\n            <jats:italic>r<\/jats:italic>\n            -uniform hypergraph assigns an integer from {1, ... ,\n            <jats:italic>k<\/jats:italic>\n            } to every vertex so that, in every edge, the (multi)set of colours has a unique maximum. Equivalently, for\n            <jats:italic>r<\/jats:italic>\n            = 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\u00a0[STACS\u201921] studied LO colourings on 3-uniform hypergraphs in the context of promise constraint satisfaction problems (PCSPs). We show two results.\n          <\/jats:p>\n          <jats:p>\n            First, given a 3-uniform hypergraph that admits an LO 2-colouring, one can find in polynomial time an LO\n            <jats:italic>k<\/jats:italic>\n            -colouring with\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( k=O(\\sqrt [3]{n \\log \\log n \/ \\log n} \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            .\n          <\/jats:p>\n          <jats:p>\n            Second, given an\n            <jats:italic>r<\/jats:italic>\n            -uniform hypergraph that admits an LO 2-colouring, we establish\n            <jats:sans-serif>NP<\/jats:sans-serif>\n            -hardness of finding an LO\n            <jats:italic>k<\/jats:italic>\n            -colouring for every constant uniformity\n            <jats:italic>r<\/jats:italic>\n            \u2265\n            <jats:italic>k<\/jats:italic>\n            +2. In fact, we determine relationships between polymorphism minions for all uniformities\n            <jats:italic>r<\/jats:italic>\n            \u2265 3, which reveals a key difference between\n            <jats:italic>r<\/jats:italic>\n            &lt;\n            <jats:italic>k<\/jats:italic>\n            +2 and\n            <jats:italic>r<\/jats:italic>\n            \u2265\n            <jats:italic>k<\/jats:italic>\n            +2 and which may be of independent interest. Using the algebraic approach to PCSPs, we actually show a more general result establishing\n            <jats:sans-serif>NP<\/jats:sans-serif>\n            -hardness of finding an LO\n            <jats:italic>k<\/jats:italic>\n            -colouring for LO \u2113-colourable\n            <jats:italic>r<\/jats:italic>\n            -uniform hypergraphs for 2 \u2264 \u2113 \u2264\n            <jats:italic>k<\/jats:italic>\n            and\n            <jats:italic>r<\/jats:italic>\n            \u2265\n            <jats:italic>k<\/jats:italic>\n            - \u2113 + 4.\n          <\/jats:p>","DOI":"10.1145\/3570909","type":"journal-article","created":{"date-parts":[[2022,11,23]],"date-time":"2022-11-23T11:52:11Z","timestamp":1669204331000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Linearly Ordered Colourings of Hypergraphs"],"prefix":"10.1145","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3684-9412","authenticated-orcid":false,"given":"Tamio-Vesa","family":"Nakajima","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Oxford, Oxford, UK"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0263-159X","authenticated-orcid":false,"given":"Stanislav","family":"\u017divn\u00fd","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Oxford, Oxford, UK"}]}],"member":"320","published-online":{"date-parts":[[2023,2]]},"reference":[{"key":"e_1_3_2_2_2","unstructured":"Per Austrin Amey Bhangale and Aditya Potukuchi. 2019. Simplified inpproximability of hypergraph coloring via  \\(t\\) -agreeing families. arXiv:1904.01163. Retrieved from https:\/\/arxiv.org\/abs\/1904.01163."},{"key":"e_1_3_2_3_2","first-page":"1479","volume-title":"Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201920)","author":"Austrin Per","year":"2020","unstructured":"Per Austrin, Amey Bhangale, and Aditya Potukuchi. 2020. Improved inapproximability of rainbow coloring. In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201920). 1479\u20131495. DOI:10.1137\/1.9781611975994.90"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1137\/15M1006507"},{"key":"e_1_3_2_5_2","first-page":"10:1\u201310:16","volume-title":"Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science (STACS\u201921)","volume":"187","author":"Barto Libor","year":"2021","unstructured":"Libor Barto, Diego Battistelli, and Kevin M. Berg. 2021. Symmetric promise constraint satisfaction problems: Beyond the boolean case. In Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science (STACS\u201921), LIPIcs Vol. 187. 10:1\u201310:16. DOI:10.4230\/LIPIcs.STACS.2021.10"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/3457606"},{"key":"e_1_3_2_7_2","first-page":"1204","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201922)","author":"Barto Libor","year":"2022","unstructured":"Libor Barto and Marcin Kozik. 2022. Combinatorial gap theorem and reductions between promise CSPs. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201922). 1204\u20131220. DOI:10.1137\/1.9781611977073.50"},{"key":"e_1_3_2_8_2","series-title":"Dagstuhl Follow-Ups","first-page":"1","volume-title":"The Constraint Satisfaction Problem: Complexity and Approximability","author":"Barto Libor","year":"2017","unstructured":"Libor Barto, Andrei Krokhin, and Ross Willard. 2017. Polymorphisms, and how to use them. In The Constraint Satisfaction Problem: Complexity and Approximability, Andrei Krokhin and Stanislav \u017divn\u00fd (Eds.). Dagstuhl Follow-Ups, Vol. 7. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 1\u201344. DOI:10.4230\/DFU.Vol7.15301.1"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-017-1621-9"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840398"},{"key":"e_1_3_2_11_2","first-page":"15:1\u201315:11","volume-title":"Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP\u201918)","volume":"107","author":"Bhangale Amey","year":"2018","unstructured":"Amey Bhangale. 2018. NP-hardness of coloring 2-colorable hypergraph with poly-logarithmically many colors. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP\u201918), LIPIcs Vol. 107. 15:1\u201315:11. DOI:10.4230\/LIPIcs.ICALP.2018.15"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/176584.176586"},{"key":"e_1_3_2_13_2","first-page":"14:1\u201314:27","volume-title":"Proceedings of the 31st Conference on Computational Complexity (CCC\u201916)","volume":"50","author":"Brakensiek Joshua","year":"2016","unstructured":"Joshua Brakensiek and Venkatesan Guruswami. 2016. New hardness results for graph and hypergraph colorings. In Proceedings of the 31st Conference on Computational Complexity (CCC\u201916), LIPIcs Vol. 50. 14:1\u201314:27. DOI:10.4230\/LIPIcs.CCC.2016.14"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1137\/19M128212X"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3459668"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3470867"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1137\/120880471"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2011.03.005"},{"key":"e_1_3_2_19_2","series-title":"Proceedings of the 11th International Workshiop on Approximation, Randomization and Combinatorial Optimization (APPROX\u201908)","first-page":"49","volume":"5171","author":"Chlamtac Eden","year":"2008","unstructured":"Eden Chlamtac and Gyanit Singh. 2008. Improved approximation guarantees through higher levels of SDP hierarchies. In Proceedings of the 11th International Workshiop on Approximation, Randomization and Combinatorial Optimization (APPROX\u201908), Lecture Notes in Computer Science, Vol. 5171. Springer, 49\u201362. DOI:10.1007\/978-3-540-85363-3_5"},{"key":"e_1_3_2_20_2","volume-title":"Introduction to Algorithms, 3rd Edition","author":"Cormen Thomas H.","year":"2009","unstructured":"Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms, 3rd Edition. MIT Press."},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1137\/07068062X"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-005-0032-4"},{"key":"e_1_3_2_23_2","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1007\/978-3-642-15369-3_11","volume-title":"Proceedings of the 13th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX\u201910)","volume":"6302","author":"Dinur Irit","year":"2010","unstructured":"Irit Dinur and Igor Shinkar. 2010. On the conditional hardness of coloring a 4-colorable graph with super-constant number of colors. In Proceedings of the 13th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX\u201910), Lecture Notes in Computer Science, Vol. 6302. Springer, 138\u2013151. DOI:10.1007\/978-3-642-15369-3_11"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321926"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480100376794"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-016-3383-0"},{"key":"e_1_3_2_27_2","first-page":"62:1\u201362:12","volume-title":"Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP\u201920)","volume":"168","author":"Guruswami Venkatesan","year":"2020","unstructured":"Venkatesan Guruswami and Sai Sandeep. 2020. d-To-1 hardness of coloring 3-colorable graphs with O(1) colors. In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP\u201920), LIPIcs Vol. 168. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, 62:1\u201362:12. DOI:10.4230\/LIPIcs.ICALP.2020.62"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1137\/19M127731X"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00020"},{"key":"e_1_3_2_30_2","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1007\/978-3-642-40328-6_17","volume-title":"Proceedings of the 16th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX\u201913)","author":"Huang Sangxia","year":"2013","unstructured":"Sangxia Huang. 2013. Improved hardness of approximating chromatic number. In Proceedings of the 16th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX\u201913). Springer, 233\u2013243. DOI:10.1007\/978-3-642-40328-6_17. arXiv:1301.5216."},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/274787.274791"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/3001582"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070013"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799349948"},{"key":"e_1_3_2_35_2","first-page":"767","volume-title":"Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC\u201902)","author":"Khot Subhash","year":"2002","unstructured":"Subhash Khot. 2002. On the power of unique 2-prover 1-round games. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC\u201902). ACM, 767\u2013775. DOI:10.1145\/509907.510017"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1173"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00077-4"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2022.128"},{"key":"e_1_3_2_39_2","volume-title":"Linearly Ordered Colourings of Hypergraphs","author":"Nakajima Tamio-Vesa","year":"2022","unstructured":"Tamio-Vesa Nakajima and Stanislav \u017divn\u00fd. 2022. Linearly Ordered Colourings of Hypergraphs. Technical Report."},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/2157.2158"},{"key":"e_1_3_2_41_2","volume-title":"A Note on Hardness of Promise Hypergraph Colouring","author":"Wrochna Marcin","year":"2022","unstructured":"Marcin Wrochna. 2022. A Note on Hardness of Promise Hypergraph Colouring. Technical Report."},{"key":"e_1_3_2_42_2","first-page":"1426","volume-title":"Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201920)","author":"Wrochna Marcin","year":"2020","unstructured":"Marcin Wrochna and Stanislav \u017divn\u00fd. 2020. Improved hardness for \\(H\\) -colourings of \\(G\\) -colourable graphs. In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201920). 1426\u20131435. DOI:10.1137\/1.9781611975994.86"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3570909","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3570909","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:49:12Z","timestamp":1750182552000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3570909"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,31]]},"references-count":41,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2022,12,31]]}},"alternative-id":["10.1145\/3570909"],"URL":"https:\/\/doi.org\/10.1145\/3570909","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,12,31]]},"assertion":[{"value":"2022-04-14","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-11-04","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-02-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}