Comparative Analysis of the Properties of the Grötzsch, Thomassen, and Herschel Graphs: A Spectral and Algebraic Approach

Abstract

This paper analyzes and compares the fundamental properties of three well-known graphs: the Grötzsch graph, the Thomassen graph, and the Herschel graph. From the class of Mycielski graphs, the Grötzsch graph is chosen as a representative with the smallest chromatic number of 4 and no triangles. The Grötzsch theorem is discussed in detail, as well as recent results connecting this theorem with the corresponding graph. Next, the spectral characteristics of the Thomassen and Herschel graphs are analyzed, with special emphasis on their algebraic structure, which is particularly significant for the application in studies involving large graphs. The research includes the calculation of the eigenvalues and eigenvectors of the Laplacian matrices of these graphs, providing insight into their spectral properties. Modern computational tools are utilized for the visualization and analysis of large graphs, such as the Thomassen graph with 42 vertices. The paper presents the basics of graph theory through isomorphic representations of the three graphs, as well as the theoretical framework necessary for understanding their intrinsic properties, which is the ultimate goal of this research.