b-coloring of the Mycielskian of some classes of graphs

DOI10.7151/DMGT.2265MaRDI QIDQ2118233zbMATH OpenOpenAlexWikidataFDO

Authors S. Francis Raj, M. Gokulnath

Publication date 22 March 2022

Published in Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported

Full work available at URL https://doi.org/10.7151/dmgt.2265

zbMATH Keywords

\(b\)-chromatic number\(b\)-coloringMycielskian of a graphregular graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Review text

Let \(G=(V,E)\) be a simple, finite, undirected graph. A \(b\)-coloring of \(G\) using \(k\) colors is a proper coloring of \(V\) in which each color class contains a vertex that is adjacent to a vertex of each other color class. The \(b\)-chromatic number \(b(G)\) of \(G\) is the largest \(k\) such that \(G\) has a \(b\)-coloring using \(k\) colors. For the Mycielskian \(\mu(G)\) of a \(k\)-regular graph \(G\) (\(k \geq 3\)) with girth at least 7 or with girth 5 having diameter at least 5 but not containing a \(C_{6}\), the authors show that \(b(\mu(G))=2k+1=2b(G)-1\). If \(G\) is of girth at least 6, they show that \(k+ \lfloor \frac{k+1}{2} \rfloor \leq b(\mu(G)) \leq 2k+1\), and if \(G\) is of girth at least 8, then \(\mu(G))\) is \(b\)-continuous. They also determine the \(b\)-chromatic number of the Mycielskian of split graphs and graphs with \(b(G)=2\). They conclude with some results on the \(b\)-chromatic number of the generalized Mycielskian of some families of regular graphs.

Recommendations

• \(b\)-coloring of the Mycielskian of regular graphs
• Bounds for the b-chromatic number of the Mycielskian of some families of graphs.
• \(b\)-chromatic sum of Mycielskian of paths
• The b-chromatic number of some standard graphs
• On the \(b\)-chromatic number of regular graphs

Cites work

• \(b\)-chromatic number of Cartesian product of some families of graphs
• \(b\)-coloring of Cartesian product of trees
• b-coloring of Kneser graphs
• About the b-continuity of graphs
• Bounds for the b-chromatic number of the Mycielskian of some families of graphs.
• Circular chromatic number and a generalization of the construction of Mycielski.
• scientific article; zbMATH DE number 1953103 (Why is no real title available?)
• On \(b\)-coloring of powers of hypercubes
• On \(b\)-coloring of the Kneser graphs
• On \(b\)-continuity of Kneser graphs of type \(\mathrm{KG}(2k+1,k)\).
• On the \(b\)-chromatic number of regular graphs
• Some bounds for the b-chromatic number of a graph
• Sur le coloriage des graphs
• The b-chromatic number and related topics -- a survey
• The b-chromatic number of a graph

Cited in

(7)

• \(b\)-coloring of the Mycielskian of regular graphs
• \(b\)-chromatic sum of Mycielskian of paths
• Bounds for the b-chromatic number of the Mycielskian of some families of graphs.
• The b-chromatic number of some standard graphs
• Graphs with large girth are \(b\)-continuous
• scientific article; zbMATH DE number 5038437 (Why is no real title available?)
• k-tuple total dominator chromatic number and Mycielskian graphs

This page was built for publication: \(b\)-coloring of the Mycielskian of some classes of graphs

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