Coloring outside the lines: Spectral bounds for generalized hypergraph colorings
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915809794719744 |
|---|---|
| author | Beers, Lies Mulas, Raffaella |
| author_facet | Beers, Lies Mulas, Raffaella |
| contents | It is known that, for an oriented hypergraph with (vertex) coloring number $χ$ and smallest and largest normalized Laplacian eigenvalues $λ_1$ and $λ_N$, respectively, the inequality $χ\geq (λ_N-λ_1)/\min\{λ_N-1,1-λ_1\}$ holds. We provide necessary conditions for oriented hypergraphs for which this bound is tight. Focusing on $c$-uniform unoriented hypergraphs, we then generalize the bound to the setting of \emph{$d$-proper colorings}: colorings in which no edge contains more than $d$ vertices of the same color. We also adapt our proof techniques to derive analogous spectral bounds for \emph{$d$-improper colorings} of graphs and for edge colorings of hypergraphs. Moreover, for all coloring notions considered, we provide necessary conditions under which the bound is an equality. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_17659 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Coloring outside the lines: Spectral bounds for generalized hypergraph colorings Beers, Lies Mulas, Raffaella Combinatorics Spectral Theory It is known that, for an oriented hypergraph with (vertex) coloring number $χ$ and smallest and largest normalized Laplacian eigenvalues $λ_1$ and $λ_N$, respectively, the inequality $χ\geq (λ_N-λ_1)/\min\{λ_N-1,1-λ_1\}$ holds. We provide necessary conditions for oriented hypergraphs for which this bound is tight. Focusing on $c$-uniform unoriented hypergraphs, we then generalize the bound to the setting of \emph{$d$-proper colorings}: colorings in which no edge contains more than $d$ vertices of the same color. We also adapt our proof techniques to derive analogous spectral bounds for \emph{$d$-improper colorings} of graphs and for edge colorings of hypergraphs. Moreover, for all coloring notions considered, we provide necessary conditions under which the bound is an equality. |
| title | Coloring outside the lines: Spectral bounds for generalized hypergraph colorings |
| topic | Combinatorics Spectral Theory |
| url | https://arxiv.org/abs/2506.17659 |