Combinatorics/Game theory
A characterization of be-critical trees
Comptes Rendus. Mathématique, Volume 356 (2018) no. 2, pp. 115-120.

The b-chromatic number of a graph G is the largest integer k such that G admits a proper coloring with k colors for which each color class contains a vertex that has at least one neighbor in all the other k1 color classes. A graph G is called be-critical if the contraction of any edge e of G decreases the b-chromatic number of G. The purpose of this paper is the characterization of all be-critical trees.

Le nombre b-chromatique d'un graphe G est le plus grand entier k tel que G admette une coloration propre avec k couleurs, pour laquelle toute classe de couleur contient un sommet qui a au moins un voisin dans toutes les autres k1 classes de couleur. Un graphe G est appelé be-critique si la contraction de toute arête e de G fait diminuer le nombre b-chromatique de G. Le but de cet article est la caractérisation de tous les arbres be-critiques.

Received:
Accepted:
Published online:
DOI: 10.1016/j.crma.2018.01.006
Bendali-Braham, Amel 1; Ikhlef-Eschouf, Noureddine 2; Blidia, Mostafa 3

1 Laboratory of Mechanics, Physics and Mathematical Modeling, Faculty of Sciences, University of Médéa, Algeria
2 Department of Mathematics and Computer Science, Faculty of Sciences, University of Médéa, Algeria
3 Laboratory LAMDA-RO, Department of Mathematics, University of Blida 1, B.P. 270, Blida, Algeria
@article{CRMATH_2018__356_2_115_0,
     author = {Bendali-Braham, Amel and Ikhlef-Eschouf, Noureddine and Blidia, Mostafa},
     title = {A characterization of \protect\emph{b}\protect\textsubscript{\protect\emph{e}}-critical trees},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {115--120},
     publisher = {Elsevier},
     volume = {356},
     number = {2},
     year = {2018},
     doi = {10.1016/j.crma.2018.01.006},
     language = {en},
     url = {http://www.numdam.org/articles/10.1016/j.crma.2018.01.006/}
}
TY  - JOUR
AU  - Bendali-Braham, Amel
AU  - Ikhlef-Eschouf, Noureddine
AU  - Blidia, Mostafa
TI  - A characterization of be-critical trees
JO  - Comptes Rendus. Mathématique
PY  - 2018
SP  - 115
EP  - 120
VL  - 356
IS  - 2
PB  - Elsevier
UR  - http://www.numdam.org/articles/10.1016/j.crma.2018.01.006/
DO  - 10.1016/j.crma.2018.01.006
LA  - en
ID  - CRMATH_2018__356_2_115_0
ER  - 
%0 Journal Article
%A Bendali-Braham, Amel
%A Ikhlef-Eschouf, Noureddine
%A Blidia, Mostafa
%T A characterization of be-critical trees
%J Comptes Rendus. Mathématique
%D 2018
%P 115-120
%V 356
%N 2
%I Elsevier
%U http://www.numdam.org/articles/10.1016/j.crma.2018.01.006/
%R 10.1016/j.crma.2018.01.006
%G en
%F CRMATH_2018__356_2_115_0
Bendali-Braham, Amel; Ikhlef-Eschouf, Noureddine; Blidia, Mostafa. A characterization of be-critical trees. Comptes Rendus. Mathématique, Volume 356 (2018) no. 2, pp. 115-120. doi : 10.1016/j.crma.2018.01.006. http://www.numdam.org/articles/10.1016/j.crma.2018.01.006/

[1] Bendali-Braham, A.; Ikhlef-Eschouf, N.; Blidia, M. A characterization of edge b-critical graphs, Discrete Appl. Math. (2018) | DOI

[2] Berge, C. Graphs, North Holland, 1985

[3] Blidia, M.; Ikhlef Eschouf, N.; Maffray, F. On vertex b-critical trees, Opusc. Math., Volume 33 (2013) no. 1, pp. 19-28

[4] Ikhlef Eschouf, N. Characterization of some b-chromatic edge b-critical graphs, Australas. J. Comb., Volume 47 (2010), pp. 21-35

[5] Ikhlef Eschouf, N.; Blidia, M. On b-vertex and b-edge critical graphs, Opusc. Math., Volume 35 (2015) no. 2, pp. 171-180

[6] Ikhlef Eschouf, N.; Blidia, M.; Maffray, F. On edge b-critical graphs, Discrete Appl. Math., Volume 180 (2015), pp. 176-180

[7] Iring, R.W.; Manlove, D.F. The b-chromatic number of a graph, Discrete Appl. Math., Volume 91 (1999), pp. 127-141

[8] Jakovac, M.; Peterin, I. The b-chromatic number and related topics—a survey, Discrete Appl. Math., Volume 235 (2018), pp. 184-201

[9] Kratochvíl, J.; Tuza, Z.; Voigt, M. On the b-chromatic number of graphs, Lecture Notes in Comput. Sci., vol. 2573, 2002, pp. 310-320

[10] Manlove, D.F. Minimaximal and Maximinimal Optimization Problems: a Partial Order-Based Approach, Department of Computing Science, University of Glasgow, UK, 1998 (PhD thesis, technical report tr-1998-27)

Cited by Sources: