×

Some bounds for the \(b\)-chromatic number of a graph. (English) Zbl 1008.05056

The \(b\)-chromatic number of a graph \(G\) is the maximum number \(k\) of colours that can be used to colour the vertices of \(G\), such that we obtain a proper colouring of \(G\) and each colour \(i\) has at least one representant \(x_i\) adjacent to a vertex with each colour \(j\), \(1\leq j\leq k\), \(j\neq i\). Some general properties of the \(b\)-chromatic number are established. The main result provides a lower bound for the \(b\)-chromatic number of the Cartesian product of two graphs.

MSC:

05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI