SUO: Re: Graphs, Labels, Isomorphisms
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
GLI. Note 14
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
My glossing of painted, colored, labeled, and rooted graphs
exhibits different degrees of standardization as one passes
along the series of terms.
The meanings of "labeled" and "rooted" are pretty much fixed
throughout the worldwide community of graph theorists and
graph appliers, with the slight reservation that computer
programmers will often take the rootedness so much for
granted that they may forget about the unrooted kinds
of graphs.
The use of "coloring" to describe a function from graph vertices
to a set of identifiers called "colors" is pretty much standard,
too, but it tends to be used in a couple of different contexts
that give it their different nuances of meaning in each case.
The primary idea appears to be that of an arbitrary coloring,
just any old function from the set of points to the set of
identifier "colors", then there is the secondary notion
that the coloring should satisfy a particular set of
coloring constraints, norms, restrictions, or rules,
for example, most typically, that adjacent nodes
should not be colored with the same colors.
My use of "painted" is much less standard, but is borrowed
from a standard usage in a region of graphical game theory.
At any rate, the more formal distinctions between 1-1 functions,
functions in general, and arbitary relations are always available
to resolve any possible ambiguity between the respective concepts
of labelings, colorings, and paintings of graphs with the elements
from a set of identifiers, that will then be referred to as labels,
colors, or paints, as the case may be. All of this is dispensable,
of course, in favor of less florid genres of speech, but experience
teaches that it really does serve to motivate the intuition through
many long trials of observation, conjecture, and proof.
Jon Awbrey
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o