Extremal chromatic bounds for distance Laplacian eigenvalues

Abstract

For a connected simple graph $G$ on $n$ vertices with chromatic number $\ddot{I}‡$, the distance Laplacian matrix is $\DL(G)=\operatorname{diag}(\Tr_G(v_1),\dots,\Tr_G(v_n))-D(G)$, where $D(G)$ is the distance matrix and $\Tr_G(v)=\sum_{u\in V(G)} d_G(u,v)$ is the transmission. The eigenvalues of $\DL(G)$ are ordered as ${\partial }_1^L(G)\ge {\partial }_2^L(G)\ge \cdots \ge {\partial }_n^L(G)=0$. Building on the chromatic lower bound $\partial^{L}_1(G)\ge n+\ceil{n/χ}$ and subsequent developments, we prove a \emph{color-class majorization principle}: if $({\ell }_1,\dots ,{\ell }_{\ddot{I}}‡)$ are the color-class sizes in an optimal $\ddot{I}‡$-coloring with ${\ell }_1\ge \cdots \ge {\ell }_{\ddot{I}}‡$, then the first ${\ell }_1-1$ distance Laplacian eigenvalues satisfy ${\partial }_i^L(G)\ge n+{\ell }_1$, for $1\le i\le {\ell }_1-1$. This gives sharp lower bounds on the number of eigenvalues above the chromatic threshold $b_χ=n+\ceil{n/χ}$, thereby refining distribution theorems of [Aouchiche and Hansen, Filomat, 2017] and [Pirzada and Khan LAA, 2021]. We further refine clique/independent-set based multiplicity results by deriving explicit chromatic criteria in terms of neighborhood compression, and we generalize the extremal problem for minimum ${\partial }_1^L$ at fixed chromatic number by characterizing the balanced complete multipartite minimizers. Finally, we present a Ky Fan type result, and complement-component consequences of the majorization principle.

21 pages, 4 figures