# The K-1 Coloring algorithm

 This is documentation for the Graph Algorithms Library, which has been deprecated by the Graph Data Science Library (GDS).

This section describes the K-1 Coloring algorithm in the Neo4j Graph Algorithms library.

This topic includes:

## 1. Introduction

The K-1 Coloring algorithm assigns a color to every node in the graph, trying to optimize for two objectives:

1. To make sure that every neighbor of a given node has a different color than the node itself.

2. To use as few colors as possible.

Note that the graph coloring problem is proven to be NP-complete, which makes it intractable on anything but trivial graph sizes. For that reason the implemented algorithm is a greedy algorithm. Thus it is neither guaranteed that the result is an optimal solution, using as few colors as theoretically possible, nor does it always produce a correct result where no two neighboring nodes have different colors. However the precision of the latter can be controlled by the number of iterations this algorithm runs.

 Running this algorithm requires sufficient memory availability. Before running this algorithm, we recommend that you read Memory Requirements.

## 2. Syntax

The following describes the API for running the algorithm and writing results back to Neo4j:
``````CALL algo.beta.k1coloring(label: STRING, relationship: STRING, {
write: BOOLEAN,
writeProperty: STRING
})
YIELD nodes, setCount, loadMillis, computeMillis, writeMillis``````
Table 1. Parameters
Name Type Default Optional Description

node label

string

`null`

yes

The node label to load from the graph. If `null`, load all nodes.

relationship

string

`null`

yes

The relationship type to load from the graph. If `null`, load all relationships.

config

map

`{}`

yes

Table 2. Configuration
Name Type Default Optional Description

`concurrency`

int

available CPUs

yes

The number of concurrent threads used for running the algorithm. Also provides the default value for 'readConcurrency' and 'writeConcurrency'. This is dependent on the Neo4j edition; for more information, see :/introduction/index.adoc#system-requirements-cpu.

`readConcurrency`

int

value of 'concurrency'

yes

`writeConcurrency`

int

value of 'concurrency'

yes

The number of concurrent threads used for writing the result.

`write`

boolean

`true`

yes

Specifies if the result should be written back as a node property.

`writeProperty`

string

yes

The property name written back the ID of the partition particular node belongs to.

`graph`

string

`'huge'`

yes

Use `'huge'` when describing the subset of the graph with node label and relationship type parameters. Use `'cypher'` for describing the subset using Cypher queries for nodes and relationships.

`iterations`

int

10

yes

The maximum number of iterations the algorithms runs with.

`batchSize`

int

10_000

yes

Controls the the number of relationships each parallel thread processes.

Table 3. Results
Name Type Description

`loadMillis`

int

`computeMillis`

int

Milliseconds for running the algorithm.

`writeMillis`

int

Milliseconds for writing result data back.

`nodes`

int

The number of nodes considered.

`ranIterations`

int

The actual number of iterations the algorithm ran.

`didConverge`

boolean

An indicator of whether the algorithm found a correct coloring.

`colorCount`

int

The number of colors used.

`write`

boolean

Specifies if the result was written back as a node property.

`writeProperty`

string

The property name written back to.

The following describes the API for running the algorithm and stream results:
``````CALL algo.beta.k1coloring.stream(label: STRING, relationship: STRING, {
// configuration
})
YIELD nodeId, color``````
Table 4. Parameters
Name Type Default Optional Description

node label

string

`null`

yes

The node label to load from the graph. If null, load all nodes.

relationship type

string

`null`

yes

The relationship type to load from the graph. If null, load all relationships.

config

map

`{}`

yes

Table 5. Configuration
Name Type Default Optional Description

`concurrency`

int

available CPUs

yes

The number of concurrent threads used for running the algorithm. Also provides the default value for 'readConcurrency' and 'writeConcurrency'. This is dependent on the Neo4j edition; for more information, see :/introduction/index.adoc#system-requirements-cpu.

`readConcurrency`

int

value of 'concurrency'

yes

`graph`

string

`'huge'`

yes

Use `'huge'` when describing the subset of the graph with node label and relationship type parameters. Use `'cypher'` for describing the subset using Cypher queries for nodes and relationships.

`iterations`

int

10

yes

The maximum number of iterations the algorithms runs with.

`batchSize`

int

10_000

yes

Controls the the number of relationships each parallel thread processes.

Table 6. Results
Name Type Description

`nodeId`

int

Node ID

`color`

int

Color ID

## 3. Examples

Consider the graph created by the following Cypher statement:

``````CREATE (nAlice:User {name: 'Alice'})
CREATE (nBridget:User {name: 'Bridget'})
CREATE (nCharles:User {name: 'Charles'})
CREATE (nDoug:User {name: 'Doug'})

This graph has a super node with name "Alice" that connects to all other nodes. It should therefore not be possible for any other node to be assigned to the color as the Alice node. In the following examples we will demonstrate using the K-1 Coloring algorithm on this graph.

### 3.1. Named graphs and Cypher projections

In the examples below, we will rely on the implicit loading of graphs for the algorithm computation. However, like other algorithms K-1 Coloring also accepts named graphs and Cypher projections as inputs. See Projected Graph Model for more details.

Using a named graph:
``````CALL algo.graph.load('myGraph', 'User', 'LINK');

CALL algo.k1coloring.stream(null, null, {graph: 'myGraph'})
YIELD nodeId, color
RETURN algo.asNode(nodeId).name AS Name, color AS Color
ORDER BY Name;``````
Table 7. Results
Name Color

`"Alice"`

`2`

`"Bridget"`

`1`

`"Charles"`

`0`

`"Doug"`

`0`

Using a Cypher projection:
``````CALL algo.k1coloring.stream(
'MATCH (u:User) RETURN id(u) AS id',
RETURN id(u1) AS source, id(u2) AS target',
{graph:'cypher'}
)
YIELD nodeId, color
RETURN algo.asNode(nodeId).name AS Name, color AS Color
ORDER BY Name``````
Table 8. Results
Name Color

`"Alice"`

`2`

`"Bridget"`

`1`

`"Charles"`

`0`

`"Doug"`

`0`

These results are identical to those of the named graph, as the Cypher projection we use mimics the behaviour of the default loading configuration. Of course, the Cypher projection feature enables more advanced control over which exact parts of the graph to compute over; please see Cypher projection for more details.