Further results on proper and strong set colorings of graphs

Abstract

A set coloring ? of a graph G is defined as an assignment of distinct subsets of a finite set X of colors to the vertices of G such that all the colors of the edges which are obtained as the symmetric differences of the sets assigned to their end-vertices are distinct. Additionally, if all the sets on the vertices and edges of G form the set of all nonempty subsets of X, then the coloring ? is said to be a strong set coloring, and the graph G is called strongly set colorable. If all the nonempty subsets of X are obtained on the edges of G, then ? is called a proper set coloring, and such a graph G is called properly set colorable. The set coloring number of a graph G, denoted by ?(G), is the smallest cardinality of a set X such that G has a set coloring with respect to X. This paper discusses the set coloring number of certain classes of graphs and the construction of strongly set colorable caterpillars which are also properly set colorable. An upper bound for b is found for K 3,b to admit set coloring with set coloring number n.