Generalized Grötzsch Graphs

08/11/2023

∙

by   Ashish Upadhyay, et al.

∙

0

∙

share

The aim of this paper is to present a generalization of Grötzsch graph. Inspired by structure of the Grötzsch's graph, we present constructions of two families of graphs, G_m and H_m for odd and even values of m respectively and on n = 2m +1 vertices. We show that each member of this family is non-planar, triangle-free, and Hamiltonian. Further, when m is odd the graph G_m is maximal triangle-free, and when m is even, the addition of exactly m/2 edges makes the graph H_m maximal triangle-free. We show that G_m is 4-chromatic and H_m is 3-chromatic for all m. Further, we note some other properties of these graphs and compare with Mycielski's construction.