Chromatic Number of Cyclic Graph
A graph is known as a cycle graph if it contains ‘n’ edges and ‘n’ vertices (n >= 3), which form a cycle of length ‘n’. The chromatic number in a cycle graph depends upon the parity of cycle length:
Case 1 (Odd length cycle): χ(G) = 3.
Case 2(Even length cycle): χ(G) = 2.
Chromatic Number of a Graph | Graph Colouring
Graph coloring is a fundamental concept in graph theory, and the chromatic number is a key parameter that quantifies the coloring properties of a graph. Let’s go into the introductory aspects of the chromatic number.
Graph coloring refers to the problem of coloring vertices of a graph in such a way that no two adjacent vertices have the same color. This is also called the vertex coloring problem. If coloring is done using at most m colors, it is called m-coloring.
Table of Content
- What is Chromatic Number?
- Chromatic Number of Cyclic Graph:
- Chromatic Number of Complete Graph:
- Chromatic Number of Bipartite Graph:
- Chromatic Number of Star Graph:
- Chromatic Number of Wheel Graph:
- Chromatic Number of Planar Graph:
- Properites of Chromatic Number:
- Importance of Chromatic Number in Graph Theory:
- Algorithm to Find Chromatic Numbers
- Choosing the right algorithm for finding chromatic number depends on the specific graph:
- Relation between chromatic number and chromatic polynomial
- Analogy:
- Related Articles: