Geodesic
b-Coloring of the Mycielskian of Some Classes of Graphs
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 2, pp. 363-381.

Voir la notice de l'article provenant de la source Library of Science

The b-chromatic number b(G) of a graph G is the maximum k for which G has a proper vertex coloring using k colors such that each color class contains at least one vertex adjacent to a vertex of every other color class. In this paper, we have mainly investigated on the b-chromatic number of the Mycielskian of regular graphs. In particular, we have obtained the exact value of the b-chromatic number of the Mycielskian of some classes of graphs. This includes a few families of regular graphs, graphs with b(G) = 2 and split graphs. In addition, we have found bounds for the b-chromatic number of the Mycielskian of some more families of regular graphs in terms of the bchromatic number of their original graphs. Also we have found b-chromatic number of the generalized Mycielskian of some regular graphs.
Keywords: b-coloring, b-chromatic number, Mycielskian of graphs, regular graphs 
@article{DMGT_2022_42_2_a3,
     author = {Raj, S. Francis and Gokulnath, M.},
     title = {b-Coloring of the {Mycielskian} of {Some} {Classes} of {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {363--381},
     publisher = {mathdoc},
     volume = {42},
     number = {2},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a3/}
}
TY  - JOUR
AU  - Raj, S. Francis
AU  - Gokulnath, M.
TI  - b-Coloring of the Mycielskian of Some Classes of Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 363
EP  - 381
VL  - 42
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a3/
LA  - en
ID  - DMGT_2022_42_2_a3
ER  - 
%0 Journal Article
%A Raj, S. Francis
%A Gokulnath, M.
%T b-Coloring of the Mycielskian of Some Classes of Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 363-381
%V 42
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a3/
%G en
%F DMGT_2022_42_2_a3
Raj, S. Francis; Gokulnath, M. b-Coloring of the Mycielskian of Some Classes of Graphs. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 2, pp. 363-381. http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a3/

[1] R. Balakrishnan and S. Francis Raj, Bounds for the b -chromatic number of the Mycielskian of some families of graphs, Ars Combin. 122 (2015) 89–96.

[2] R. Balakrishnan, S. Francis Raj and T. Kavaskar, b -chromatic number of Cartesian product of some families of graphs, Graphs Combin. 30 (2014) 511–520. https://doi.org/10.1007/s00373-013-1285-0

[3] R. Balakrishnan, S. Francis Raj and T. Kavaskar, b -coloring of Cartesian product of trees, Taiwanese J. Math. 20 (2016) 1–11. https://doi.org/10.11650/tjm.20.2016.5062

[4] R. Balakrishnan and T. Kavaskar, b -coloring of Kneser graphs, Discrete Appl. Math. 160 (2012) 9–14. https://doi.org/10.1016/j.dam.2011.10.022

[5] S. Cabello and M. Jakovac, On the b -chromatic number of regular graphs, Discrete Appl. Math. 159 (2011) 1303–1310. https://doi.org/10.1016/j.dam.2011.04.028

[6] T. Faik, About the b -continuity of graphs: ( Extended Abstract ), Electron. Notes Discrete Math. 17 (2004) 151–156. https://doi.org/10.1016/j.endm.2004.03.030

[7] T. Faik, La b-Continuité des b-Colorations: Complexité, Propriétés Structurelles et Algorithmes (PhD Thesis LRI, Univ. Orsay, France, 2005).

[8] P. Francis and S. Francis Raj, On b -coloring of powers of hypercubes, Discrete Appl. Math. 225 (2017) 74–86. https://doi.org/10.1016/j.dam.2017.03.005

[9] P. Hall, On representatives of subsets, J. London Math. Soc. 10 (1935) 26–30. https://doi.org/10.1112/jlms/s1-10.37.26

[10] R.W. Irving and D.F. Manlove, The b -chromatic number of a graph, Discrete Appl. Math. 91 (1999) 127–141. https://doi.org/10.1016/S0166-218X(98)00146-2

[11] M. Jakovac and I. Peterin, The b -chromatic number and related topics—A survey, Discrete Appl. Math. 235 (2018) 184–201. https://doi.org/10.1016/j.dam.2017.08.008

[12] R. Javadi and B. Omoomi, On b -coloring of the Kneser graphs, Discrete Math. 309 (2009) 4399–4408. https://doi.org/10.1016/j.disc.2009.01.017

[13] M. Kouider, b-Chromatic Number of a Graph, Subgraphs and Degrees (Res. Rep. 1392 LRI, Univ. Orsay, France, 2004).

[14] M. Kouider and A. El-Sahili, About b-Colouring of Regular Graphs (Res. Rep. 1432 LRI, Univ. Orsay, France, 2006).

[15] M. Kouider and M. Mahéo, Some bounds for the b -chromatic number of a graph, Discrete Math. 256 (2002) 267–277. https://doi.org/10.1016/S0012-365X(01)00469-1

[16] J. Kratochvíl, Zs. Tuza and M. Voigt, On the b -chromatic number of graphs, in: 28th International Workshop WG 2002, (Graph-Theoretic Concepts in Computer Science, Lect. Notes Comput. Sci. 2573, 2002) 310–320. https://doi.org/10.1007/3-540-36379-3_27

[17] P.C.B. Lam, G. Gu, W. Lin and Z. Song, Some properties of generalized Mycielski’s graphs, manuscript.

[18] P.C.B. Lam, G. Gu, W. Lin and Z. Song, Circular chromatic number and a generalization of the construction of Mycielski, J. Combin. Theory Ser. B 89 (2003) 195–205. https://doi.org/10.1016/S0095-8956(03)00070-4

[19] J. Mycielski, Sur le coloriage des graphes, Colloq. Math. 3 (1955) 161–162. https://doi.org/10.4064/cm-3-2-161-162

[20] S. Shaebani, On b -continuity of Kneser graphs of type KG (2 k + 1, k ), Ars Combin. 119 (2015) 143–147.

[21] D.B. West, Introduction to Graph Theory, Vol. 2 (Prentice-Hall, Englewood Cliffs, 2000).