git / email
index

Chromatic number and planar graphs

In a graph G where 𝚫 is the maximum vertex degree we have χ(G)𝚫+1 with χ(G) the chromatic number of this graph.

In planar graphs, we have χ(G)4.

Four color theorem on Wikipedia.