Article in volume
Authors:
S. Francis Raj
JRF in Discrete MathematicsSRC, Satra UniversityKumbakonam-612001INDIA
email: francisraj_s@yahoo.com
Title:
b-coloring of the Mycielskian of some classes of graphs
PDFSource:
Discussiones Mathematicae Graph Theory 42(2) (2022) 363-381
Received: 2019-02-11 , Revised: 2019-10-31 , Accepted: 2019-11-02 , Available online: 2019-12-16 , https://doi.org/10.7151/dmgt.2265
Abstract:
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 b-chromatic
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
References:
- 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.
- 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 - 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 - 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 - 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 - 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 - T. Faik, La b-Continuité des b-Colorations: Complexité, Propriétés Structurelles et Algorithmes (PhD Thesis LRI, Univ. Orsay, France, 2005).
- 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 - P. Hall, On representatives of subsets, J. London Math. Soc. 10 (1935) 26–30.
https://doi.org/10.1112/jlms/s1-10.37.26 - 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 - 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 - 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 - M. Kouider, b-Chromatic Number of a Graph, Subgraphs and Degrees (Res. Rep. 1392 LRI, Univ. Orsay, France, 2004).
- M. Kouider and A. El-Sahili, About b-Colouring of Regular Graphs (Res. Rep. 1432 LRI, Univ. Orsay, France, 2006).
- 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 - 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 - P.C.B. Lam, G. Gu, W. Lin and Z. Song, Some properties of generalized Mycielski's graphs, manuscript.
- 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 - J. Mycielski, Sur le coloriage des graphes, Colloq. Math. 3 (1955) 161–162.
https://doi.org/10.4064/cm-3-2-161-162 - S. Shaebani, On b-continuity of Kneser graphs of type $KG(2k + 1, k)$, Ars Combin. 119 (2015) 143–147.
- D.B. West, Introduction to Graph Theory, Vol. 2 (Prentice-Hall, Englewood Cliffs, 2000).
Close