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 ?
Vertex (edge) chromatic number and in particular its defining number of many graphs have not been determined yet.
The minimum value of k for which G is edge k-colored is called edge chromatic number of G and is denoted by [[chi].
Along with the exercises come both hints and solutions as he works through basic enumeration, the sieve process, permutations, classical enumeration problems in graph theory, parity and duality, connectivity, factors of graphs, independent sets of points, chromatic number, problems for graphs, the spectra of graphs and random walks, automorphisms of graphs, hypergraphs, Ramsey theory and reconstruction.
The minimal value of k is called the chromatic number of the graph G, commonly denoted by X(G).
4] For Mixed hypergraph H = (X, C, D), the largest i among all strict i-coloring of H call as the upper chromatic number H, said that for [bar.
3,4] For mixed hypergraph H'= (X, C, D), the largest i among all existence of strict i-Coloring known as the upper chromatic number H, said that for [[bar.
at](G), is called the adjacent-vertex distinguishing I-total chromatic number of G.
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.
We first state a purely topological result and then turn the existence of the vector bundle guaranteed by it into the existence of a graph with lower chromatic number than expected.
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.
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.
Circular chromatic number, the minimum p for which a circular coloring exists, is a refinement of the chromatic number of a graph, and similarly NP-hard to compute.