The b-chromatic number and f-chromatic vertex number of regular graphs

DOI10.1016/J.DAM.2014.07.011zbMATH Open1303.05059arXiv1302.4214OpenAlexW2003480521MaRDI QIDQ477335FDOQ477335

Authors: Amine El Sahili, Mekkia Kouider, Maidoun Mortada, H. Kheddouci 

Publication date: 3 December 2014

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

Abstract: The $b$-chromatic number of a graph $G$, denoted by $b(G)$, is the largest positive integer $k$ such that there exists a proper coloring for G with $k$ colors in which every color class contains at least one vertex adjacent to some vertex in each of the other color classes, such a vertex is called a dominant vertex. The $f$-chromatic vertex number of a $d$-regular graph $G$, denoted by $f(G)$, is the maximum number of dominant vertices of distinct colors in a proper coloring with $d+1$ colors. El Sahili and Kouider conjectured that $b(G)=d+1$ for any $d$-regular graph $G$ of girth 5. We study this conjecture by giving some partial answers under supplementary conditions.

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

Recommendations

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

zbMATH Keywords

coloringregular graphs\(b\)-chromatic number\(f\)-chromatic vertex number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

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?)
• On approximating the b-chromatic number
• On the \(b\)-chromatic number of regular bounded graphs
• On the \(b\)-dominating coloring of graphs
• On \(b\)-colorings in regular graphs

Cited In (5)

• The \(b\)-chromatic number of regular graphs via the edge-connectivity
• 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

This page was built for publication: The \(b\)-chromatic number and \(f\)-chromatic vertex number of regular graphs

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