| Title:
|
Set colorings in perfect graphs (English) |
| Author:
|
Gera, Ralucca |
| Author:
|
Okamoto, Futaba |
| Author:
|
Rasmussen, Craig |
| Author:
|
Zhang, Ping |
| Language:
|
English |
| Journal:
|
Mathematica Bohemica |
| ISSN:
|
0862-7959 (print) |
| ISSN:
|
2464-7136 (online) |
| Volume:
|
136 |
| Issue:
|
1 |
| Year:
|
2011 |
| Pages:
|
61-68 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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})$. (English) |
| Keyword:
|
set coloring |
| Keyword:
|
perfect graph |
| Keyword:
|
NP-completeness |
| MSC:
|
05C15 |
| MSC:
|
05C17 |
| MSC:
|
05C35 |
| MSC:
|
05C70 |
| idZBL:
|
Zbl 1224.05171 |
| idMR:
|
MR2807709 |
| DOI:
|
10.21136/MB.2011.141450 |
| . |
| Date available:
|
2011-03-31T11:26:42Z |
| Last updated:
|
2020-07-29 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/141450 |
| . |
| Reference:
|
[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. Zbl 0211.56702, MR 0289354, 10.1007/BFb0059422 |
| Reference:
|
[2] Chartrand, G., Okamoto, F., Rasmussen, C., Zhang, P.: The set chromatic number of a graph.Discuss. Math., Graph Theory (to appear). MR 2642800 |
| Reference:
|
[3] Chartrand, G., Polimeni, A. D.: Ramsey theory and chromatic numbers.Pac. J. Math. 55 (1974), 39-43. Zbl 0284.05107, MR 0371707, 10.2140/pjm.1974.55.39 |
| Reference:
|
[4] Chvátal, V., Hammer, P.: Set-packing problems and threshold graphs.CORR 73-21 University of Waterloo (1973). |
| Reference:
|
[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. Zbl 0157.55201, MR 0232704 |
| Reference:
|
[6] Golumbic, M. C.: Algorithmic Graph Theory and Perfect Graphs, 2nd edition.Elsevier Amsterdam (2004). MR 2063679 |
| Reference:
|
[7] Hammer, P., Simeone, B.: The splittance of a graph.Combinatorica 1 (1981), 275-284. Zbl 0492.05043, MR 0637832, 10.1007/BF02579333 |
| Reference:
|
[8] Nordhaus, E. A., Gaddum, J. W.: On complementary graphs.Am. Math. Mon. 63 (1956), 175-177. Zbl 0070.18503, MR 0078685, 10.2307/2306658 |
| Reference:
|
[9] Stewart, B. M.: On a theorem of Nordhaus and Gaddum.J. Comb. Theory 6 (1969), 217-218. MR 0274339, 10.1016/S0021-9800(69)80126-2 |
| . |
