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

DOI10.1016/J.DAM.2014.07.011MaRDI QIDQ477335zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

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

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

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.

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

Cites work

• scientific article; zbMATH DE number 5717278 (Why is no real title available?)
• scientific article; zbMATH DE number 1953103 (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 bounded graphs
• On the \(b\)-chromatic number of regular graphs
• On the \(b\)-chromatic number of regular graphs without 4-cycle
• On the \(b\)-dominating coloring of graphs
• The b-chromatic number of a graph

Cited in

(6)

• 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 without 4-cycle
• 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)