The set chromatic number of a graph

Thumbnail Image
Files
The_set_chromatic_number_of_a_graph.pdf (157.3 KB)
Authors
Chartrand, Gary
Okamoto, Futaba
Rasmussen, Craig W.
Zhang, Ping
Subjects
neighbor-distinguishing coloring
set coloring
neighborhood color set
Advisors
Date of Issue
2009
Date
2009
Publisher
Language
en_US
Abstract
For a nontrivial connected graph G, let c : V (G) → ℕ be a vertex coloring of G where adjacent vertices may be colored the same. For a vertex v of G, the neighborhood color set NC(v) is the set of colors of the neighbors of v. The coloring c is called a set coloring if NC(u) ≠ 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 χ(s)(G) of G. The set chromatic numbers of some well-known classes of graphs are determined and several bounds are established for the set chromatic number of a graph in terms of other graphical parameters.
Type
Article
Description
URI
https://hdl.handle.net/10945/56997
Series/Report No
Department
Applied Mathematics
Organization
Naval Postgraduate School (U.S.)
Identifiers
NPS Report Number
Sponsors
Funder
Format
18 p.
Citation
Chartrand, G., Okamoto, F., Rasmussen, C.W. & Zhang, P. 2009, "The set chromatic number of a graph", Discussiones Mathematicae Graph Theory, vol. 29, pp. 545-561.
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.
Collections
Publications