Characterization and chromatic number of triangle-free graphs with diameter 2
2026-06-02 • Discrete Mathematics
Discrete Mathematics
AI summaryⓘ
The authors study triangle-free graphs that have a diameter of 2, focusing on a special type called 2-self-centered graphs. They found a small mistake in a previous characterization of these graphs by Shekarriz et al. and corrected it with a new, accurate description. Using their improved characterization, they also explored how these graphs can be colored, specifically looking at the chromatic number. Their work helps better understand the structure and coloring of these specific graphs.
triangle-free graphdiameterradius2-self-centered graphgraph isomorphismchromatic numbergraph characterizationstar graph
Authors
Akihiro Higashitani, Diogo Kendy Matsumoto, Naoki Matsumoto
Abstract
In this paper, we consider triangle-free graphs with diameter 2. If a triangle-free graph $G$ with diameter 2 is not isomorphic to a star, then the radius of $G$ is also 2, where such a graph is also called a $2$-self-centered graph. Shekarriz et al. [A characterization for 2-self-centered graphs, Discuss. Math. Graph Theory 38 (2018), 27--37.] gave a characterization of 2-self-centered graphs. However, there is a slight flaw in their characterization. Thus, in this paper, we modify it and prove an accurate characterization of those graphs. Furthermore, by using our characterization, we prove some results concerning the chromatic number of triangle-free graphs with diameter 2.