Some results on the b-chromatic number in complementary prism graphs
RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 4, pp. 1187-1195.

A b-coloring of a graph G is a proper coloring of G with k colors such that each color class has a vertex that is adjacent to at least one vertex of every other color classes. The b-chromatic number is the largest integer k for which G has a b-coloring with k colors. In this paper, we present some results on b-coloring in complementary prism graphs.

DOI : 10.1051/ro/2018054
Classification : 05C15
Mots-clés : b-coloring, b-chromatic number, complementary prism graph
Bendali-Braham, Amel 1 ; Ikhlef-Eschouf, Noureddine 1 ; Blidia, Mostafa 

1 
@article{RO_2019__53_4_1187_0,
     author = {Bendali-Braham, Amel and Ikhlef-Eschouf, Noureddine and Blidia, Mostafa},
     title = {Some results on the b-chromatic number in complementary prism graphs},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {1187--1195},
     publisher = {EDP-Sciences},
     volume = {53},
     number = {4},
     year = {2019},
     doi = {10.1051/ro/2018054},
     mrnumber = {3986372},
     zbl = {1425.05052},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2018054/}
}
TY  - JOUR
AU  - Bendali-Braham, Amel
AU  - Ikhlef-Eschouf, Noureddine
AU  - Blidia, Mostafa
TI  - Some results on the b-chromatic number in complementary prism graphs
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2019
SP  - 1187
EP  - 1195
VL  - 53
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2018054/
DO  - 10.1051/ro/2018054
LA  - en
ID  - RO_2019__53_4_1187_0
ER  - 
%0 Journal Article
%A Bendali-Braham, Amel
%A Ikhlef-Eschouf, Noureddine
%A Blidia, Mostafa
%T Some results on the b-chromatic number in complementary prism graphs
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2019
%P 1187-1195
%V 53
%N 4
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2018054/
%R 10.1051/ro/2018054
%G en
%F RO_2019__53_4_1187_0
Bendali-Braham, Amel; Ikhlef-Eschouf, Noureddine; Blidia, Mostafa. Some results on the b-chromatic number in complementary prism graphs. RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 4, pp. 1187-1195. doi : 10.1051/ro/2018054. http://www.numdam.org/articles/10.1051/ro/2018054/

[1] A. Alhashim, W.J. Desormeaux and T.W. Haynes, Roman domination in complementary prisms. Australas. J. Combin. 68 (2017) 218–228. | MR | Zbl

[2] R. Balakrishnan and T. Kavaskar, b-coloring of Kneser graphs. Discrete Appl. Math. 160 (2012) 9–14. | DOI | MR | Zbl

[3] C. Berge, Graphs. North Holland, Amsterdam/New York (1985). | Zbl

[4] M. Blidia, F. Maffray and Z. Zemir, On b-colorings in regular graphs. Discrete Appl. Math. 157 (2009) 1787–1793. | DOI | MR | Zbl

[5] V. Campos, C. Linhares-Sales, F. Maffray and A. Silva, b-chromatic number of cacti. Electron. Notes Discrete Math. 35 (2009) 281–286. | DOI | MR | Zbl

[6] B. Effantin, The b-chromatic number of power graphs of complete caterpillars. J. Discrete Math. Sci. Cryptogr. 8 (2005) 483–502. | DOI | MR | Zbl

[7] B. Effantin and H. Kheddouci, The b-chromatic number of some power graphs. Discrete Math. Theor. Comput. Sci. 6 (2003) 45–54. | MR | Zbl

[8] B. Effantin and H. Kheddouci, Exact values for the b-chromatic number of a power complete k-ary tree. J. Discrete Math. Sci. Cryptogr. 8 (2005) 117–129. | DOI | MR | Zbl

[9] H. Hajiabolhassan, On the b-chromatic number of Kneser graphs. Discrete Appl. Math. 158 (2010) 232–234. | DOI | MR | Zbl

[10] T.W. Haynes, M.A. Henning, P.J. Slater and L.C. Van Der Merwe, The complementary product of two graphs. Bull. Inst. Comb. Appl. 51 (2007) 21–30. | MR | Zbl

[11] T.W. Haynes, M.A. Henning, P.J. Slater and L.C. Van Der Merwe, Domination and total domination in complementary prisms. J. Comb. Optim. 18 (2009) 23–37. | DOI | MR | Zbl

[12] T.W. Haynes, K.R.S. Holmes, D.R. Koessler and L. Sewell, Locating-domination in complementary prisms of paths and cycles. Congr. Numerantium 199 (2009) 45–55. | MR | Zbl

[13] R.W. Ivring and D.F. Manlove, The b-chromatic number of a graph. Discrete Appl. Math. 91 (1999) 127–141. | DOI | MR | Zbl

[14] M. Jakovac and S. Klavžar, The b-chromatic number of cubic graphs. Graphs Comb. 26 (2010) 107–118. | DOI | MR | Zbl

[15] M. Jakovac and I. Peterin, On the b-chromatic number of some products. Studia Sci. Math. Hungar. 49 (2012) 156–169. | MR | Zbl

[16] M. Jakovac and I. Peterin, The b-chromatic number and related topics-a survey. Discrete Appl. Math. 235 (2018) 184–201. | DOI | MR | Zbl

[17] P. Janseana, S. Rueangthampisan and N. Ananchuen, Extendability of the complementary prism of 2-regular graphs. Thai J. Math. 14 (2016) 31–41. | MR | Zbl

[18] R. Javadi and B. Omoomi, On b-coloring of the Kneser graphs. Discrete Math. 309 (2009) 4399–4408. | DOI | MR | Zbl

[19] A. Kohl, The b-chromatic number of powers of cycles. Discrete Math. Theor. Comput. Sci. 15 (2013) 147–156. | MR | Zbl

[20] J. Kratochívl, Z. Tuza and M. Voigt, On the b-chromatic number of graphs. Lect. Notes Comput. Sci. 2573 (2002) 310–320. | DOI | MR | Zbl

[21] W.-H. Lin and G.J. Chang, b-coloring of tight bipartite graphs and the Erdös–Faber–Lovász conjecture. Discrete Appl. Math. 161 (2013) 1060–1066. | DOI | MR | Zbl

[22] C. Linhares-Sales and L. Sampaio, b-coloring of m-tight graphs. Electron. Notes Discrete Math. 35 (2009) 209–214. | DOI | MR | Zbl

[23] F. Maffray and A. Silva, b-colouring the Cartesian product of trees and some other graphs. Discrete Appl. Math. 161 (2013) 650–669. | DOI | MR | Zbl

[24] F. Maffray and A. Silva, b-colouring outerplanar graphs with large girth. Discrete Math. 312 (2012) 1796–1803. | DOI | MR | Zbl

[25] D.F. Manlove, Minimaximal and maximinimal optimization problems: a partial order-based approach. Ph.D. thesis, technical report tr-1998-27 of the Computing Science Department of Glasgow University (1998).

[26] H.D. Russell, Italian domination in complementary prisms. Electronic thesis and dissertations. Paper 3429 (2018).

Cité par Sources :