Extremal Regular Graphs of Given Chromatic Number
División de Matemáticas e Ingeniería, FES Acatlán, Universidad Nacional Autónoma de México, 53150, Naucalpan, Mexico., Christian Rubio-Montiel · Ars Combinatoria · 2023
We define an extremal ( r | χ ) -graph as an r -regular graph with chromatic number χ of minimum order. We show that the Turán graphs T a k , k , the antihole graphs and the graphs K k × K 2 are extremal in this sense. We also study extremal Cayley ( r | χ ) -graphs and we exhibit several ( r | χ ) -graph constructions arising from Turán graphs.