Geodesic
Set colorings in perfect graphs
Mathematica Bohemica, Tome 136 (2011) no. 1, pp. 61-68
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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)\neq \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})$.
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)\neq \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})$.
DOI : 10.21136/MB.2011.141450
Classification : 05C15, 05C17, 05C35, 05C70
Keywords: set coloring; perfect graph; NP-completeness 
@article{10_21136_MB_2011_141450,
     author = {Gera, Ralucca and Okamoto, Futaba and Rasmussen, Craig and Zhang, Ping},
     title = {Set colorings in perfect graphs},
     journal = {Mathematica Bohemica},
     pages = {61--68},
     year = {2011},
     volume = {136},
     number = {1},
     doi = {10.21136/MB.2011.141450},
     mrnumber = {2807709},
     zbl = {1224.05171},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.2011.141450/}
}
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
SP  - 61
EP  - 68
VL  - 136
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.2011.141450/
DO  - 10.21136/MB.2011.141450
LA  - en
ID  - 10_21136_MB_2011_141450
ER  - 
%0 Journal Article
%A Gera, Ralucca
%A Okamoto, Futaba
%A Rasmussen, Craig
%A Zhang, Ping
%T Set colorings in perfect graphs
%J Mathematica Bohemica
%D 2011
%P 61-68
%V 136
%N 1
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.2011.141450/
%R 10.21136/MB.2011.141450
%G en
%F 10_21136_MB_2011_141450
Gera, Ralucca; Okamoto, Futaba; Rasmussen, Craig; Zhang, Ping. Set colorings in perfect graphs. Mathematica Bohemica, Tome 136 (2011) no. 1, pp. 61-68. doi: 10.21136/MB.2011.141450

[1] Chartrand, G., Mitchem, J.: Graphical theorems of the Nordhaus-Gaddum class. Recent Trends in Graph Theory. Proc. 1st New York City Graph Theory Conf. 1970, Lect. Notes Math 186 55-61 (1971), Springer Berlin. | DOI | MR | Zbl

[2] Chartrand, G., Okamoto, F., Rasmussen, C., Zhang, P.: The set chromatic number of a graph. Discuss. Math., Graph Theory (to appear). | MR

[3] Chartrand, G., Polimeni, A. D.: Ramsey theory and chromatic numbers. Pac. J. Math. 55 (1974), 39-43. | DOI | MR | Zbl

[4] Chvátal, V., Hammer, P.: Set-packing problems and threshold graphs. CORR 73-21 University of Waterloo (1973).

[5] 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. | MR | Zbl

[6] Golumbic, M. C.: Algorithmic Graph Theory and Perfect Graphs, 2nd edition. Elsevier Amsterdam (2004). | MR

[7] Hammer, P., Simeone, B.: The splittance of a graph. Combinatorica 1 (1981), 275-284. | DOI | MR | Zbl

[8] Nordhaus, E. A., Gaddum, J. W.: On complementary graphs. Am. Math. Mon. 63 (1956), 175-177. | DOI | MR | Zbl

[9] Stewart, B. M.: On a theorem of Nordhaus and Gaddum. J. Comb. Theory 6 (1969), 217-218. | DOI | MR

Cité par Sources :