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
[Une caractérisation des arbres b_e-critiques]

Présenté par : 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.

Résumé
Abstract

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.

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.

Reçu le : 2016-11-20
Accepté le : 2018-01-15
Publié le : 2018-02-01

DOI : 10.1016/j.crma.2018.01.006

Affiliations des auteurs :

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

@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/

Bibliographie
Cité par

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

Cité par Sources :

Commentaires - Politique

Ces articles pourraient vous intéresser

Simulating the composition and structuration of coloring layers in historical painting from non-invasive spectral reflectance measurements

Fabien Pottier; Morgane Gerardin; Anne Michelin; ...

C. R. Phys (2018)

Rank, term rank and chromatic number of a graph

Saieed Akbari; Hamid-Reza Fanaï

C. R. Math (2005)

Coloration des graphes de reines

Michel Vasquez

C. R. Math (2006)