Skedbooks
←
Discrete Mathematics

Graph Coloring

GRAPH COLORING

Coloring problem
Suppose that you are given a graph G with n vertices and are asked to paint its vertices such that no two adjacent vertices have the same color. What is the minimum number of colors that you would require. This constitutes a coloring problem.

Partitioning problem
Having painted the vertices, you can group them into different sets—one set consisting of all red vertices, another of blue, and so forth. This is a partitioning problem. For example, finding a spanning tree in a connected graph is equivalent to partitioning the edges into two sets—one set consisting of the edges included in the spanning tree, and the other consisting of the remaining edges. Identification of a Hamiltonian circuit (if it exists) is another partitioning of set of edges in a given graph.

Properly coloring of a graph
Painting all the vertices of a graph with colours such that no two adjacent vertices have the same colour is called the proper colouring (or simply colouring) of a graph.
A graph in which every vertex has been assigned a colour according to a proper colouring is called a properly coloured graph.
Usually a given graph can be properly coloured in many different ways. Figure (2.69)(a) shows three different proper colouring of a graph.

The K-colourings of the graph G is a colouring of graph G using K-colours. If the graph G has colouring, then the graph G is said to be K-colourable.

Chromatic number
A graph G is said to be K-colourable if we can properly colour it with K (number of) colours.
A graph G which is n-colourable but not (K – 1)-colourable is called a K-chromatic graph.
In other words, a K-chromatic graph is a graph that can be properly coloured with K-colours but not with less than K colours.
If a graph G is K-chromatic, then K is called chromatic number of the graph G. Thus the chromatic number of a graph is the smallest number of colours with which the graph can be properly coloured.The chromatic number of a graph G is usually denoted by χ(G).

We list a few rules that may be helpful :

  1. χ(G) ≤ | V |, where | V | is the number of vertices of G.
  2. A triangle always requires three colours, that is χ(K3) = 3 ; more generally, χ(Kn) = n, where Kn is the complete graph on n vertices.
  3. If some subgraph of G requires K colors then χ(G) ≥ K.
  4. If degree (v) = d, then atmost d colours are required to colour the vertices adjacent to v.
  5. χ(G) = maximum {χ(C)/C is a connected component of G}
  6. Every K-chromatic graph has at least K vertices v such that degree (v) ≥ k – 1.
  7. For any graph G, χ(G) ≤ 1 Δ(G), where Δ(G) is the largest degree of any vertex of G.
  8. When building a K-colouring of a graph G, we may delete all vertices of degree less than K (along with their incident edges). In general, when attempting to build a K-colouring of a graph, it is desirable to start by Kcolouring a complete subgraph of K vertices and then successively finding vertics adjacent to K – 1 different colours, thereby forcing the color choice of such vertices.
  9. These are equivalent :
  • (i) A graph G is 2-colourable
  • (ii) G is bipartite
  • (iii) Every cycle of G has even length.
  1. If δ(G) is the minimum degree of any vertex of G, then χ(G) ≥ | V | / | V | – δ(G) where | V | is the number of vertices of G.

K-Critical graph: If the chromatic number denoted by (G) = K, and (G – v) is less than equal to K – 1 for each vertex v of G, then