Locality of not-so-weak coloring

Alkida Balliu, Juho Hirvonen, Christoph Lenzen, Dennis Olivetti, Jukka Suomela

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference contributionScientificvertaisarvioitu

7 Sitaatiot (Scopus)


Many graph problems are locally checkable: a solution is globally feasible if it looks valid in all constant-radius neighborhoods. This idea is formalized in the concept of locally checkable labelings (LCLs), introduced by Naor and Stockmeyer (1995). Recently, Chang et al. (2016) showed that in bounded-degree graphs, every LCL problem belongs to one of the following classes: “Easy”: solvable in O(log*n) rounds with both deterministic and randomized distributed algorithms.“Hard”: requires at least Ω(log n) rounds with deterministic and Ω(log log n) rounds with randomized distributed algorithms. Hence for any parameterized LCL problem, when we move from local problems towards global problems, there is some point at which complexity suddenly jumps from easy to hard. For example, for vertex coloring in d-regular graphs it is now known that this jump is at precisely d colors: coloring with d + 1 colors is easy, while coloring with d colors is hard. However, it is currently poorly understood where this jump takes place when one looks at defective colorings. To study this question, we define k-partial c-coloring as follows: nodes are labeled with numbers between 1 and c, and every node is incident to at least k properly colored edges. It is known that 1-partial 2-coloring (a.k.a. weak 2-coloring) is easy for any d ≥ 1. As our main result, we show that k-partial 2-coloring becomes hard as soon as k ≥ 2, no matter how large a d we have. We also show that this is fundamentally different from k-partial 3-coloring: no matter which k ≥ 3 we choose, the problem is always hard for d = k but it becomes easy when d >> k. The same was known previously for partial c-coloring with c ≥ 4, but the case of c < 4 was open.
OtsikkoStructural Information and Communication Complexity - 26th International Colloquium, SIROCCO 2019, Proceedings
ISBN (painettu)9783030249212
DOI - pysyväislinkit
TilaJulkaistu - 2019
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaInternational Colloquium on Structural Information and Communication Complexity - L'Aquila, Italia
Kesto: 1 heinäk. 20194 heinäk. 2019
Konferenssinumero: 26


NimiLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in
Vuosikerta11639 LNCS
ISSN (painettu)0302-9743
ISSN (elektroninen)1611-3349


ConferenceInternational Colloquium on Structural Information and Communication Complexity


Sukella tutkimusaiheisiin 'Locality of not-so-weak coloring'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä