A characterization of be-critical trees

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

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

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

¹ 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, Tome 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 :

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

@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://archive.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://archive.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://archive.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 b_e-critical trees. Comptes Rendus. Mathématique, Tome 356 (2018) no. 2, pp. 115-120. doi : 10.1016/j.crma.2018.01.006. http://archive.numdam.org/articles/10.1016/j.crma.2018.01.006/

Bibliographie
Cité par

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

Cité par Sources :