کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4654368 | 1632821 | 2009 | 10 صفحه PDF | دانلود رایگان |
A set coloring of the graph GG is an assignment (function) of distinct subsets of a finite set XX 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 XX. A set coloring is called a proper set coloring if all the nonempty subsets of XX 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.
Journal: European Journal of Combinatorics - Volume 30, Issue 4, May 2009, Pages 986–995