The Study of Vertex Coloring Algorithms Using Heuristic Approaches
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Dhirubhai Ambani Institute of Information and Communication Technology
Abstract
Graph vertex coloring is one of the most studied NP-complete optimization problem (READ, 1972) [2]. The problem is that; given a graph G, determine the number of colors required to color G, so that no two adjacent vertices share the same color. And the minimum number of colors required to color graph is known as Chromatic Number and is denoted by ?(G). By using existing properties of eccentricity, BFS, DFS (West, 2000) [3] and graph components we have proposed three new heuristic algorithms to obtain approximated chromatic number of a given graph G. And these approaches are as follows: 1. Eccentricity based coloring 2. DFS based coloring, and 3. Maximum degree based coloring.
Description
Keywords
Algorithms, Vertex Coloring, Graph, Kneser Lines Graph, Harary Line Graph, Hyper-cube Line Graph, Star Line Graph, Path Line Graph, Wheel Line Graph, Machine Learning
Citation
Lodha, Pratik (2018). The Study of Vertex Coloring Algorithms Using Heuristic Approaches. Dhirubhai Ambani Institute of Information and Communication Technology, v, 30 p. (Acc. No: T00687)