New bounds for the \(b\)-chromatic number of vertex deleted graphs (Q2243141)

A \(b\)-coloring is a proper vertex coloring of a graph such that each color class contains a vertex that has a neighbor in all other color classes. The \(b\)-chromatic number of a graph \(G\) is the largest integer \(\chi_b(G)\) for which \(G\) admits a \(b\)-coloring with \(\chi_b(G)\) colors. For a vertex \(v\) of a graph \(G\), the vertex-deleted subgraph of \(G\) is obtained by deleting \(v\) and all edges incident to \(v\). It is known that the difference between the \(b\)-chromatic number of a graph and the \(b\)-chromatic number of its vertex-deleted subgraph can be arbitrarily large. The main goal of this note is to establish lower bounds on the \(b\)-chromatic number of a vertex-deleted subgraph of \(G\), where \(G\) belongs to a class of claw-free graphs or chordal graphs. In particular, it is shown that the \(b\)-chromatic number of a vertex-deleted subgraph of \(G\) can have a maximum variation of two colors compared to the \(b\)-chromatic number of \(G\) if \(G\) is a claw-free graph, while this difference is at most one if \(G\) is a chordal graph. The paper concludes with a result, which shows that the difference between the \(b\)-chromatic number of a graph with girth of at least five and the \(b\)-chromatic number of its vertex-deleted subgraph cannot be bigger than two.