Graph: Hamiltonian & Coloring: Nitin Upadhyay March 17, 2006

Graph: Hamiltonian & Coloring Nitin Upadhyay March 17, 2006

Hamiltonian Graphs 

 



A graph G is said to be Hamiltonian if there exists a cycle containing every vertex of G. Such cycle referred to Hamiltonian cycle. A graph is said to be Hamiltonian graph if it contains Hamiltonian cycle. A Hamiltonian path is a simple path that contains all vertices of G where the end points are distinct.

Example 1 

Find Hamiltonian Cycle and Path for the following graph:

Solution 

Hamiltonian Cycle

Solution 

Hamiltonian Path

Rules for Constructing Hamiltonian paths and Cycles 





If G has n vertices, then a Hamiltonian path must contain exactly n-1 edges, and a Hamiltonian cycle must contain exactly n edges. If a vertex v in G has degree k, then a Hamiltonian path must contain at least one edge incident on v and at most two edges incident on v. Once a vertex is selected in the path then all other unused edges associated with the vertex must be deleted as only two edges incident on v can be included in a Hamiltonian cycle.

Scheduling Problem 







Suppose state legislature has a list of 21 standing committees. Each committee is supposed to meet one hour each week. The constraint is that no legislator should be schedule to be in two different committee meetings at the same time. The problem is to obtain a weekly schedule such that it comprise of minimum hours of time for meeting with no legislators share two meeting.

Solution 





One of the solution to the scheduling problem is to use vertex coloring. A graph G is build such that vertices represent legislative committees and edges joining vertices represent common legislator. In this the colors are assigned to vertices of G, such that adjacent vertices have different colors.

Chromatic numbers 





An n-coloring of G is a coloring of G using ncolors. If g has n-coloring then G is said to be ncoloring. The chromatic number of a graph G, χ(G), is the minimum number n for which there exists an n-coloring of the vertices of G.

Sequential coloring 

 

For any ordering v1, v2,…vn of the n vertices of a graph. Any sequence c1, c2,…, cn of n colors. The color to be assigned to Vi is the smallestindexed color not already assigned to one of its lower-indexed neighboring vertices.

Theorem 1 A Complete graph of n vertices, Kn, requires at least n colors. A complete graph with n vertices have n(n-1)/2 edges as their exists an edge between every pair of vertices. n-1 colors implies at least one vertex will have the same color as an adjacent vertex .

Theorems 



A Complete Bipartite graph with m set of vertices and n set of vertices can be colored using at most two colors. The chromatic number of a cycle of length n, Cn, is 2 if the cycle is even.

The chromatic number of a cycle of length n, Cn, is 2 if the cycle  isConsider even. an even cycle: v1,v2,v3,v4,v1. 

a coloring of an even cycle is analogous to selecting vertices to be in one set and adjacent vertices to be in the opposite set

The chromatic number of a cycle of length n, Cn, is 3 if the cycle  isStarting odd from andtheninitial > 1. vertex, we color it 1. 







As the graph is traversed, vertices are colored in alternation. Proceeding to color vertices we arrive at case where the first and n-1 vertex have the same color. Thus, it is necessary to introduce a third color to either of the vertices in order to color the graph. A graph with an odd cycle is not bipartite.

The map coloring problem 





Color the countries with the fewest number of colors Different colors on adjacent countries 4 colors always suffice

Every simple planar graph is 5colorable 

 





Color all the vertices of the graph G with color set c={c1, c2,…,c5} Delete the vertex v (G-v) having maximum degree. Recolor the vertices with different color schemes so that no contradiction exists. If at any vertex contradiction occur that means two adjacent vertex results in same color then pick the left over color from the set and assigned to the vertex. Again repeat the process by deleting the vertex of maximum degree and recoloring the rest graph.

Questions ?