Coloring in graph theory pdf

Graph Coloring- Graph Coloring is a process of assigning colors to the vertices of a graph such that no two adjacent vertices of it are assigned the same color. Graph Coloring is also called as Vertex Coloring. It ensures that there exists no edge in the graph whose end vertices are colored with the same color. Such a graph is called as a Properly colored graph. Graph Coloring Example- The following graph is an example of a properly colored graph- In this graph, No two adjacent vertices are colored with the same color.

Therefore, it is a properly colored graph. OR Chromatic Number is the minimum number of colors required to color any graph such that no two adjacent vertices of it are assigned the same color. Chromatic Number Example- Consider the following graph- In this graph, No two adjacent vertices are colored with the same color. We can not properly color this graph with less than 3 colors. In a cycle graph, all the vertices are of degree 2.

Examples- 2. Planar Graphs- A Planar Graph is a graph that can be drawn in a plane such that none of its edges cross each other. Chromatic number of each graph is less than or equal to 4. Complete Graphs- A complete graph is a graph in which every two distinct vertices are joined by exactly one edge. Graph coloring is nothing but a simple way of labelling graph components such as vertices, edges, and regions under some constraints. In a graph, no two adjacent vertices, adjacent edges, or adjacent regions are colored with minimum number of colors.

This number is called the chromatic number and the graph is called a properly colored graph. While graph coloring, the constraints that are set on the graph are colors, order of coloring, the way of assigning color, etc.

A coloring is given to a vertex or a particular region. Thus, the vertices or regions having same colors form independent sets. Simply put, no two vertices of an edge should be of the same color. Region coloring is an assignment of colors to the regions of a planar graph such that no two adjacent regions have the same color. Two regions are said to be adjacent if they have a common edge. Graph Diagrams.

Common Graphs. Complements and Subgraphs. Recognizing Isomorphic Graphs. The Number of Graphs Having a Given v. Are There More Nonplanar Graphs? Determining Whether a Graph is Planar or Nonplanar.

Mathematical Induction. Algebraic Topology. Chromatic Number. Coloring Planar Graphs. Proof of the Five Color Theorem. Coloring Maps. The Genus of a Graph. Some Consequences. Estimating the Genus of a Connected Graph. The Heawood Coloring Theorem.