Coloring¶
Vertex Coloring¶
In vertex coloring, each vertex is assigned a color such that no two adjacent vertices have the same color.
K-Colorable¶
If we can color the vertices of a graph using at most k colors, we call that graph k-colorable.
Proper K-Coloring¶
If in coloring the vertices we use k colors (meaning for each of the k colors, there is at least one vertex assigned that color), the coloring is called a proper k-coloring.
Chromatic Number¶
A graph that is k-colorable but not (k-1)-colorable is called k-chromatic. k is called the chromatic number of the graph, and it is denoted as χ(G) = k. In fact, the chromatic number of a graph represents the minimum number of colors required to color the vertices of the graph.
Edge Coloring¶
If the edges of a graph can be colored with k colors, we say that graph is k-edge-colorable.
Edge Chromatic Number¶
If a graph is k-edge-colorable but not (k-1)-edge-colorable, we say this graph is k-edge-chromatic. Here, k is considered the edge chromatic number of the graph, and it is denoted as χ′(G) = k.
Information about Coloring¶
Maps are colored in such a way that no two adjacent countries have the same color. However, the question was what the minimum number of colors required for coloring is, and Francis Guthrie was the first to conjecture that any map could be colored with 4 colors. In 1976, Guthrie's conjecture was proven with the help of computers and became a theorem.
This book is made by The Shaazzz contributors.
It is publicly available with cc-by-sa license.
Last updated at اکتبر 13, 2025.
Rendered by Sphinx (4.3.2) and Minoo theme (Beta 0.9.7).
