Bounds for the b-Chromatic Number of Subgraphs and Edge-Deleted Subgraphs

• Autorzy: P. Francis , S. Francis Raj
• Języki publikacji: EN

Abstrakty

EN

A b-coloring of a graph G with k colors is a proper coloring of G using k colors in which each color class contains a color dominating vertex, that is, a vertex which has a neighbor in each of the other color classes. The largest positive integer k for which G has a b-coloring using k colors is the b-chromatic number b(G) of G. In this paper, we obtain bounds for the b- chromatic number of induced subgraphs in terms of the b-chromatic number of the original graph. This turns out to be a generalization of the result due to R. Balakrishnan et al. [Bounds for the b-chromatic number of G−v, Discrete Appl. Math. 161 (2013) 1173-1179]. Also we show that for any connected graph G and any e ∈ E(G), b(G - e) ≤ b(G) + [...] -2. Further, we determine all graphs which attain the upper bound. Finally, we conclude by finding bound for the b-chromatic number of any subgraph.

Słowa kluczowe

EN

b-coloring; b-chromatic number

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2016
• Tom: 36
• Numer: 4
• Strony: 959-976

Daty

wydano

2016-11-01

otrzymano

2015-04-28

poprawiono

2015-11-11

zaakceptowano

2016-01-08

online

2016-10-21

Twórcy

autor

P. Francis

• Department of Mathematics Pondicherry University Puducherry – 605014,

autor

S. Francis Raj

• Department of Mathematics Pondicherry University Puducherry – 605014,

Identyfikatory

DOI

10.7151/dmgt.1913