Document Type : Research Paper

**Author**

Department of Mathematics, College of Sciences, Shiraz University, Shiraz, 71457-44776, Iran

**Abstract**

For any simple graph $G$, the signless Laplacian matrix of $G$ is defined as $D(G)+A(G)$, where $D(G)$ and $A(G)$ are the diagonal matrix of vertex degrees and the adjacency matrix of $G$, respectively. %Let $\chi(G)$ be the chromatic number of $G$ Let $q(G)$ be the signless Laplacian spectral radius of $G$ (the largest eigenvalue of the signless Laplacian matrix of $G$). In this paper we find some relations between the chromatic number and the signless Laplacian spectral radius of graphs. In particular, we characterize all graphs $G$ of order $n$ with odd chromatic number $\chi$ such that $q(G)=2n\Big(1-\frac{1}{\chi}\Big)$. Finally we show that if $G$ is a graph of order $n$ and with chromatic number $\chi$, then under certain conditions, $q(G)<2n\Big(1-\frac{1}{\chi}\Big)-\frac{2}{n}$. This result improves some previous similar results.

**Keywords**

**Main Subjects**

[1] D. M. Cvetković, M. Doob and H. Sachs, Spectra of Graphs, Theory and Application, Academic Press, Inc., New

York, 1980.

York, 1980.

[2] D. Cvetković, P. Rowlinson and S. Simić, An introduction to the theory of graph spectra, London Mathematical

Society Student Texts, 75, Cambridge University Press, Cambridge, 2010.

Society Student Texts, 75, Cambridge University Press, Cambridge, 2010.

[3] D. Cvetković, P. Rowlinson and S. Simić, Eigenvalue bounds for the signless laplacian,Publ. Inst. Math., (Beograd)

81 (2007) 11–27.

81 (2007) 11–27.

[4] C .S. Edwards, C. H. Elphick, Lower bounds for the clique and the chromatic numbers of a graph, Discrete Appl.

Math., 5 (1983) 51–64.

Math., 5 (1983) 51–64.

[5] A. W. Marshall, I. Olkin and B. C. Arnold, Inequalities: Theory of Majorization and Its Applications, Second

Edition, Springer, New York, 2011.

Edition, Springer, New York, 2011.

[6] V. Nikiforov, Chromatic number and spectral radius, Linear Algebra Appl., 426 (2007) 810–814.

[7] M. R. Oboudi, A relation between the signless Laplacian spectral radius of complete multipartite graphs and

majorization, Linear Algebra Appl., 565 (2019) 225–238.

majorization, Linear Algebra Appl., 565 (2019) 225–238.

[8] M. R. Oboudi, Distance spectral radius of complete multipartite graphs and majorization, Linear Algebra Appl.,

583 (2019) 134–145.

583 (2019) 134–145.

[9] M. R. Oboudi, Majorization and the spectral radius of starlike trees, J. Comb. Optim., 36 (2018) 121–129.

[10] M. R. Oboudi, On the difference between the spectral radius and maximum degree of graphs, Algebra Discrete

Math., 24 (2017) 302–307.

Math., 24 (2017) 302–307.

[11] M. R. Oboudi, On the largest real root of independence polynomials of graphs, an ordering on graphs, and starlike

trees, arXiv:1303.3222.

trees, arXiv:1303.3222.

[12] M. R. Oboudi, On the third largest eigenvalue of graphs, Linear Algebra Appl., 503 (2016) 164–179.

[13] H. S. Wilf, Spectral bounds for the clique and independence numbers of graphs, J. Combin. Theory Ser. B, 40

(1986) 113–117.

(1986) 113–117.

[14] H. S. Wilf, The eigenvalues of a graph and its chromatic number, J. London Math. Soc., 42 (1967) 330–332.

[15] G. Yu, Y. Wu and J. Shu, Signless Laplacian spectral radii of graphs with given chromatic number, Linear Algebra

Appl., 435 (2011) 1813–1822.

Appl., 435 (2011) 1813–1822.

December 2022

Pages 327-334