|
|
Close Help | ||||||||||||||
Ralucca Gera, Naval Postgraduate School, Monterey, CA 93943, USA, e-mail: rgera@nps.edu; Futaba Okamoto, University of Wisconsin - LaCrosse, LaCrosse, WI 54601, USA, e-mail: okamoto.futa@uwlax.edu; Craig Rasmussen (corresponding author), Department of Applied Mathematics, Naval Postgraduate School, Monterey, CA 93943, USA, e-mail: ras@nps.edu; Ping Zhang, Western Michigan University, Kalamazoo, MI 49008, USA, e-mail: ping.zhang@wmich.edu
Abstract: For a nontrivial connected graph $G$, let $c V(G)\rightarrow\mathbb{N}$ be a vertex coloring of $G$ where adjacent vertices may be colored the same. For a vertex $v \in V(G)$, the neighborhood color set $\mathop NC(v)$ is the set of colors of the neighbors of $v$. The coloring $c$ is called a set coloring if $\mathop NC(u)\neq\mathop NC(v)$ for every pair $u, v$ of adjacent vertices of $G$. The minimum number of colors required of such a coloring is called the set chromatic number $\chi_ s(G)$. We show that the decision variant of determining $\chi_ s(G)$ is NP-complete in the general case, and show that $\chi_ s(G)$ can be efficiently calculated when $G$ is a threshold graph. We study the difference $\chi(G)-\chi_ s(G)$, presenting new bounds that are sharp for all graphs $G$ satisfying $\chi(G)=\omega(G)$. We finally present results of the Nordhaus-Gaddum type, giving sharp bounds on the sum and product of $\chi_ s(G)$ and $\chi_ s({\overline G})$.
Keywords: set coloring, perfect graph, NP-completeness
Classification (MSC 2000): 05C15, 05C17, 05C35, 05C70
Full text available as PDF.
Access to the full text of journal articles on this site is restricted to the subscribers of Myris Trade. To activate your access, please contact Myris Trade at myris@myris.cz.
