2011/05/14 by Saeed Shaebani, Shaebani, Saeed
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #math.CO
paper · pdf · doi:10.48550/arxiv.1105.2909
arxiv created 2011/05/14 · openalex publication_date 2011/05/14 · arxiv updated 2011/05/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
\noindent The b-chromatic number of a graph G, denoted by ϕ(G), is the largest integer k that G admits a proper coloring by k colors, such that each color class has a vertex that is adjacent to at least one vertex in each of the other color classes. El Sahili and Kouider [About b-colorings of regular graphs, Res. Rep. 1432, LRI, Univ. Orsay, France, 2006] asked whether it is true that every d-regular graph G of girth at least 5 satisfies ϕ(G)=d+1. Blidia, Maffray, and Zemir [On b-colorings in regular graphs, Discrete Appl. Math. 157 (2009), 1787-1793] showed that the Petersen graph provides a negative answer to this question, and then conjectured that the Petersen graph is the only exception. In this paper, we investigate a strengthened form of the question. The edge connectivity of a graph G, denoted by λ(G), is the minimum cardinality of a subset U of E(G) such that G∖ U is either disconnected or a graph with only one vertex. A d-regular graph G is called super-edge-connected if every minimum edge-cut is the set of all edges incident with a vertex in G, i.e., λ(G)=d and every minimum edge-cut of G isolates a vertex. We show that if G is a d-regular graph that contains no 4-cycle, then ϕ(G)=d+1 whenever G is not super-edge-connected.