Set colorings of graphs

Abstract

A set coloring of the graph G is an assignment (function) of distinct subsets of a finite set X of colors to the vertices of the graph, where the colors of the edges are obtained as the symmetric differences of the sets assigned to their end vertices which are also distinct. A set coloring is called a strong set coloring if sets on the vertices and edges are distinct and together form the set of all nonempty subsets of X. A set coloring is called a proper set coloring if all the nonempty subsets of X are obtained on the edges. A graph is called strongly set colorable (properly set colorable) if it admits a strong set coloring (proper set coloring). In this paper we give some necessary conditions for a graph to admit a strong set coloring (a proper set coloring), characterize strongly set colorable complete bipartite graphs and strongly (properly) set colorable complete graphs, etc. Also, we give a construction of a planar strongly set colorable graph from a planar graph, a strongly set colorable tree from a tree and a properly set colorable tree from a tree, etc., thereby showing their embeddings. 2008 Elsevier Ltd. All rights reserved.