chromatic number

chromatic number

English

A minimal colouring of a graph whose chromatic number is 3

Noun

chromatic number (plural chromatic numbers)

1. (graph theory) The smallest number of colours needed to colour a given graph (i.e., to assign a colour to each vertex such that no two vertices connected by an edge have the same colour).

   The chromatic number of a complete graph ${\\displaystyle K_{n}}$ is ${\\displaystyle n}$; the chromatic number of a bipartite graph ${\\displaystyle K_{n,m}}$ is 2.

   • 1995, J. A. Bondy, 1: Basic Graph Theory: Paths and Circuits, Ronald L. Graham, Martin Grötschel, László Lovász (editors), Handbook of Combinatorics, Volume 1, Elsevier (North-Holland), page 48,

     The chromatic number of a graph ${\\displaystyle G}$ is the minimum value of ${\\displaystyle k}$ for which ${\\displaystyle G}$ is ${\\displaystyle k}$-colourable, and is denoted by ${\\displaystyle \\chi (G)}$. […] A more essential use of the chromatic number was made by Gallai (1968a) and Roy (1967), who discovered a simple relationship between the chromatic number of a digraph and the length of a longest directed path in the digraph, where the chromatic number ${\\displaystyle \\chi (D)}$ of a digraph ${\\displaystyle D}$ is defined to be the chromatic number of its underlying graph ${\\displaystyle G(D)}$.

   • 2004, Monia Discepoli, Ivan Gerace, Riccardo Mariani, Andrea Remigi, A Spectral Technique to Solve the Chromatic Number Problem in Circulant Graphs, Antonio Laganà, et al. (editors), Computational Science and Its Applications, ICCSA 2004: International Conference, Proceedings, Part 3, Springer, LNCS 3045, page 745,

     The CHROMATIC NUMBER is the minimum number of colors by means of which it is possible to color a graph in such a way that each vertex has a different color with respect to the adjacent vertices. Such a problem is an NP-hard problem [14] and [it] is even hard to obtain a good approximation of the solution in a polynomial time [17]. Although in a lot of computational problems the cost decreases when these problems are restricted to circulant graphs [6, 9], the CHROMATIC NUMBER problem is NP-hard even restrecting^[sic] to circulant graphs [9]. Moreover the problem of finding a good approximation of the CHROMATIC NUMBER problem on circulant graphs is also NP-hard.

   • 2009, Gary Chartrand, Ping Zhang, Chromatic Graph Theory, Taylor & Francis Group (CRC Press / Chapman & Hall), page 149,

     There is no general formula for the chromatic number of a graph. Consequently, we will often be concerned and must be content with (1) determining the chromatic number of some classes of interest and (2) determining upper and/or lower bounds for the chromatic number of a graph.

Usage notes

• Not to be confused with chromatic index (aka edge-chromatic number), which is the equivalent minimum number for an edge colouring.
• The chromatic number of a graph ${\\displaystyle G}$ is often denoted ${\\displaystyle \\chi (G)}$.

Synonyms

• (smallest number of colours needed to colour the vertices of a graph): vertex chromatic number (used to differentiate from edge chromatic number, etc.)

Derived terms

• chromatic number problem
• edge chromatic number
• harmonious chromatic number
• total chromatic number

Related terms

• achromatic number
• chromatic index
• chromatic polynomial

Translations

smallest number of colours needed to colour a graph

Hungarian: kromatikus szám (hu) Icelandic: litatala f Italian: numero cromatico m Spanish: número cromático m

See also

• k-colouring
• k-chromatic

Further reading

• Graph coloring on Wikipedia.Wikipedia
• Edge coloring on Wikipedia.Wikipedia
• Total coloring on Wikipedia.Wikipedia
• Hadwiger conjecture (graph theory) on Wikipedia.Wikipedia