Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: set coloring

Sortuj według:

Ogranicz wyniki do:

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

The set chromatic number of a graph

100%

Chartrand G., Okamoto F., Rasmussen C., Zhang P.

Discussiones Mathematicae Graph Theory

2009

tom 29

nr 3

545-561

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 and several bounds are established for the set chromatic number of a graph in terms of other graphical parameters.

A Tight Bound on the Set Chromatic Number

88%

Sereni J.-S., Yilma Z. B.

Discussiones Mathematicae Graph Theory

2013

tom 33

nr 2

461-465

We provide a tight bound on the set chromatic number of a graph in terms of its chromatic number. Namely, for all graphs G, we show that χs(G) > ⌈log2 χ(G)⌉ + 1, where χs(G) and χ(G) are the set chromatic number and the chromatic number of G, respectively. This answers in the affirmative a conjecture of Gera, Okamoto, Rasmussen and Zhang.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

1 Chartrand G.

1 Okamoto F.

1 Rasmussen C.

1 Sereni J.-S.

1 Yilma Z. B.

1 Zhang P.

1 2013

1 2009

Wyniki wyszukiwania

The set chromatic number of a graph

A Tight Bound on the Set Chromatic Number