Set vertex colorings and joins of graphs |
| |
Authors: | Futaba Okamoto Craig W Rasmussen Ping Zhang |
| |
Institution: | (1) Department of Mathematics, Dayalbagh Educational Institute, Agra, India |
| |
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 x
s
(G). A study is made of the set chromatic number of the join G+H of two graphs G and H. Sharp lower and upper bounds are established for x
s
(G + H) in terms of x
s
(G), x
s
(H), and the clique numbers ω(G) and ω(H). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|