# Greedy Graph Coloring

Supported Graph Characteristics
 Unweighted edges Homogeneous vertex types Heterogeneous vertex types

Algorithm link: Greedy Graph Coloring

This algorithm assigns a unique integer value known as its color to the vertices of a graph such that no neighboring vertices share the same color. The reason why this is called color is that this task is equivalent to assigning a color to each nation on a map so that no neighboring nations share the same color.

Given a set of k vertices, the algorithm first colors all vertices with the same color - the first color. It then starts from all the vertices and has each vertex send its own colors to its neighbors. If there are two neighboring vertices with the same color, the algorithm will reassign colors where there is a conflict. The same process is repeated until all conflicts are resolved.

## Notes

This algorithm ignores edge weights.

## Specifications

``````CREATE QUERY tg_greedy_graph_coloring(SET<STRING> v_type_set,SET<STRING> e_type_set,UINT max_colors = 999999,
BOOL print_color_count = TRUE, BOOL print_stats = TRUE, STRING file_path = "")  SYNTAX V1 {``````

### Parameters

Name Description

`SET<STRING> v_type_set`

A set of all vertex types to color.

`SET<STRING> e_type_set`

A set of all edge types to traverse.

`INT max_colors`

The Maximum number of colors that can be used. Use a large number like `999999` unless there is a strict limit.

`BOOL print_color_count`

If set to true, the total number of colors used will be displayed

`BOOL print_stats`

If set to true, the output will display all vertices and their associated color

`STRING file_path`

If a file path is provided, the output will be saved to the file indicated by the file path in CSV format.

### Time complexity

The algorithm has a worst-case time complexity of O(V^2 + E), where V is the number of vertices and E is the number of edges.

### Run commands

#### Schema-Free Query

``RUN QUERY greedy_graph_coloring (<parameters>)``

#### Packaged Template Query

``CALL GDBMS_ALGO.classification.greedy_graph_coloring (<parameters>)``

## Example

On the social10 graph, say we want to color the `Person` vertices in such a way that any two vertices that are either connected by a `Friend` edge or a `Coworker` edge do not have the same color. By running the `greedy_graph_color` algorithm, we get the following result:

``````GSQL > RUN QUERY greedy_graph_coloring(["Person"], ["Friend", "Coworker"],
999999, true, true, "")

[
{
// Total number of colors used
"color_count": 4
},
{
"start": [
{
"attributes": {
"start.@colorvertex": 4
},
"v_id": "Fiona",
"v_type": "Person"
},
{
"attributes": {
"start.@colorvertex": 3
},
"v_id": "Justin",
"v_type": "Person"
},
{
"attributes": {
"start.@colorvertex": 2
},
"v_id": "Bob",
"v_type": "Person"
},
{
"attributes": {
"start.@colorvertex": 3
},
"v_id": "Chase",
"v_type": "Person"
},
{
"attributes": {
"start.@colorvertex": 2
},
"v_id": "Damon",
"v_type": "Person"
},
{
"attributes": {
"start.@colorvertex": 1
},
"v_id": "Alex",
"v_type": "Person"
},
{
"attributes": {
"start.@colorvertex": 3
},
"v_id": "George",
"v_type": "Person"
},
{
"attributes": {
"start.@colorvertex": 1
},
"v_id": "Eddie",
"v_type": "Person"
},
{
"attributes": {
"start.@colorvertex": 2
},
"v_id": "Ivy",
"v_type": "Person"
},
{
"attributes": {
"start.@colorvertex": 1
},
"v_id": "Howard",
"v_type": "Person"
}
]
}
]``````