r-tuple colorings of uniquely colorable graphs |
| |
Authors: | Dennis P. Geller |
| |
Affiliation: | Human Sciences and Technology Group, School of Advanced Technology, State University of New York, Binghamton, NY 13901, USA |
| |
Abstract: | An r-tuple coloring of a graph is one in which r colors are assigned to each point of the graph so that the sets of colors assigned to adjacent points are always disjoint. We investigate the question of whether a uniquely n-colorable graph can receive an r-tuple coloring with fewer than nr colors. We show that this cannot happen for n=3 and r=2 and that for a given n and r to establish the conjecture that no uniquely n-colorable graph can receive an r-tuple coloring from fewer than nr colors it suffices to prove it for on a finite set of uniquely n-colorable graphs. |
| |
Keywords: | Present address: Massachusetts Computer Associates 26 Princess Street Wakefield MA U.S.A. |
本文献已被 ScienceDirect 等数据库收录! |