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

DOI10.1016/J.DISC.2013.08.001zbMATH Open1280.05045arXiv1105.2909OpenAlexW1964234691MaRDI QIDQ393940FDOQ393940

Authors: Saeed Shaebani 

Publication date: 24 January 2014

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: oindent The b-chromatic number of a graph $G$, denoted by $phi(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 $phi(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 $lambda(G)$, is the minimum cardinality of a subset $U$ of $E(G)$ such that $GsetminusU$ 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., $lambda(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 $phi(G)=d+1$ whenever $G$ is not super-edge-connected.

Full work available at URL: https://arxiv.org/abs/1105.2909

Recommendations

• On the \(b\)-chromatic number of regular graphs
• On the \(b\)-chromatic number of regular bounded graphs
• The \(b\)-chromatic number and \(f\)-chromatic vertex number of regular graphs
• The \(b\)-chromatic number of certain graphs and digraphs
• scientific article; zbMATH DE number 3961644
• scientific article; zbMATH DE number 1953103
• On the \(b\)-chromatic number of some graphs
• The total chromatic number of regular graphs whose complement is bipartite
• The \(b\)-chromatic number of some standard graphs
• scientific article; zbMATH DE number 5717278

zbMATH Keywords

\(b\)-coloring\(b\)-chromatic numberedge-connectivitysuper-edge-connected

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Connectivity (05C40)

Cites Work

• The b-chromatic number of a graph
• On the \(b\)-chromatic number of regular graphs
• Title not available (Why is that?)
• On the \(b\)-chromatic number of regular graphs without 4-cycle
• Title not available (Why is that?)
• The b-chromatic number of cubic graphs
• On \(b\)-colorings in regular graphs
• On \(b\)-coloring of the Kneser graphs

Cited In (7)

• The \(b\)-chromatic number and \(f\)-chromatic vertex number of regular graphs
• On the \(b\)-chromatic number of regular bounded graphs
• The \(b\)-chromatic number and related topics -- a survey
• On \(b\)-colorings in regular graphs
• On the \(b\)-chromatic number of regular graphs without 4-cycle
• On the \(b\)-chromatic number of regular graphs
• On \(b\)-vertex and \(b\)-edge critical graphs

This page was built for publication: The \(b\)-chromatic number of regular graphs via the edge-connectivity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q393940)