Vol. 57, No. 1, 1975

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 329: 1
Vol. 328: 1  2
Vol. 327: 1  2
Vol. 326: 1  2
Vol. 325: 1  2
Vol. 324: 1  2
Vol. 323: 1  2
Vol. 322: 1  2
Online Archive
The Journal
About the journal
Ethics and policies
Peer-review process
Submission guidelines
Submission form
Editorial board
ISSN: 1945-5844 (e-only)
ISSN: 0030-8730 (print)
Special Issues
Author index
To appear
Other MSP journals
Reconstructing colored graphs

Joseph M. Weinstein

Vol. 57 (1975), No. 1, 307–314

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.

Mathematical Subject Classification 2000
Primary: 05C15
Received: 4 June 1974
Published: 1 March 1975
Joseph M. Weinstein