Currently displaying 1 – 3 of 3

Showing per page

Order by Relevance | Title | Year of publication

Set colorings in perfect graphs

Ralucca GeraFutaba OkamotoCraig RasmussenPing Zhang — 2011

Mathematica Bohemica

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 V ( 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 ) . We show that the decision variant of determining χ s ( G ) is NP-complete in the general case, and show that χ s ( G ) can be...

The set chromatic number of a graph

Gary ChartrandFutaba OkamotoCraig W. RasmussenPing Zhang — 2009

Discussiones Mathematicae Graph Theory

For a nontrivial connected graph G, let c: V(G)→ N 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 χₛ(G) of G. The set chromatic numbers of some well-known classes of graphs are determined...

Set vertex colorings and joins of graphs

Futaba OkamotoCraig W. RasmussenPing Zhang — 2009

Czechoslovak Mathematical Journal

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 ) . 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...

Page 1

Download Results (CSV)