On the $sd_{b}$-critical graphs

Zamime, Mohamed

doi:10.22108/toc.2023.137558.2069

تعداد نشریات	43
تعداد شماره‌ها	1,647
تعداد مقالات	13,387
تعداد مشاهده مقاله	30,128,206
تعداد دریافت فایل اصل مقاله	12,065,832

	On the $sd_{b}$-critical graphs
Transactions on Combinatorics
دوره 13، شماره 4، اسفند 2024، صفحه 363-375 اصل مقاله (436.92 K)
نوع مقاله: Research Paper
شناسه دیجیتال (DOI): 10.22108/toc.2023.137558.2069
نویسنده
Mohamed Zamime^*
Department of Technology, University Yahia Fares of Medea, c.p 26000, Medea, Algeria
چکیده
A $b$-coloring of a graph\ $G$ is a proper coloring of its vertices such that each color class contains a vertex that has a neighbor in every other color classes. The $b$-chromatic number of a graph $G$, denoted by $b(G)$, is the largest integer $k$ such that $G$ admits a $b$-coloring with $k$ colors. Let $G_{e}$ be the graph obtained from $G$ by subdividing the edge $e $. A graph $G$ is $sd_{b}$-critical if $b(G_{e})<b(G)$ holds for any edge $e$ of $G$. In this paper, we first present \ several basic properties of $sd_{b} $-critical graphs and then we give a characterization of $sd_{b}$-critical $P_{4}$-sparse graphs and $sd_{b}$-critical quasi-line graphs.
کلیدواژه‌ها
$b$-coloring؛ $b$-chromatic number؛ $sd_{b}$-critical graphs

مراجع
[1] R. Balakrishnan and S. Francis Raj, Bounds for the b-chromatic number of vertex-deleted subgraphs and the extremal graphs, Electron. Notes Discrete Math., 34 (2009) 353–358. [2] A. Bendali-Braham, N. Ikhlef-Eschouf and M. Blidia, A characterization of be -critical trees, C. R. Math. Acad. Sci. Paris, 356 (2018) 115–120. [3] A. Bendali-Braham, N. Ikhlef-Eschouf and M. Blidia, A characterization of edge b-critical graphs, Discrete Appl. Math., 238 (2018) 158–160. [4] M. Blidia and N. Ikhlef Eschouf, On b-vertex and b-edge critical graphs, Opuscula Math., 35 (2015) 171–180. [5] M. Blidia, N. Ikhlef Eschouf and F. Maffray, On edge b-critical graphs, Discrete Appl. Math., 180 (2015) 176–180. [6] M. Blidia, N. Ikhlef Eschouf and F. Maffray, On vertex b-critical trees, Opuscula Math., 33 (2013) 19–28. [7] F. Bonomo, G. Duran, F. Maffray, J. Marenco and M. Valencia-Pabon, On the b-coloring of cographs and P4 -sparse graphs, Graphs Combin., 25 (2009) 153–167. [8] A. El-Sahili and M. Kouider, About b-colourings of regular graphs, Util. Math., 80 (2009) 211–215. [9] N. Ikhlef Eschouf, Characterization of some b-chromatic edge critical graphs, Australas. J. Combin., 47 (2010) 21–35. [10] C. T. Hoàng, Perfect graphs, Thesis (Ph.D.)–McGill University (Canada). ProQuest LLC, Ann Arbor, MI, 1985. [11] C. T. Hoàng and M. Kouider, On the b-dominating coloring of graphs, Discrete Appl. Math., 152 (2005) 176–186. [12] R. W. Irving and D. F. Manlove, The b-chromatic number of graphs, Discrete Appl. Math., 91 (1999) 127–141. [13] B. Jamison and D. Olarui, A tree representation for P4 -sparse graphs, Discrete Appl. Math., 35 (1992) 115–129. [14] A. Kohl, The b-chromatic number of powers of cycles, Discrete Math. Theor. Comput. Sci, 15 (2013) 147–156. [15] M. Kouider and M. Zaker, Bounds for the b-chromatic number of some families of graphs, Discrete Math., 306 (2006) 617–623. [16] F. Maffray, Silva A b-colouring outerplanar graphs with large girth, Discrete Math., 312 (2012) 1769–1803. [17] M. Zamime, M. Kouider and H. Ait Haddadène, On the b-coloring of G − e, Discrete Appl. Math., 188 (2015) 41–50.
آمار تعداد مشاهده مقاله: 205 تعداد دریافت فایل اصل مقاله: 475

سامانه مدیریت نشریات علمی. قدرت گرفته از سیناوب

پیوندهای مفید

اخبار و اعلانات

آمار

On the $sd_{b}$-critical graphs