Vol. 57, No. 1, 1975

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 307: 1  2
Vol. 306: 1  2
Vol. 305: 1  2
Vol. 304: 1  2
Vol. 303: 1  2
Vol. 302: 1  2
Vol. 301: 1  2
Vol. 300: 1  2
Online Archive
Volume:
Issue:
     
The Journal
Subscriptions
Editorial Board
Officers
Contacts
 
Submission Guidelines
Submission Form
Policies for Authors
 
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
Abstract

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
Milestones
Received: 4 June 1974
Published: 1 March 1975
Authors
Joseph M. Weinstein