Generalizing Brooks’ theorem via Partial Coloring is Hard Classically and Locally
Jan Bok, Avinandan Das, Anna Gujgiczer, Nikola Jedličková · 2025
Read Generalizing Brooks’ theorem via Partial Coloring is Hard Classically and Locally by Jan Bok, Avinandan Das, Anna Gujgiczer, Nikola Jedličková (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-16308.txt.
Introduction
Jan Bok, Avinandan Das, Anna Gujgiczer, and Nikola Jedličková show that a natural relaxation of graph coloring turns hard the moment one color is removed. Brooks' theorem colors most graphs with as many colors as their maximum degree. Partial coloring asks only that each vertex differ from a required number of its neighbors. With one extra color beyond the requirement, fast algorithms exist, centrally and distributed. The paper studies the tight case, colors equal to the requirement.
For every fixed requirement of at least three, deciding colorability becomes NP-complete. In the distributed model, an algorithm needs a number of rounds linear in the network's size, even on graphs promised to be colorable. That is an exponential separation from the extra-color case. Hard instances are characterized structurally, where partial coloring collapses into proper coloring. Gadget constructions carry the lower bounds.
Catalog record
| CREATOR | Jan Bok, Avinandan Das, Anna Gujgiczer, Nikola Jedličková |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 38 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-16308
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Generalizing Brooks’ theorem via Partial Coloring is Hard Classically and Locally Jan Bok, Avinandan Das, Anna Gujgiczer, Nikola Jedličková Abstract We investigate the classical and distributed complexity of k k -partial c c -coloring where c = k c=k , a natural generalization of Brooks’ theorem where each vertex should be colored from the palette { 1 , … , c } = { 1 , … , k } \{1,\ldots,c\}=\{1,\ldots,k\} such that it must have at least min { k , deg ( v ) } \min\{k,\deg(v)\} neighbors colored differently. Das, Fraigniaud, and Rosén [OPODIS 2023] showed that the problem of k k -partial ( k + 1 ) (k+1) -coloring admits efficient centralized and distributed algorithms and posed an open problem about the status of the distributed complexity of k k -partial k k -coloring. We show that the problem becomes significantly harder when the number of colors is reduced from k + 1 k+1 to k k for every constant k ≥ 3 k\geq 3 . In the classical setting, we prove that deciding whether a graph admits a k k -partial k k -coloring is NP-complete for every constant k ≥ 3 k\geq 3 , revealing a sharp contrast with the linear-time solvable ( k + 1 ) (k+1) -color case. For the distributed LOCAL model, we establish an Ω ( n ) \Omega(n) -round lower bound for computing k k -partial k k -colorings, even when the graph is guaranteed to be k k -partial k k -colorable. This demonstrates an exponential separation from the O ( log 2 k ⋅ log n ) O(\log^{2}k\cdot\log n) -round algorithms known for ( k + 1 ) (k+1) -colorings. Our results leverage novel structural characterizations of “hard instances” where partial coloring reduces to proper coloring, and we construct intricate graph gadgets to prove lower bounds via indistinguishability arguments. \declaretheorem [name=Theorem]thm 1 Introduction Every graph of maximum degree \Delta can be properly colored with at most \Delta+1 colors (with a simple greedy algorithm). The famous Brooks’ theorem [ 7 ] states that \Delta colors are enough for almost all graphs, except for two cases, complete graphs and odd cycles, where \Delta+1 colors are needed. This means that – except for those two cases – every vertex v is colored from the palette \{1,\ldots,\Delta\} in such a way that each of its \deg(v) neighbors receives different colors than v . 1.1 Partial Coloring A natural generalization of proper coloring is partial coloring [ 2 , 6 , 18 , 22 ] . Given two integers k\geq 0 and c\geq 1 , a k -partial c -coloring of a graph assigns to each vertex a color from \{1,\dots,c\} such that every vertex v has at least \min\{k,\deg(v)\} neighbors with a color different from its own. This notion generalizes several well-known coloring paradigms: • For k=\Delta , where \Delta is the maximum degree of the graph, k -partial (k+1) -coloring corresponds to proper (\Delta+1) -coloring and k -partial k -coloring corresponds to proper \Delta -coloring. • For k=1 , the condition captures the classical notion of weak coloring [ 22 ] . The problems of proper (\Delta+1) -coloring [ 1 , 24 , 26 , 16 , 13 , 3 , 11 , 21 , 14 ] , proper \Delta -coloring [ 23 , 16 , 10 , 4 , 15 ] and weak coloring [ 2 , 6 , 22 , 18 ] have been studied extensively in the distributed computing paradigm. The notion of partial coloring brings all these problems in the same framework. For every integer k and every graph G , a k -partial (k+1) -coloring always exists. As outlined in [ 9 ] and implicitly in [ 2 ] , a simple greedy algorithm achieves this: initialize all vertices with color 1, and process the vertices sequentially. For each vertex v , let C(v) denote the set of colors in its neighborhood. If |C(v)|=k+1 , the vertex retains its color. Otherwise, we color it with any color from \{1,\dots,k+1\}\setminus C(v) . This construction guarantees that each vertex has enough differently colored neighbors at the end of the process. Moreover, once two adjacent vertices are assigned different colors during any stage of the algorithm, they permanently maintain this property. From a distributed perspective, Das, Fraigniaud, and Rosén [ 9 ] studied the complexity of computing such a coloring in the LOCAL model. They designed an O(\log n\cdot\log^{2}k) -round algorithm for k -partial (k+1) -coloring using the rounding framework from [ 16 ] which matches their round complexity of O(\log n\cdot\log^{2}\Delta) for proper (\Delta+1) -coloring. The result suggested that “relaxing” the constraints of proper coloring to partial coloring made the problem “easier”, as demonstrated by the improvement of the round complexity. They also posed an open problem; what is the distributed complexity of k -partial k -coloring? The problem of proper \Delta -coloring admits polylogarithmic round complexity ( [ 16 , 4 ] ) in the deterministic LOCAL model. This question can also be viewed as whether this relaxation extends computation advantage to proper \Delta -coloring as well. While proper \Delta -coloring is well understood in the classical (centralized) setting – with known characterizations and complexity classifications — the same is not true for k -partially k -colorable graphs. To the best of our knowledge, no characterization or complexity classification is known for the decision problem: given a graph G and integer k , is G k -partially k -colorable? The problem is far from being trivial. For example, our quest for characterization of k -partial k -colorability quickly yielded non-trivial obstructions (which, for instance, do not even have (k+1) -clique as a subgraph, see Figure 1 for such an example). In this work, we initiate a systematic study of this problem. We first investigate the classical complexity of recognizing k -partially k -colorable graphs. Then, leveraging structural insights, we develop distributed lower bounds for computing k -partial k -colorings in graphs that are guaranteed to admit such a coloring. For distributed computing, we work in the standard LOCAL model of distributed computing [ 20 ] . In this model, the input graph represents a communication network where each node is a computational entity. The nodes communicate in synchronous rounds, exchanging unbounded-sized messages with their neighbors. Each node has a unique identifier (typically from a polynomial-size range) and knows only its own id and the size of the universe of the id s at the beginning of the computation. The complexity of a distributed algorithm is measured in the number of rounds until all nodes produce their output. In our context, each node must eventually decide its color based on the information available in its local neighborhood. A more detailed discussion of the LOCAL model is provided in Section 4 . 2 Related Work Proper (\Delta+1) -Coloring. For many years, the fastest known deterministic algorithms for proper (\Delta+1) -coloring in graphs with maximum degree \Delta required essentially 2^{O(\sqrt{\log n})} rounds in n -node networks [ 1 , 24 ] . This long-standing upper bound was only recently surpassed when a polylogarithmic-round algorithm for (\Delta+1) -coloring was introduced [ 26 ] . All