Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2311.10379 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913584077864960 |
|---|---|
| author | Taranchuk, Vladislav Timmons, Craig |
| author_facet | Taranchuk, Vladislav Timmons, Craig |
| contents | A complete partition of a graph $G$ is a partition of the vertex set such that there is at least one edge between any two parts. The largest $r$ such that $G$ has a complete partition into $r$ parts, each of which is an independent set, is the achromatic number of $G$. We determine the achromatic number of polarity graphs of biaffine planes coming from generalized polygons. Our colorings of a family of unitary polarity graphs are used to solve a problem of Axenovich and Martin on complete partitions of $C_4$-free graphs. Furthermore, these colorings prove that there are sequences of graphs which are optimally complete and have unbounded degree, a problem that had been studied for the sequence of hypercubes independently by Roichman, and Ahlswede, Bezrukov, Blokhuis, Metsch, and Moorhouse. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_10379 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Achromatic colorings of polarity graphs Taranchuk, Vladislav Timmons, Craig Combinatorics A complete partition of a graph $G$ is a partition of the vertex set such that there is at least one edge between any two parts. The largest $r$ such that $G$ has a complete partition into $r$ parts, each of which is an independent set, is the achromatic number of $G$. We determine the achromatic number of polarity graphs of biaffine planes coming from generalized polygons. Our colorings of a family of unitary polarity graphs are used to solve a problem of Axenovich and Martin on complete partitions of $C_4$-free graphs. Furthermore, these colorings prove that there are sequences of graphs which are optimally complete and have unbounded degree, a problem that had been studied for the sequence of hypercubes independently by Roichman, and Ahlswede, Bezrukov, Blokhuis, Metsch, and Moorhouse. |
| title | Achromatic colorings of polarity graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2311.10379 |