Chromatic number and signless Laplacian spectral radius of graphs

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

References

[1] D. M. Cvetković, M. Doob and H. Sachs, Spectra of Graphs, Theory and Application, Academic Press, Inc., New
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.
[3] D. Cvetković, P. Rowlinson and S. Simić, Eigenvalue bounds for the signless laplacian,Publ. Inst. Math., (Beograd)
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.
[5] A. W. Marshall, I. Olkin and B. C. Arnold, Inequalities: Theory of Majorization and Its Applications, Second
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.
[8] M. R. Oboudi, Distance spectral radius of complete multipartite graphs and majorization, Linear Algebra Appl.,
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.
[11] M. R. Oboudi, On the largest real root of independence polynomials of graphs, an ordering on graphs, and starlike
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.
[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.
Transactions on Combinatorics
Volume 11, Issue 4 - Serial Number 4
December 2022
Pages 327-334

Files

History

  • Receive Date: 23 July 2021
  • Revise Date: 03 December 2021
  • Accept Date: 07 December 2021
  • Published Online: 01 December 2022

Share

How to cite

Statistics