The -chromatic number of regular graphs via the edge-connectivity

The b -chromatic number of a graph G , denoted by φ ( G ) , is the largest integer k such that G has a proper vertex coloring with k colors in which each color class contains a vertex that is adjacent to at least one vertex in each of the other color classes. El Sahili and Kouider asked whether φ ( G ) = d + 1 for every d -regular graph G with girth at least 5 . Blidia, Maffray, and Zemir showed that the Petersen graph provides a negative answer to this question and conjectured that the Petersen graph is the only exception. In this note, we investigate a strengthened form of the question. egular graph G is super-edge-connected if every minimum edge-cut is the set of all edges incident to one vertex in G , i.e., the edge-connectivity of G is equal to d and deleting every minimum edge-cut of G isolates a vertex. We show that if G is a d -regular graph that contains no 4 -cycle as a subgraph, then φ ( G ) = d + 1 whenever G is not super-edge-connected.