Graph Coloring | Graph Coloring Algorithm | Math@TutorCircle.com



Graph Coloring | Graph Coloring Algorithm | Math@TutorCircle.com

Graph Coloring Algorithm

Back to Top
There are many heuristic sequential techniques for coloring a graph. Given below are different graph coloring algorithms.

Greed Graph Coloring: This algorithm focuses on carefully picking the next vertex to be colored. In this, once a vertex is colored, its color never changes.
Vertices are considered to be in a specific order v1,v2,........,vn and vi is the smallest available color not used by vi's neighbours.
If the vertices are ordered according to their degrees, the resulting greedy coloring uses at most maxi min{d(xi) + 1, i} colors, at most one more than the graph's maximum degree.
This heuristic is sometimes called the Welsh–Powell algorithm.
A coloring F of the vertices v0,v1,...... ,vn1 of the graph G is tight with respect to the given order, if
F(ai) colors (i - 1) + 1 for all i = 0, 1, ...., n - 1
This is the backtracking sequential coloring algorithm, which returns the exact value of $x(G), first developed by Brown.
First Fit Algorithm: This is an easiest and fastest technique of all greedy coloring heuistics. It sequentially assigns each vertex the lowest legal color. This algorithm has the advantage of being very simple and fast and this can be implemented to run in O(n).
This algorithm simply picks a vertex from an arbitrary order.

Vertex Coloring

Back to Top
Vertex coloring is a way of coloring the vertices of a graph such that no two adjacent vertices share the same color.
Edge and Face coloring can be transformed into Vertex version.

In vertex coloring, given a graph, identify how many colors are required to color its vertices in such a way that no two adjacent vertices receive the same color. The required number of colors is called the chromatic number of G and is denoted by χ(G). It assigns colors to each vertex of the graph in such a way that no edge connects two identically colored vertices. vertex coloring tries to minimize the number of colors for a given graph.

A vertex coloring of a graph with k or fewer colors is known as a k-coloring. A graph having a k-coloring, χ(G) = k is said to be a k-colorable graph, while a graph having chromatic number χG) = k is called a k-chromatic graph
Vertex Coloring

Edge Coloring

Back to Top
An edge coloring of a graph G is a coloring of the edges of G such that adjacent edges receive different colors. An edge coloring containing the smallest possible number of colors for a given graph is known as a minimum edge coloring. Whether it is possible to color the edges of a given graph using at most k different colors, for a given value of k, or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph.
Edge Coloring

Face Coloring

Back to Top
Face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color. Faces that meet only at a vertex are allowed to be colored the same color. The (face) chromatic number of a map is the smallest number of colors that can be used to color the map subject to our rule, that faces with an edge in common get different colors.

Read full article from Graph Coloring | Graph Coloring Algorithm | Math@TutorCircle.com


No comments:

Post a Comment

Labels

Algorithm (219) Lucene (130) LeetCode (97) Database (36) Data Structure (33) text mining (28) Solr (27) java (27) Mathematical Algorithm (26) Difficult Algorithm (25) Logic Thinking (23) Puzzles (23) Bit Algorithms (22) Math (21) List (20) Dynamic Programming (19) Linux (19) Tree (18) Machine Learning (15) EPI (11) Queue (11) Smart Algorithm (11) Operating System (9) Java Basic (8) Recursive Algorithm (8) Stack (8) Eclipse (7) Scala (7) Tika (7) J2EE (6) Monitoring (6) Trie (6) Concurrency (5) Geometry Algorithm (5) Greedy Algorithm (5) Mahout (5) MySQL (5) xpost (5) C (4) Interview (4) Vi (4) regular expression (4) to-do (4) C++ (3) Chrome (3) Divide and Conquer (3) Graph Algorithm (3) Permutation (3) Powershell (3) Random (3) Segment Tree (3) UIMA (3) Union-Find (3) Video (3) Virtualization (3) Windows (3) XML (3) Advanced Data Structure (2) Android (2) Bash (2) Classic Algorithm (2) Debugging (2) Design Pattern (2) Google (2) Hadoop (2) Java Collections (2) Markov Chains (2) Probabilities (2) Shell (2) Site (2) Web Development (2) Workplace (2) angularjs (2) .Net (1) Amazon Interview (1) Android Studio (1) Array (1) Boilerpipe (1) Book Notes (1) ChromeOS (1) Chromebook (1) Codility (1) Desgin (1) Design (1) Divide and Conqure (1) GAE (1) Google Interview (1) Great Stuff (1) Hash (1) High Tech Companies (1) Improving (1) LifeTips (1) Maven (1) Network (1) Performance (1) Programming (1) Resources (1) Sampling (1) Sed (1) Smart Thinking (1) Sort (1) Spark (1) Stanford NLP (1) System Design (1) Trove (1) VIP (1) tools (1)

Popular Posts