Extremal regular graphs of given chromatic number

Christian Rubio-Montiel

doi:10.61091/ars157-13

paper

Extremal regular graphs of given chromatic number

arXiv:1910.01072 · doi:10.61091/ars157-13

Abstract

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.

arXiv comment11 pages