On the $sd_{b}$-critical graphs

Document Type : Research Paper

Author

Department of Technology, University Yahia Fares of Medea, c.p 26000, Medea, Algeria

Abstract

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.

Keywords

Main Subjects

References

[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. Hoàng, Perfect graphs, Thesis (Ph.D.)–McGill University (Canada). ProQuest LLC, Ann Arbor, MI, 1985.
[11] C. T. Hoà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 Haddadène, On the b-coloring of G − e, Discrete Appl. Math., 188 (2015) 41–50.
Transactions on Combinatorics
Volume 13, Issue 4 - Serial Number 4
December 2024
Pages 363-375

Files

History

  • Receive Date: 02 May 2023
  • Revise Date: 06 October 2023
  • Accept Date: 07 October 2023
  • Published Online: 01 December 2024

Share

How to cite

Statistics