Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

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

Upper bounds on the b-chromatic number and results for restricted graph classes

100%

Alkhateeb M., Kohl A.

Discussiones Mathematicae Graph Theory

2011

tom 31

nr 4

709-735

A b-coloring of a graph G by k colors is a proper vertex coloring such that every color class contains a color-dominating vertex, that is, a vertex having neighbors in all other k-1 color classes. The b-chromatic number $χ_b(G)$ is the maximum integer k for which G has a b-coloring by k colors. Moreover, the graph G is called b-continuous if G admits a b-coloring by k colors for all k satisfying $χ(G) ≤ k ≤ χ_b(G)$. In this paper, we establish four general upper bounds on $χ_b(G)$. We present results on the b-chromatic number and the b-continuity problem for special graphs, in particular for disconnected graphs and graphs with independence number 2. Moreover we determine $χ_b(G)$ for graphs G with minimum degree δ(G) ≥ |V(G)|-3, graphs G with clique number ω(G) ≥ |V(G)|-3, and graphs G with independence number α(G) ≥ |V(G)|-2. We also prove that these graphs are b-continuous.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Alkhateeb M.

1 Kohl A.

1 2011

Wyniki wyszukiwania

Upper bounds on the b-chromatic number and results for restricted graph classes