chromatic number

chromatic number

[krō′mad·ik ′nəm·bər]
(mathematics)
For a specified surface, the smallest number n such that for any decomposition of the surface into regions the regions can be colored with n colors in such a way that no two adjacent regions have the same color.

chromatic number

(mathematics)
The smallest number of colours necessary to colour the nodes of a graph so that no two adjacent nodes have the same colour.

See also: four colour map theorem.

Graph Theory Lessons.

Eric Weisstein's World Of Mathematics.

The Geometry Center.
Mentioned in ?
References in periodicals archive ?
Tahmasbpour and Borzooei [12] introduced two different approaches corresponding to chromatic number of a bipolar fuzzy graph.
The concept of locating chromatic number is a marriage between the partition dimension and coloring of a graph, first introduced by Chartrand et al in 2002 [5].
Then, we provide a formula based on 0-1 integer programming to get chromatic number in 9-CAA.
If k is the smallest number of colors, the graph is said to be k-chromatic and k is called the chromatic number of the graph.
This result implies, in Section 5.1, that every graph G has regular-irregular chromatic index at most 6( [log [chi](G)] + 1), where [chi](G) denotes the classic chromatic number of G.
Keywords: game colouring number, marking game, activation strategy, graph power, forest, game chromatic number
In [2] Hadwiger formulated his well-known and deep conjecture linking the chromatic number z (G ) of a graph G with clique minors.
The following theorem presented by Mohar in [32] will be useful for determining the face chromatic number of a (4,6)-fullerene on the projective plane.
In this paper, we obtain the adjacent vertex-distinguishing I-total chromatic number of ladder graph by constructing method.
The 21 selected papers discuss such topics as the dynamic chromatic number of graphs, Euclidean designs and coherent configurations, the list coloring of graphs with cycles of length divisible by a given integer, the rational independence roots, a theorem on incidence matrices and quasi-random hyper-graphs, characterizing completely regular codes from an algebraic viewpoint, and the proportion of various graphs in graph-designs.
Definition 4 The chromatic number [gamma](G) of a graph G is the smallest number of colors needed to color the vertices of G so that no two adjacent vertices share the same color, i.e., the smallest value of k possible to obtain a k-coloring [6]
Later chapters deal with graph colorings, with material on vertex colorings and bounds for the chromatic number, vertex colorings of graphs embedded on surfaces, and a variety of restricted vertex colorings.