On set colorings of complete bipartite graphs
Steffen Grüter, Andreas Holtkamp, Michel Surmacs · RWTH Publications (RWTH Aachen) · 2011
In European J. Combin. 30 (2009), 986–995, S. M. Hegde recently introduced set colorings of a graph G as an assignment (function) of distinct subsets of a finite set X of colors to the vertices of G, where the colors of the edges are obtained as the symmetric difference of the sets assigned to their end vertices (which are also distinct). 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 properly set colorable if it admits a proper set coloring. In this paper we give a proof for Hegde’s conjecture that the complete bipartite graph Ka,b is properly set colorable if and only if one of the partition sets is of cardinality 1, and the other one of cardinality 2 n − 1 for some positive integer n.