On the b-chromatic number of regular bounded graphs

DOI10.1016/J.DAM.2015.04.017MaRDI QIDQ2355753zbMATH OpenOpenAlexFDO

Authors El Sahili Amine, Kouider Mekkia, Mortada Maidoun

Publication date 24 July 2015

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

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

zbMATH Keywords

\(b\)-chromatic number\(b\)-coloringproper coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: A $b$-coloring of a graph is a proper coloring such that every color class contains a vertex adjacent to at least one vertex in each of the other color classes. The $b$-chromatic number of a graph $G$, denoted by $b(G)$, is the maximum integer $k$ such that $G$ admits a $b$-coloring with $k$ colors. El Sahili and Kouider conjectured that $b(G)=d+1$ for $d$-regular graph with girth 5, $dgeq4$. In this paper, we prove that this conjecture holds for $d$-regular graph with at least $d^3+d$ vertices. More precisely we show that $b(G)=d+$1 for $d$-regular graph with at least $d^3+d$ vertices and containing no cycle of order 4. We also prove that $b(G)=d+1$ for $d$-regular graphs with at least $2d^3+2d-2d^2$ vertices improving Cabello and Jakovac bound.

Recommendations

• On the \(b\)-chromatic number of regular graphs
• The b-chromatic number and f-chromatic vertex number of regular graphs
• On \(b\)-colorings in regular graphs
• On the \(b\)-chromatic number of regular graphs without 4-cycle
• The b-chromatic number of regular graphs via the edge-connectivity

Cites work

• \(b\)-chromatic number of Cartesian product of some families of graphs
• Bounds for the b-chromatic number of G-v
• scientific article; zbMATH DE number 5717278 (Why is no real title available?)
• scientific article; zbMATH DE number 1953103 (Why is no real title available?)
• scientific article; zbMATH DE number 1919512 (Why is no real title available?)
• On \(b\)-colorings in regular graphs
• On approximating the b-chromatic number
• On the \(b\)-chromatic number of regular graphs
• On the \(b\)-dominating coloring of graphs
• The b-chromatic number and f-chromatic vertex number of regular graphs
• The b-chromatic number of a graph

Cited in

(14)

• On \(b\)-colorings in regular graphs
• The b-chromatic number and related topics -- a survey
• The \(b\)-continuity of graphs with large girth
• On the \(b\)-chromatic number of regular graphs
• Graphs of girth at least 7 have high \(b\)-chromatic number
• Bounds for the b-chromatic number of subgraphs and edge-deleted subgraphs
• The b-chromatic number of regular graphs via the edge-connectivity
• On the \(b\)-chromatic number of regular graphs without 4-cycle
• The b-chromatic number and f-chromatic vertex number of regular graphs
• On the b-coloring of tight graphs
• Some bounds for the b-chromatic number of a generalized Hamming graph
• On b-greedy colourings and z-colourings
• A new approach to b-coloring of regular graphs
• On quasi-monotonous graphs

This page was built for publication: On the \(b\)-chromatic number of regular bounded graphs

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