Coverings in Graph

tutorial and example
tutorial and example

A covering graph ‘C’ is a subgraph that either contains all the vertices or all the edges of graph ‘G’.

Coverings in Graph

There are basically two types of Covering:

Edge Covering: A subgraph that contains all the edges of graph ‘G’ is called as edge covering.

Vertex Covering: A subgraph that contains all the vertices of graph ‘G’ is called as vertex covering.

Examples: In the following figure, the covering graph of H is the graph C.

Coloring

Proper Coloring: Proper coloring is a process in which all the vertices of the graph are painted with different colors such that no adjacent vertices have the same color. We consider only simple, connected graph for coloring problem.

Some of the observation based on colorings are:

  1. A graph that has only one isolated vertex is 1- chromatic.
  2. A graph with one or more edges is 2- chromatic or bichromatic .
  3. A complete graph with n vertices in n- chromatic because all its vertices are adjacent to each other or if it has r vertices then it is r- chromatic. Every graph that has a triangle is at least 3 – chromatic.
  4. A graph that has simple one circuit with n>=3 is 2 chromatic if n is even and 3- chromatic if n is odd.

Types of coloring

  1. Vertex Coloring .
  2. Edge Coloring .

1. Vertex Coloring

It is a method of coloring in which all the vertices of a graph have different colors that’s why they do not share the same color. This is called as Vertex coloring .

2. Edge Coloring

It is a method of coloring in which all the edges of a graph have different colors that’s why they do not share the same color. This is called as Edge coloring. An edge coloring with k colors is called k-edge coloring.

Chromatic number: The graph that requires K different colors for coloring and we cannot reduce the number of colors is called K-chromatic graph and the number K is called as Chromatic number of graph ‘G’.

Chromatic Index: The smallest number of colors that are required for an edge coloring of a graph G is called chromatic index, or edge chromatic number, χ'(G).