Set colorings in perfect graphs

Gera, Ralucca, et al. "Set colorings in perfect graphs." Mathematica Bohemica 136.1 (2011): 61-68. <http://eudml.org/doc/196432>.

@article{Gera2011,
abstract = {For a nontrivial connected graph $G$, let $c\colon 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 \{\rm NC\}(v)$ is the set of colors of the neighbors of $v$. The coloring $c$ is called a set coloring if $\mathop \{\rm NC\}(u)\ne \mathop \{\rm 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 _\{\rm s\}(G)$. We show that the decision variant of determining $\chi _\{\rm s\}(G)$ is NP-complete in the general case, and show that $\chi _\{\rm s\}(G)$ can be efficiently calculated when $G$ is a threshold graph. We study the difference $\chi (G)-\chi _\{\rm 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 _\{\rm s\}(G)$ and $\chi _\{\rm s\}(\{\overline\{G\}\})$.},
author = {Gera, Ralucca, Okamoto, Futaba, Rasmussen, Craig, Zhang, Ping},
journal = {Mathematica Bohemica},
keywords = {set coloring; perfect graph; NP-completeness; set coloring; perfect graph; NP-completeness},
language = {eng},
number = {1},
pages = {61-68},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Set colorings in perfect graphs},
url = {http://eudml.org/doc/196432},
volume = {136},
year = {2011},
}

TY - JOUR
AU - Gera, Ralucca
AU - Okamoto, Futaba
AU - Rasmussen, Craig
AU - Zhang, Ping
TI - Set colorings in perfect graphs
JO - Mathematica Bohemica
PY - 2011
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 136
IS - 1
SP - 61
EP - 68
AB - For a nontrivial connected graph $G$, let $c\colon 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 {\rm NC}(v)$ is the set of colors of the neighbors of $v$. The coloring $c$ is called a set coloring if $\mathop {\rm NC}(u)\ne \mathop {\rm 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 _{\rm s}(G)$. We show that the decision variant of determining $\chi _{\rm s}(G)$ is NP-complete in the general case, and show that $\chi _{\rm s}(G)$ can be efficiently calculated when $G$ is a threshold graph. We study the difference $\chi (G)-\chi _{\rm 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 _{\rm s}(G)$ and $\chi _{\rm s}({\overline{G}})$.
LA - eng
KW - set coloring; perfect graph; NP-completeness; set coloring; perfect graph; NP-completeness
UR - http://eudml.org/doc/196432
ER -