Spectral approaches for $d$-improper chromatic number
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909383671152640 |
|---|---|
| author | Guo, Krystal Kang, Ross J. Zwaneveld, Gabriëlle |
| author_facet | Guo, Krystal Kang, Ross J. Zwaneveld, Gabriëlle |
| contents | In this paper, we explore algebraic approaches to $d$-improper and $t$-clustered colourings, where the colouring constraints are relaxed to allow some monochromatic edges. Bilu [J. Comb. Theory Ser. B, 96(4):608-613, 2006] proved a generalization of the Hoffman bound for $d$-improper colourings. We strengthen this theorem by characterizing the equality case. In particular, if the Hoffman bound is tight for a graph $G$, then the $d$-improper Hoffman bound is tight for the strong product $G \boxtimes K_{d+1}$. Moreover, we prove d-improper analogous for the inertia bound by Cvetkovíc and the multi-eigenvalue lower bounds of Elphick and Wocjan.
We conjecture an equality between the chromatic number of a graph $G$ and the $d$-improper chromatic number of its strong product with a complete graph, $G \boxtimes K_{d+1}$, and prove the conjecture in special graph classes, including perfect graphs and graphs with chromatic number at most 4. Other supporting evidence for the conjecture includes a fractional analogue, a clustered analogue, and various spectral relaxations of the equality. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_06941 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Spectral approaches for $d$-improper chromatic number Guo, Krystal Kang, Ross J. Zwaneveld, Gabriëlle Combinatorics Primary 05C15, Secondary 05C50, 05C76 In this paper, we explore algebraic approaches to $d$-improper and $t$-clustered colourings, where the colouring constraints are relaxed to allow some monochromatic edges. Bilu [J. Comb. Theory Ser. B, 96(4):608-613, 2006] proved a generalization of the Hoffman bound for $d$-improper colourings. We strengthen this theorem by characterizing the equality case. In particular, if the Hoffman bound is tight for a graph $G$, then the $d$-improper Hoffman bound is tight for the strong product $G \boxtimes K_{d+1}$. Moreover, we prove d-improper analogous for the inertia bound by Cvetkovíc and the multi-eigenvalue lower bounds of Elphick and Wocjan. We conjecture an equality between the chromatic number of a graph $G$ and the $d$-improper chromatic number of its strong product with a complete graph, $G \boxtimes K_{d+1}$, and prove the conjecture in special graph classes, including perfect graphs and graphs with chromatic number at most 4. Other supporting evidence for the conjecture includes a fractional analogue, a clustered analogue, and various spectral relaxations of the equality. |
| title | Spectral approaches for $d$-improper chromatic number |
| topic | Combinatorics Primary 05C15, Secondary 05C50, 05C76 |
| url | https://arxiv.org/abs/2411.06941 |