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 $k−1$ 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 $k−1$ 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.

Accepted:
Published online:
DOI: 10.1016/j.crma.2018.01.006

Amel Bendali-Braham 1; Noureddine Ikhlef-Eschouf 2; Mostafa Blidia 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 = {Amel Bendali-Braham and Noureddine Ikhlef-Eschouf and Mostafa Blidia},
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},
}
TY  - JOUR
AU  - Amel Bendali-Braham
AU  - Noureddine Ikhlef-Eschouf
AU  - Mostafa Blidia
TI  - A characterization of be-critical trees
JO  - Comptes Rendus. Mathématique
PY  - 2018
SP  - 115
EP  - 120
VL  - 356
IS  - 2
PB  - Elsevier
DO  - 10.1016/j.crma.2018.01.006
LA  - en
ID  - CRMATH_2018__356_2_115_0
ER  - 
%0 Journal Article
%A Amel Bendali-Braham
%A Noureddine Ikhlef-Eschouf
%A Mostafa Blidia
%T A characterization of be-critical trees
%J Comptes Rendus. Mathématique
%D 2018
%P 115-120
%V 356
%N 2
%I Elsevier
%R 10.1016/j.crma.2018.01.006
%G en
%F CRMATH_2018__356_2_115_0
Amel Bendali-Braham; Noureddine Ikhlef-Eschouf; Mostafa Blidia. 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. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2018.01.006/

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

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

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

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

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

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

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

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

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

[10] D.F. Manlove 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: