Properites of Chromatic Number
Here are some properties of the chromatic number:
- Upper Bounds: The chromatic number of a graph is at most the maximum vertex degree, unless the graph is complete or an odd cycle, in which case the chromatic number is equal to the maximum vertex degree plus one2. This is known as Brooks’ theorem2.
- Lower Bounds: The chromatic number of a graph is at least the size of the largest clique in the graph3. A clique is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent3.
- Bicolorable Graphs: A graph with a chromatic number of 2 is said to be bicolorable2. This means that the vertices of the graph can be colored using only two colors in such a way that no two adjacent vertices share the same color2.
- Three-colorable Graphs: A graph with a chromatic number of 3 is said to be three-colorable2. This means that the vertices of the graph can be colored using only three colors in such a way that no two adjacent vertices share the same color2.
- Complete Graphs: The chromatic number of a complete graph is equal to the number of vertices in the graph1. A complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge1.
- Cycle Graphs: The chromatic number of a cycle graph is 2 if the number of vertices in the graph is even, and 3 if the number of vertices in the graph is odd1.
- Edgeless Graphs: The only graphs that can be 1-colored are edgeless graphs3. An edgeless graph is a graph with no edges3
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: