New Eigenvalue Bound for the Fractional Chromatic Number
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908634304217088 |
|---|---|
| author | Guo, Krystal Spiro, Sam |
| author_facet | Guo, Krystal Spiro, Sam |
| contents | Given a graph $G$, we let $s^+(G)$ denote the sum of the squares of the positive eigenvalues of the adjacency matrix of $G$, and we similarly define $s^-(G)$. We prove that
\[χ_f(G)\ge 1+\max\left\{\frac{s^+(G)}{s^-(G)},\frac{s^-(G)}{s^+(G)}\right\}\] and thus strengthen a result of Ando and Lin, who showed the same lower bound for the chromatic number $χ(G)$.
We in fact show a stronger result wherein we give a bound using the eigenvalues of $G$ and $H$ whenever $G$ has a homomorphism to an edge-transitive graph $H$. Our proof utilizes ideas motivated by association schemes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2211_04499 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | New Eigenvalue Bound for the Fractional Chromatic Number Guo, Krystal Spiro, Sam Combinatorics 05C50, 05C72 Given a graph $G$, we let $s^+(G)$ denote the sum of the squares of the positive eigenvalues of the adjacency matrix of $G$, and we similarly define $s^-(G)$. We prove that \[χ_f(G)\ge 1+\max\left\{\frac{s^+(G)}{s^-(G)},\frac{s^-(G)}{s^+(G)}\right\}\] and thus strengthen a result of Ando and Lin, who showed the same lower bound for the chromatic number $χ(G)$. We in fact show a stronger result wherein we give a bound using the eigenvalues of $G$ and $H$ whenever $G$ has a homomorphism to an edge-transitive graph $H$. Our proof utilizes ideas motivated by association schemes. |
| title | New Eigenvalue Bound for the Fractional Chromatic Number |
| topic | Combinatorics 05C50, 05C72 |
| url | https://arxiv.org/abs/2211.04499 |