A characterization of be-critical trees

Amel Bendali-Braham; Noureddine Ikhlef-Eschouf; Mostafa Blidia

doi:10.1016/j.crma.2018.01.006

Combinatorics/Game theory

A characterization of b_e-critical trees

Presented by: Vladimir Nikiforov

Amel Bendali-Braham ¹; Noureddine Ikhlef-Eschouf ²; Mostafa Blidia ³

¹ Laboratory of Mechanics, Physics and Mathematical Modeling, Faculty of Sciences, University of Médéa, Algeria
² Department of Mathematics and Computer Science, Faculty of Sciences, University of Médéa, Algeria
³ Laboratory LAMDA-RO, Department of Mathematics, University of Blida 1, B.P. 270, Blida, Algeria

Comptes Rendus. Mathématique, Volume 356 (2018) no. 2, pp. 115-120.

Abstract
Résumé

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 $b_{e}$ -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 $b_{e}$ -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é $b_{e}$ -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 $b_{e}$ -critiques.

Received: 2016-11-20
Accepted: 2018-01-15
Published online: 2018-02-01

DOI: 10.1016/j.crma.2018.01.006

Author's affiliations:

Amel Bendali-Braham ¹; Noureddine Ikhlef-Eschouf ²; Mostafa Blidia ³

¹ Laboratory of Mechanics, Physics and Mathematical Modeling, Faculty of Sciences, University of Médéa, Algeria
² Department of Mathematics and Computer Science, Faculty of Sciences, University of Médéa, Algeria
³ 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 b_e-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/

References
Cited by

[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:

Comments - Policy