K-1 Coloring

Overview

The K-1 Coloring algorithm assigns colors to each node such that no two adjacent nodes share the same color and the number of colors used is minimized.

• Graph Coloring Algorithms for Multi-core and Massively Multithreaded Architectures (2018)

Concepts

Coloring

A coloring of a graph often refers to a proper node coloring, namely a labeling of the graph's nodes with colors such that no two nodes sharing the same edge have the same color. Graph coloring is a fundamental problem in computer science used in applications such as scheduling, register allocation, and wireless channel assignment.

Chromatic Number

The smallest number of colors needed to color a graph G is called its chromatic number, and is often denoted χ(G). A graph that can be assigned a (proper) k-coloring is k-colorable, and it is k-chromatic if its chromatic number is exactly k.

Considerations

Graph coloring is NP-complete It is NP-complete to decide if a given graph admits a k-coloring and NP-hard to compute the chromatic number. As a result, greedy algorithm is often used to solve graph coloring problem for large graphs. In fact, such approach does not guarantee the optimal solution and may color neighboring nodes the same. However, increasing the number of iterations can improve accuracy.

Syntax

• Command: algo(k1_coloring)
• Parameters:

Examples

The example graph is as follows:

File Writeback

Property Writeback

Direct Return

Stream Return

Stats Return