In a colouring of a graph, a vertex is b-chromatic if it is adjacent to a vertex of every other colour. We consider four well-studied colouring problems: b-Chromatic Number, Tight b-Chromatic Number, Fall Chromatic Number and Fall Achromatic Number, which fit into a framework based on whether every colour class has (i) at least one b-chromatic vertex, (ii) exactly one b-chromatic vertex, or (iii) all of its vertices being b-chromatic. By combining known and new results, we fully classify the computational complexity of b-Chromatic Number, Fall Chromatic Number and Fall Achromatic Number in H-free graphs. For Tight b-Chromatic Number in H-free graphs, we develop a general technique to determine new graphs H, for which the problem is polynomial-time solvable, and we also determine new graphs H, for which the problem is still NP-complete. We show, for the first time, the existence of a graph H such that in H-free graphs, b-Chromatic Number is NP-hard, while Tight b-Chromatic Number is polynomial-time solvable.

A b-chromatic colouring of a graph G is a proper k -colouring of the vertices of G , for some integer k , such that, for each colour i (1 ≤ i ≤ k) , there exists a vertex v of colour i such that v is adjacent to a vertex of colour j , for each j (1 ≤ j ≤ k, j ≠ i). The b-chromatic number of G is the maximum integer k such that G admits a b-chromatic colouring using k colours. In this paper we introduce the concept of a total b-chromatic colouring , which extends the notion of b -chromatic colourings to both vertices and edges in a graph. We show that the problem of computing the total b-chromatic number is NP-hard in general graphs. On the other hand for a subclass of caterpillars we give a polynomial-time algorithm to compute the total b-chromatic number, and indeed a total b-chromatic colouring with the maximum number of colours.