Exact coloring
Encyclopedia
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, an exact coloring is a (proper) vertex coloring
Graph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...
in which every pair of colors appears on exactly one pair of adjacent vertices. In essence, an exact coloring is a coloring that is both harmonious
Harmonious coloring
In graph theory, a harmonious coloring is a vertex coloring in which every pair of colors appears on at most one pair of adjacent vertices...
and complete
Complete coloring
In graph theory, complete coloring is the opposite of harmonious coloring in the sense that it is a vertex coloring in which every pair of colors appears on at least one pair of adjacent vertices. Equivalently, a complete coloring is minimal in the sense that it cannot be transformed into a proper...
. Graphs that admit exact colorings have been classified.
External links
- http://www.maths.dundee.ac.uk/~kedwards/biblio.html A Bibliography of Harmonious Colourings and Achromatic Number by Keith Edwards