Chromatic number
Jump to navigation
Jump to search
English
Noun
- Template:Lb 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).
- Template:Quote-book
- 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, Template:W 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 restrectingTemplate: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 Template:M (aka Template:M), which is the equivalent minimum number for an edge colouring.
- The chromatic number of a graph is often denoted .
Synonyms
Derived terms
Related terms
Translations
- Hungarian: Template:T+
- Icelandic: Template:T
- Italian: Template:T
- Spanish: Template:T