A colored graph G is a
graph with given “coloring” (i.e., function) defined on the nodes and edges. A
colored-graph isomorphism is a graph isomorphism which preserves color values. G is
reconstructible if G is isomorphic with H whenever H is a colored graph with the
same nodes as G and with H − x isomorphic with G − x for each node x. In this
paper known reconstruction methods and results are generalized to colored graphs. A
“colored” approach is used to give a simple proof of a recent black-and-white” result:
a block G is reconstructible if G has a node z with G − z a tree. New “colored”
concepts and methods are used to deduce such results as the following: a
colored graph G is reconstructible if each color appears on at most three
nodes.
