Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
set coloring; perfect graph; NP-completeness
set coloring; perfect graph; NP-completeness
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})$.
References:
[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 10.1007/BFb0059422 | MR 0289354 | Zbl 0211.56702
[2] Chartrand, G., Okamoto, F., Rasmussen, C., Zhang, P.: The set chromatic number of a graph. Discuss. Math., Graph Theory (to appear). MR 2642800
[3] Chartrand, G., Polimeni, A. D.: Ramsey theory and chromatic numbers. Pac. J. Math. 55 (1974), 39-43. DOI 10.2140/pjm.1974.55.39 | MR 0371707 | Zbl 0284.05107
[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 0232704 | Zbl 0157.55201
[6] Golumbic, M. C.: Algorithmic Graph Theory and Perfect Graphs, 2nd edition. Elsevier Amsterdam (2004). MR 2063679
[7] Hammer, P., Simeone, B.: The splittance of a graph. Combinatorica 1 (1981), 275-284. DOI 10.1007/BF02579333 | MR 0637832 | Zbl 0492.05043
[8] Nordhaus, E. A., Gaddum, J. W.: On complementary graphs. Am. Math. Mon. 63 (1956), 175-177. DOI 10.2307/2306658 | MR 0078685 | Zbl 0070.18503
[9] Stewart, B. M.: On a theorem of Nordhaus and Gaddum. J. Comb. Theory 6 (1969), 217-218. DOI 10.1016/S0021-9800(69)80126-2 | MR 0274339
Search
Partner of
