MTH4140 Home

# Chromatic number

## Proper colorings and chromatic numbers

Definition

The chromatic number $$\chi(G)$$ of the graph $$G=(V,E)$$ is the smallest integer $$k$$ for which the vertices from $$V$$ can be colored with $$k$$ colors such that no two neighbors share the same color.

Let us calculate the chromatic number of the graph from the picture below: We can color the graph with $$3$$ colors. The vertices $$D$$ and $$B$$ can have the same color. Let us call that color $$1$$. This means that the vertices $$B$$ and $$D$$ have the color $$1$$. The vertex $$A$$ can be of color $$2$$ and the vertex $$C$$ is of color $$3$$. Therefore, the graph can be colored with $$3$$ colors.

We now need to prove that $$3$$ is the smallest number of colors. In other words, we must prove that it is not possible to color the vertices of the graph with $$2$$ colors. To see this, observe that the vertices $$A$$, $$B$$, and $$C$$ form a complete subgraph: every one of $$A$$, $$B$$, and $$C$$ is connected to every other. This means that they all must have different colors, which implies that $$2$$ colors cannot be used to paint these three vertices.

We will now provide a formal definition of coloring.

Definition

A proper coloring of the graph $$G=(V,E)$$ with $$k$$ colors is any function $$f:V\to \{1,2,\dots, k\}$$ that satisfies:

For every two vertices $$u,v\in V$$ such that $$(u,v)\in E$$, the values $$f(u)$$ and $$f(e)$$ are different.

Then the chromatic number $$\chi(G)$$ can be defined as $\chi(G)=\min\left\{k:\mbox{There exists a proper coloring of }G \mbox{ with }k\mbox{ colors.}\right\}.$

## Parameters of the graph

Definition

Let $$G=(V,E)$$ be a graph.

• $$\Delta(G)$$ is the maximum of degrees of the vertices. $\Delta(G)=\max\left\{d(v):v\in V\right\}.$

• $$\delta(G)$$ is the minimum of degrees of the vertices. $\delta(G)=\min\left\{d(v):v\in V\right\}.$

• $$\alpha(G)$$ is the independence number - the maximum of the size of an independent set. A set of vertices $$I\subseteq V$$ is called independent if no two vertices from $$I$$ are adjacent. $\alpha(G)=\max\left\{|I|:I\subseteq V, \; I \mbox{ is an independent set}\right\}.$

• $$\omega(G)$$ is the clique number - the maximum size of a complete subgraph. $\omega(G)=\max\left\{m:\mbox{ the complete graph }K_m\mbox{ is a subgraph of }G\right\}.$

Exercise

Calculate $$\delta(G)$$, $$\Delta(G)$$, $$\alpha(G)$$ and $$\omega(G)$$ for the graph from the picture above.

## Bounds on the chromatic number

Theorem 1

The inequality $$\chi(G)\leq 1+\Delta(G)$$ holds for every simple graph $$G$$.

Theorem 2

Assume that the chromatic number of the simple graph $$H$$ is equal to $$k$$ and that $$H$$ is a $$k$$-critical graph. Then the following inequality holds $\delta(H)\geq k-1.$

Theorem 3

The following inequality holds for every simple graph $$G$$: $\chi(G)\leq 1+ \max\left\{\delta(H): H\mbox{ is a subgraph of } G\right\}.$

Theorem 4

Assume that the simple graph $$G$$ has $$n$$ vertices and that their degrees are $d_1\geq d_2\geq\cdots \geq d_n$ in non-decreasing order. The following inequality holds $\chi(G)\leq 1+\max_i\min\left\{i-1,d_i\right\}.$

Theorem 5

Assume that $$G$$ is a simple graph. Then the following inequality holds $$\chi(G)\geq \frac{n(G)}{\alpha(G)}$$.