K-1 Coloring

Overview

The K-1 Coloring algorithm assigns colors to nodes so that no two adjacent nodes share the same color, while minimizing the total number of colors used.

• U.V. Çatalyürek, J. Feo, A.H. Gebremedhin, M. Halappanavar, A. Pothen, Graph Coloring Algorithms for Multi-core and Massively Multithreaded Architectures (2018)

Concepts

Distance-1 Graph Coloring

Distance-1 graph coloring, also known as K-1 graph coloring, is a concept in graph theory where the goal is to assign colors (represented by integers 0, 1, 2, ...) to the nodes of a graph such that no two nodes at distance 1 from each other (i.e., adjacent nodes) share the same color. The objective is also to minimize the number of colors used.

One of the most famous applications of graph coloring is geographical map coloring, where regions on a map are represented as nodes, and edges connect adjacent regions (those sharing a border). The task is to color the regions so that no two adjacent regions have the same color.

This concept has many practical applications beyond maps. For example, in school scheduling, each class is represented as a node, and edges indicate conflicts (such as two classes needing the same room). By coloring the graph, each class is assigned a "color" that represents a different time slot, ensuring no two conflicting classes are scheduled simultaneously.

Greedy Coloring Algorithm

The graph coloring problem is NP-hard to solve optimally, but near-optimal solutions can be obtained using a greedy algorithm.

At the beginning of the greedy algorithm, each node v in the graph is initialized as uncolored. The algorithm processes each node v as below:

• For every adjacent node w of v, mark the color of w as forbidden for v.
• Assign the smallest available color to v that is different from all its forbidden colors.

The algorithm uses an iterative parallel approach: in each iteration, colors are tentatively assigned in parallel, then conflicts (adjacent nodes with the same color) are detected and re-colored in the next iteration.

Considerations

• The algorithm treats all edges as undirected.
• The greedy approach does not guarantee the minimum number of colors — it produces a near-optimal solution.
• Results may vary between runs due to parallel execution order.

Example Graph

GQL
INSERT (A:default {_id: "A"}), (B:default {_id: "B"}),
       (C:default {_id: "C"}), (D:default {_id: "D"}),
       (E:default {_id: "E"}), (F:default {_id: "F"}),
       (G:default {_id: "G"}), (H:default {_id: "H"}),
       (A)-[:default]->(B), (A)-[:default]->(C),
       (A)-[:default]->(D), (A)-[:default]->(E),
       (A)-[:default]->(G), (D)-[:default]->(E),
       (D)-[:default]->(F), (E)-[:default]->(F),
       (G)-[:default]->(D), (G)-[:default]->(H)

Parameters

Run Mode

Returns:

GQL
CALL algo.k1coloring() YIELD nodeId, color, colorCount

Stream Mode

Returns the same columns as run mode, streamed for memory efficiency.

GQL
CALL algo.k1coloring.stream() YIELD nodeId, color
RETURN color, COLLECT(nodeId) AS nodes, COUNT(nodeId) AS size
GROUP BY color

Stats Mode

Returns:

GQL
CALL algo.k1coloring.stats() YIELD nodeCount, colorCount

Write Mode

Computes results and writes them back to node properties. The write configuration is passed as a second argument map.

Write parameters:

Writable columns:

Returns:

GQL
CALL algo.k1coloring.write({}, {
  db: {
    property: "node_color"
  }
}) YIELD task_id, nodesWritten, computeTimeMs, writeTimeMs