Extremal regular graphs of given chromatic number
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2019
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914656542523392 |
|---|---|
| author | Rubio-Montiel, Christian |
| author_facet | Rubio-Montiel, Christian |
| contents | We define an extremal $(r|χ)$-graph as an $r$-regular graph with chromatic number $χ$ of minimum order. We show that the Tur{\' a}n graphs $T_{ak,k}$, the antihole graphs and the graphs $K_k\times K_2$ are extremal in this sense. We also study extremal Cayley $(r|χ)$-graphs and we exhibit several $(r|χ)$-graph constructions arising from Tur{\' a}n graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1910_01072 |
| institution | arXiv |
| publishDate | 2019 |
| record_format | arxiv |
| spellingShingle | Extremal regular graphs of given chromatic number Rubio-Montiel, Christian Combinatorics 05C35, 05C15 We define an extremal $(r|χ)$-graph as an $r$-regular graph with chromatic number $χ$ of minimum order. We show that the Tur{\' a}n graphs $T_{ak,k}$, the antihole graphs and the graphs $K_k\times K_2$ are extremal in this sense. We also study extremal Cayley $(r|χ)$-graphs and we exhibit several $(r|χ)$-graph constructions arising from Tur{\' a}n graphs. |
| title | Extremal regular graphs of given chromatic number |
| topic | Combinatorics 05C35, 05C15 |
| url | https://arxiv.org/abs/1910.01072 |