In this paper, we utilize the signless Laplacian eigenvalues of line graphs and the dominant number to determine the limits of chromatic numbers for the line graphs of certain special graphs. The application of Vizing’s theorem helps to justify the existence of larger boundaries in this particular case.

line graph, chromatic number, domination number, signless Laplacian matrix, spectrum.

Received: July 1, 2024; Revision: September 23, 2024; Accepted: October 30, 2024; Published: November 21, 2024

How to cite this article: Kajal Mittal and Pranjali Kekre, Chromatic bounds of a line graph using signless Laplacian values, Advances and Applications in Discrete Mathematics 42(1) (2025), 55-68. https://doi.org/10.17654/0974165825004

This Open Access Article is Licensed under Creative Commons Attribution 4.0 International License

References:
[1] D. Cvetkovic, Chromatic number and the spectrum of a graph, Publ. Inst. Math. (Beograd) 14(28) (1972), 25-38.
[2] G. Chartrand and P. Zhang, Chromatic graph theory, Discrete Math. Appl., CRC Press, Taylor & Francis Group, 2009, pp. 249-250.
[3] D. Gernert, Inequalities between the domination number and the chromatic number of a graph, Discrete Math. 76(2) (1989), 151-153.
[4] A. J. Hoffman, On eigenvalues and colorings of graphs, Graph Theory its Appl., Academic Press, New York, 1970, pp. 79-91.
[5] P. Kekre and K. Mittal, Signless Laplacian spectrum of line graph, J. Calcutta Math. Soc. 19(1) (2023), 15-28.
[6] P. Kekre and K. Mittal, Bounds and algorithm for the domination number of line graph using signless Laplacian matrix, Indian J. Nat. Sci. 3(75) (2022), 51497-51505.
[7] M. Li, S. Zhang, C. Wang and C. Ye, Total dominator edge chromatic number of graphs, Int. J. Appl. Math. 51(4) (2021), 1-6.
[8] L. S. de Lima, C. S. Oliveira, N. M. M. de Abreu and V. Nikiforov, The smallest eigenvalue of the signless Laplacian, Linear Algebra Appl. 435(10) (2011), 2570-2584.
[9] J. Umamaheswari and R. Mithra, The study of edge coloring and chromatic graph theory and its applications, Materials Today: Proceedings (2021).
10.1016/j.matpr.2020.10.138.
[10] A. Mansuri and R. S. Chandel, On harmonious chromatic number of and Jñānābha 53(2) (2023), 248-251.
[11] M. R. Oboudi, Chromatic number and signless Laplacian spectral radius of graphs, Trans. Comb. 11(4) (2022), 327-334.
[12] M. R. Oboudi, On the smallest signless Laplacian eigenvalue of graphs, Linear Algebra Appl. 637 (2022), 138-156.
[13] S. Pirzada and S. Khan, Distance Laplacian eigenvalues of graphs and chromatic and independence number, (2022). https://doi.org/10.48550/arXiv.2202.05987.
[14] T. Ramachandran and N. Deepika, Vertex coloring of graph using adjacency matrix, IJERA 10(4) (2020), 1-5.
[15] W. Wang, Z. Yan and J. Qian, Eigenvalues and chromatic number of a signed graph, Linear Algebra Appl. 619 (2021), 137-145.