# Set colorings in perfect graphs

Ralucca Gera; Futaba Okamoto; Craig Rasmussen; Ping Zhang

Mathematica Bohemica (2011)

- Volume: 136, Issue: 1, page 61-68
- ISSN: 0862-7959

## Access Full Article

top## Abstract

top## How to cite

topGera, 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 -

## References

top- Chartrand, G., Mitchem, J., 10.1007/BFb0059422, Recent Trends in Graph Theory. Proc. 1st New York City Graph Theory Conf. 1970, Lect. Notes Math 186 55-61 (1971), Springer Berlin. (1971) Zbl0211.56702MR0289354DOI10.1007/BFb0059422
- Chartrand, G., Okamoto, F., Rasmussen, C., Zhang, P., The set chromatic number of a graph, Discuss. Math., Graph Theory (to appear). MR2642800
- Chartrand, G., Polimeni, A. D., 10.2140/pjm.1974.55.39, Pac. J. Math. 55 (1974), 39-43. (1974) Zbl0284.05107MR0371707DOI10.2140/pjm.1974.55.39
- Chvátal, V., Hammer, P., Set-packing problems and threshold graphs, CORR 73-21 University of Waterloo (1973). (1973)
- Finck, H. J., On the chromatic numbers of a graph and its complement, Theory of Graphs. Proc. Colloq., Tihany, 1966 Academic Press New York (1968), 99-113. (1968) Zbl0157.55201MR0232704
- Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs, 2nd edition, Elsevier Amsterdam (2004). (2004) MR2063679
- Hammer, P., Simeone, B., 10.1007/BF02579333, Combinatorica 1 (1981), 275-284. (1981) Zbl0492.05043MR0637832DOI10.1007/BF02579333
- Nordhaus, E. A., Gaddum, J. W., 10.2307/2306658, Am. Math. Mon. 63 (1956), 175-177. (1956) Zbl0070.18503MR0078685DOI10.2307/2306658
- Stewart, B. M., 10.1016/S0021-9800(69)80126-2, J. Comb. Theory 6 (1969), 217-218. (1969) MR0274339DOI10.1016/S0021-9800(69)80126-2

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.