Opuscula Mathematica (Jan 2015)

On b-vertex and b-edge critical graphs

  • Noureddine Ikhlef Eschouf,
  • Mostafa Blidia

DOI
https://doi.org/10.7494/OpMath.2015.35.2.171
Journal volume & issue
Vol. 35, no. 2
pp. 171 – 180

Abstract

Read online

A \(b\)-coloring is a coloring of the vertices of a graph such that each color class contains a vertex that has a neighbor in all other color classes, and the \(b\)-chromatic number \(b(G)\) of a graph \(G\) is the largest integer \(k\) such that \(G\) admits a \(b\)-coloring with \(k\) colors. A simple graph \(G\) is called \(b^{+}\)-vertex (edge) critical if the removal of any vertex (edge) of \(G\) increases its \(b\)-chromatic number. In this note, we explain some properties in \(b^{+}\)-vertex (edge) critical graphs, and we conclude with two open problems.

Keywords