On extremal properties of perfect 2-colorings
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912376263016448 |
|---|---|
| author | Potapov, Vladimir N. |
| author_facet | Potapov, Vladimir N. |
| contents | A coloring of vertices of a graph is called perfect if, for every vertex, the collection of colors of its neighbors depends only on its own color. The correspondent color partition of vertices is called equitable. We note that a number of bounds (Hoffman bound, Cheeger bound, Bierbrauer--Friedman bound and other) is only reached on perfect $2$-colorings. We show that the Expander Mixing Lemma is another example of an inequality that generates a perfect $2$-coloring. We prove a new upper bound for the size of $S\subset V(G)$ with the fixed average internal degree for an amply regular graph $G$. This bound is reached on the set $S$ if and only if $\{S, V(G)\setminus S\}$ is an equitable partition. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2204_03308 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | On extremal properties of perfect 2-colorings Potapov, Vladimir N. Combinatorics 05C35, 05B30, 05E30 A coloring of vertices of a graph is called perfect if, for every vertex, the collection of colors of its neighbors depends only on its own color. The correspondent color partition of vertices is called equitable. We note that a number of bounds (Hoffman bound, Cheeger bound, Bierbrauer--Friedman bound and other) is only reached on perfect $2$-colorings. We show that the Expander Mixing Lemma is another example of an inequality that generates a perfect $2$-coloring. We prove a new upper bound for the size of $S\subset V(G)$ with the fixed average internal degree for an amply regular graph $G$. This bound is reached on the set $S$ if and only if $\{S, V(G)\setminus S\}$ is an equitable partition. |
| title | On extremal properties of perfect 2-colorings |
| topic | Combinatorics 05C35, 05B30, 05E30 |
| url | https://arxiv.org/abs/2204.03308 |