Vol. 57, No. 1, 1975

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 295: 1  2
Vol. 294: 1  2
Vol. 293: 1  2
Vol. 292: 1  2
Vol. 291: 1  2
Vol. 290: 1  2
Vol. 289: 1  2
Vol. 288: 1  2
Online Archive
The Journal
Editorial Board
Special Issues
Submission Guidelines
Submission Form
Author Index
To Appear
ISSN: 0030-8730
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