2026-07-22T17:01:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25192 2026-03-19T12:59:25Z ddc:004 open_access

Orientation Does Not Help with 3-Coloring a Grid in Online-LOCAL Boudier, Thomas Casagrande, Filippo Das, Avinandan Equi, Massimo Lievonen, Henrik Modanese, Augusto Stimpert, Ronja coloring locally checkable labeling problems online algorithms The online-LOCAL and SLOCAL models are extensions of the LOCAL model where nodes are processed in a sequential but potentially adversarial order. So far, the only problem we know of where the global memory of the online-LOCAL model has an advantage over SLOCAL is 3-coloring bipartite graphs. Recently, Chang et al. [PODC 2024] showed that even in grids, 3-coloring requires Ω(log n) locality in deterministic online-LOCAL. This result was subsequently extended by Akbari et al. [STOC 2025] to also hold in randomized online-LOCAL. However, both proofs heavily rely on the assumption that the algorithm does not have access to the orientation of the underlying grid. In this paper, we show how to lift this requirement and obtain the same lower bound (against either model) even when the algorithm is explicitly given a globally consistent orientation of the grid. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Thomas Boudier and Filippo Casagrande and Avinandan Das and Massimo Equi and Henrik Lievonen and Augusto Modanese and Ronja Stimpert 2026 Is Part Of LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2025.19 urn:nbn:de:0030-drops-251925 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.19 eng https://creativecommons.org/licenses/by/4.0/legalcode