@article{22247,
  abstract     = {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).
Here, we investigate the complexity of approximating the “linearly ordered chromatic number” of a hypergraph. We prove that the following promise problem is NP-complete: Given a 3-uniform hypergraph, distinguish between the case that it is LO 3-colourable, and the case that it is not even LO 4-colourable. We prove this result by a combination of algebraic, topological, and combinatorial methods, building on and extending a topological approach for studying approximate graph colouring introduced by Krokhin, Opršal, Wrochna, and Živný (2023).},
  author       = {Filakovský, Marek and Nakajima, Tamio Vesa and Opršal, Jakub and Tasinato, Gianluca and Wagner, Uli},
  issn         = {1942-3462},
  journal      = {ACM Transactions on Computation Theory},
  keywords     = {Constraint satisfaction problem, hypergraph colouring, promise problem, topological methods},
  number       = {2},
  publisher    = {Association for Computing Machinery},
  title        = {{Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs}},
  doi          = {10.1145/3779121},
  volume       = {18},
  year         = {2026},
}

@article{19860,
  abstract     = {An eight-partition of a finite set of points (respectively, of a continuous mass distribution) in R^3
 consists of three planes that divide the space into 8 octants, such that each open octant contains at most 1/8 of the points (respectively, of the mass). In 1966, Hadwiger showed that any mass distribution in R^3 admits an eight-partition; moreover, one can prescribe the normal direction of one of the three planes. The analogous result for finite point sets follows by a standard limit argument. We prove the following variant of this result: any mass distribution (or point set) in R^3 admits an eight-partition for which the intersection of two of the planes is a line with a prescribed direction. Moreover, we present an efficient algorithm for calculating an eight-partition of a set of n points in R^3 (with prescribed normal direction of one of the planes) in time O(n^7/3). A preliminary version of this work appeared in SoCG’24 (Aronov et al., 40th International Symposium on Computational Geometry, 2024).},
  author       = {Aronov, Boris and Basit, Abdul and Ramesh, Indu and Tasinato, Gianluca and Wagner, Uli},
  issn         = {1432-0444},
  journal      = {Discrete & Computational Geometry},
  publisher    = {Springer Nature},
  title        = {{Eight-partitioning points in 3D, and efficiently too}},
  doi          = {10.1007/s00454-025-00739-0},
  year         = {2025},
}

@inproceedings{20008,
  abstract     = {We study the complexity of a class of promise graph homomorphism problems. For a fixed graph H, the H-colouring problem is to decide whether a given graph has a homomorphism to H. By a result of Hell and Nešetřil, this problem is NP-hard for any non-bipartite loop-less graph H. Brakensiek and Guruswami [SODA 2018] conjectured the hardness extends to promise graph homomorphism problems as follows: fix a pair of non-bipartite loop-less graphs G, H such that there is a homomorphism from G to H, it is NP-hard to distinguish between graphs that are G-colourable and those that are not H-colourable. We confirm this conjecture in the cases when both G and H are 4-colourable. This is a common generalisation of previous results of Khanna, Linial, and Safra [Comb. 20(3): 393-415 (2000)] and of Krokhin and Opršal [FOCS 2019]. The result is obtained by combining the algebraic approach to promise constraint satisfaction with methods of topological combinatorics and equivariant obstruction theory.},
  author       = {Avvakumov, Sergey and Filakovský, Marek and Opršal, Jakub and Tasinato, Gianluca and Wagner, Uli},
  booktitle    = {Proceedings of the 57th Annual ACM Symposium on Theory of Computing},
  isbn         = {9798400715105},
  issn         = {0737-8017},
  location     = {Prague, Czechia},
  pages        = {72--83},
  publisher    = {Association for Computing Machinery},
  title        = {{Hardness of 4-colouring G-colourable graphs}},
  doi          = {10.1145/3717823.3718154},
  year         = {2025},
}

@phdthesis{20339,
  abstract     = {This thesis investigates the interplay between algebraic and topological methods and combinatorial problems, focusing on approximate graph colourings and mass partitioning. The unifying theme throughout the dissertation is the use of continuous maps and symmetry constraints to extract combinatorial insights.

We first explore approximate graph colouring problems and more generally promise constraint satisfaction problems. Using tools from equivariant topology in combination with the general theory of polymorphism of a promise constraint satisfaction problem, we establish hardness for specific types of approximations.

In the second part, we address mass partitioning problems, where one seeks to divide geometric objects or measures in Euclidean space into parts of equal size using hyperplanes. Employing techniques from topological combinatorics (configuration space/test map setup and Borsuk–Ulam type theorems), we both obtain a new equipartitioning result in the and provide a fast algorithm for computing equipartitioning of point sets in 3D.
},
  author       = {Tasinato, Gianluca},
  issn         = {2663-337X},
  pages        = {106},
  publisher    = {Institute of Science and Technology Austria},
  title        = {{Topological methods in discrete geometry and theoretical computer science : Measure partitioning and constraint satisfaction problems}},
  doi          = {10.15479/AT-ISTA-20339},
  year         = {2025},
}

@inproceedings{18917,
  abstract     = {An eight-partition of a finite set of points (respectively, of a continuous mass distribution) in ℝ³ consists of three planes that divide the space into 8 octants, such that each open octant contains at most 1/8 of the points (respectively, of the mass). In 1966, Hadwiger showed that any mass distribution in ℝ³ admits an eight-partition; moreover, one can prescribe the normal direction of one of the three planes. The analogous result for finite point sets follows by a standard limit argument.
We prove the following variant of this result: Any mass distribution (or point set) in ℝ³ admits an eight-partition for which the intersection of two of the planes is a line with a prescribed direction.
Moreover, we present an efficient algorithm for calculating an eight-partition of a set of n points in ℝ³ (with prescribed normal direction of one of the planes) in time O^*(n^{5/2}).},
  author       = {Aronov, Boris and Basit, Abdul and Ramesh, Indu and Tasinato, Gianluca and Wagner, Uli},
  booktitle    = {40th International Symposium on Computational Geometry},
  isbn         = {9783959773164},
  location     = {Athens, Greece},
  pages        = {8:1--8:15},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Eight-partitioning points in 3D, and efficiently too}},
  doi          = {10.4230/LIPIcs.SoCG.2024.8},
  volume       = {293},
  year         = {2024},
}

@inproceedings{15168,
  abstract     = {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). Here, we investigate the complexity of approximating the "linearly ordered chromatic number" of a hypergraph. We prove that the following promise problem is NP-complete: Given a 3-uniform hypergraph, distinguish between the case that it is LO 3-colourable, and the case that it is not even LO 4-colourable. We prove this result by a combination of algebraic, topological, and combinatorial methods, building on and extending a topological approach for studying approximate graph colouring introduced by Krokhin, Opršal, Wrochna, and Živný (2023).},
  author       = {Filakovský, Marek and Nakajima, Tamio Vesa and Opršal, Jakub and Tasinato, Gianluca and Wagner, Uli},
  booktitle    = {41st International Symposium on Theoretical Aspects of Computer Science},
  isbn         = {9783959773119},
  issn         = {1868-8969},
  location     = {Clermont-Ferrand, France},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs}},
  doi          = {10.4230/LIPIcs.STACS.2024.34},
  volume       = {289},
  year         = {2024},
}